## The inverse of a triangular matrix using forward substitution

This post is about how to invert a lower triangular matrix ${A}$ by forward substitution.

Consider a matrix ${X}$ which is the matrix inverse of another ${n*n}$ sized triangular matrix ${A}$. We take the definition of matrix inversion as a starting point:

${A*X=I}$

Here ${A*X}$ is the matrix multiplication of ${X}$ times ${A}$ and ${I}$ is the identity matrix, kind of the equivalent of the number 1 of the natural numbers 1,2,3… but as a matrix.
By writing out elements this could for example look like:
$\left(\begin{array}{cccccc}a_{\mathrm{11}}&0&0&0&0&0\\ a_{\mathrm{21}}&a_{\mathrm{22}}&0&0&0&0\\ a_{\mathrm{31}}&a_{\mathrm{32}}&a_{\mathrm{33}}&0&0&0\\ a_{\mathrm{41}}&a_{\mathrm{42}}&a_{\mathrm{43}}&a_{\mathrm{44}}&0&0\\ a_{\mathrm{51}}&a_{\mathrm{52}}&a_{\mathrm{53}}&a_{\mathrm{54}}&a_{\mathrm{55}}&0\\ a_{\mathrm{61}}&a_{\mathrm{62}}&a_{\mathrm{63}}&a_{\mathrm{64}}&a_{\mathrm{65}}&a_{\mathrm{66}}\end{array}\right){*}\left(\begin{array}{cccccc}x_{\mathrm{11}}&x_{\mathrm{12}}&x_{\mathrm{13}}&x_{\mathrm{14}}&x_{\mathrm{15}}&x_{\mathrm{16}}\\ x_{\mathrm{21}}&x_{\mathrm{22}}&x_{\mathrm{23}}&x_{\mathrm{24}}&x_{\mathrm{25}}&x_{\mathrm{26}}\\ x_{\mathrm{31}}&x_{\mathrm{32}}&x_{\mathrm{33}}&x_{\mathrm{34}}&x_{\mathrm{35}}&x_{\mathrm{36}}\\ x_{\mathrm{41}}&x_{\mathrm{42}}&a_{\mathrm{43}}&x_{\mathrm{44}}&x_{\mathrm{45}}&x_{\mathrm{46}}\\ x_{\mathrm{51}}&x_{\mathrm{52}}&x_{\mathrm{53}}&x_{\mathrm{54}}&x_{\mathrm{55}}&x_{\mathrm{51}}\\ x_{\mathrm{61}}&x_{\mathrm{62}}&x_{\mathrm{63}}&x_{\mathrm{64}}&x_{\mathrm{65}}&x_{\mathrm{66}}\end{array}\right){=}\left(\begin{array}{cccccc}1&0&0&0&0&0\\ 0&1&0&0&0&0\\ 0&0&1&0&0&0\\ 0&0&0&1&0&0\\ 0&0&0&0&1&0\\ 0&0&0&0&0&1\end{array}\right)$

However it is a fact that the inverse of a triangular matrix is also a triangular matrix and therefore we can write the equation as follows:
$\left(\begin{array}{cccccc}a_{\mathrm{11}}&0&0&0&0&0\\ a_{\mathrm{21}}&a_{\mathrm{22}}&0&0&0&0\\ a_{\mathrm{31}}&a_{\mathrm{32}}&a_{\mathrm{33}}&0&0&0\\ a_{\mathrm{41}}&a_{\mathrm{42}}&a_{\mathrm{43}}&a_{\mathrm{44}}&0&0\\ a_{\mathrm{51}}&a_{\mathrm{52}}&a_{\mathrm{53}}&a_{\mathrm{54}}&a_{\mathrm{55}}&0\\ a_{\mathrm{61}}&a_{\mathrm{62}}&a_{\mathrm{63}}&a_{\mathrm{64}}&a_{\mathrm{65}}&a_{\mathrm{66}}\end{array}\right){*}\left(\begin{array}{cccccc}x_{\mathrm{11}}&0&0&0&0&0\\ x_{\mathrm{21}}&x_{\mathrm{22}}&0&0&0&0\\ x_{\mathrm{31}}&x_{\mathrm{32}}&x_{\mathrm{33}}&0&0&0\\ x_{\mathrm{41}}&x_{\mathrm{42}}&a_{\mathrm{43}}&x_{\mathrm{44}}&0&0\\ x_{\mathrm{51}}&x_{\mathrm{52}}&x_{\mathrm{53}}&x_{\mathrm{54}}&x_{\mathrm{55}}&0\\ x_{\mathrm{61}}&x_{\mathrm{62}}&x_{\mathrm{63}}&x_{\mathrm{64}}&x_{\mathrm{65}}&x_{\mathrm{66}}\end{array}\right){=}\left(\begin{array}{cccccc}1&0&0&0&0&0\\ 0&1&0&0&0&0\\ 0&0&1&0&0&0\\ 0&0&0&1&0&0\\ 0&0&0&0&1&0\\ 0&0&0&0&0&1\end{array}\right)$

We then proceed by solving n different equation systems for each column of ${X}$. Here ${x_{\mathrm{n}}}$ denotes the n:th column of ${X}$ and the somewhat unorthodox ${i_{\mathrm{n}}}$ denotes the n:th column of the identity matrix ${I}$.

Equation system 1: ${A*x_{\mathrm{1}}=i_{\mathrm{1}}}$:

$\left(\begin{array}{cccccc}a_{\mathrm{11}}&0&0&0&0&0\\ a_{\mathrm{21}}&a_{\mathrm{22}}&0&0&0&0\\ a_{\mathrm{31}}&a_{\mathrm{32}}&a_{\mathrm{33}}&0&0&0\\ a_{\mathrm{41}}&a_{\mathrm{42}}&a_{\mathrm{43}}&a_{\mathrm{44}}&0&0\\ a_{\mathrm{51}}&a_{\mathrm{52}}&a_{\mathrm{53}}&a_{\mathrm{54}}&a_{\mathrm{55}}&0\\ a_{\mathrm{61}}&a_{\mathrm{62}}&a_{\mathrm{63}}&a_{\mathrm{64}}&a_{\mathrm{65}}&a_{\mathrm{66}}\end{array}\right){*}\left(\begin{array}{cccccc}x_{\mathrm{11}}\\ x_{\mathrm{21}}\\ x_{\mathrm{31}}\\ x_{\mathrm{41}}\\ x_{\mathrm{51}}\\ x_{\mathrm{61}}\end{array}\right){=}\left(\begin{array}{cccccc}1\\ 0\\ 0\\ 0\\ 0\\ 0\end{array}\right)$

Equation system 2: ${A*x_{\mathrm{2}}=i_{\mathrm{2}}}$:

$\left(\begin{array}{cccccc}a_{\mathrm{11}}&0&0&0&0&0\\ a_{\mathrm{21}}&a_{\mathrm{22}}&0&0&0&0\\ a_{\mathrm{31}}&a_{\mathrm{32}}&a_{\mathrm{33}}&0&0&0\\ a_{\mathrm{41}}&a_{\mathrm{42}}&a_{\mathrm{43}}&a_{\mathrm{44}}&0&0\\ a_{\mathrm{51}}&a_{\mathrm{52}}&a_{\mathrm{53}}&a_{\mathrm{54}}&a_{\mathrm{55}}&0\\ a_{\mathrm{61}}&a_{\mathrm{62}}&a_{\mathrm{63}}&a_{\mathrm{64}}&a_{\mathrm{65}}&a_{\mathrm{66}}\end{array}\right){*}\left(\begin{array}{cccccc}0\\ x_{\mathrm{22}}\\ x_{\mathrm{32}}\\ x_{\mathrm{42}}\\ x_{\mathrm{52}}\\ x_{\mathrm{62}}\end{array}\right){=}\left(\begin{array}{cccccc}0\\ 1\\ 0\\ 0\\ 0\\ 0\end{array}\right)$

Equation system 3: ${A*x_{\mathrm{3}}=i_{\mathrm{3}}}$:

$\left(\begin{array}{cccccc}a_{\mathrm{11}}&0&0&0&0&0\\ a_{\mathrm{21}}&a_{\mathrm{22}}&0&0&0&0\\ a_{\mathrm{31}}&a_{\mathrm{32}}&a_{\mathrm{33}}&0&0&0\\ a_{\mathrm{41}}&a_{\mathrm{42}}&a_{\mathrm{43}}&a_{\mathrm{44}}&0&0\\ a_{\mathrm{51}}&a_{\mathrm{52}}&a_{\mathrm{53}}&a_{\mathrm{54}}&a_{\mathrm{55}}&0\\ a_{\mathrm{61}}&a_{\mathrm{62}}&a_{\mathrm{63}}&a_{\mathrm{64}}&a_{\mathrm{65}}&a_{\mathrm{66}}\end{array}\right){*}\left(\begin{array}{cccccc}0\\ 0\\ x_{\mathrm{33}}\\ x_{\mathrm{43}}\\ x_{\mathrm{53}}\\ x_{\mathrm{63}}\end{array}\right){=}\left(\begin{array}{cccccc}0\\ 0\\ 1\\ 0\\ 0\\ 0\end{array}\right)$

Equation system 4: ${A*x_{\mathrm{4}}=i_{\mathrm{4}}}$:

$\left(\begin{array}{cccccc}a_{\mathrm{11}}&0&0&0&0&0\\ a_{\mathrm{21}}&a_{\mathrm{22}}&0&0&0&0\\ a_{\mathrm{31}}&a_{\mathrm{32}}&a_{\mathrm{33}}&0&0&0\\ a_{\mathrm{41}}&a_{\mathrm{42}}&a_{\mathrm{43}}&a_{\mathrm{44}}&0&0\\ a_{\mathrm{51}}&a_{\mathrm{52}}&a_{\mathrm{53}}&a_{\mathrm{54}}&a_{\mathrm{55}}&0\\ a_{\mathrm{61}}&a_{\mathrm{62}}&a_{\mathrm{63}}&a_{\mathrm{64}}&a_{\mathrm{65}}&a_{\mathrm{66}}\end{array}\right){*}\left(\begin{array}{cccccc}0\\ 0\\ 0\\ x_{\mathrm{44}}\\ x_{\mathrm{54}}\\ x_{\mathrm{64}}\end{array}\right){=}\left(\begin{array}{cccccc}0\\ 0\\ 0\\ 1\\ 0\\ 0\end{array}\right)$

Equation system 5: ${A*x_{\mathrm{5}}=i_{\mathrm{5}}}$:

$\left(\begin{array}{cccccc}a_{\mathrm{11}}&0&0&0&0&0\\ a_{\mathrm{21}}&a_{\mathrm{22}}&0&0&0&0\\ a_{\mathrm{31}}&a_{\mathrm{32}}&a_{\mathrm{33}}&0&0&0\\ a_{\mathrm{41}}&a_{\mathrm{42}}&a_{\mathrm{43}}&a_{\mathrm{44}}&0&0\\ a_{\mathrm{51}}&a_{\mathrm{52}}&a_{\mathrm{53}}&a_{\mathrm{54}}&a_{\mathrm{55}}&0\\ a_{\mathrm{61}}&a_{\mathrm{62}}&a_{\mathrm{63}}&a_{\mathrm{64}}&a_{\mathrm{65}}&a_{\mathrm{66}}\end{array}\right){*}\left(\begin{array}{cccccc}0\\ 0\\ 0\\ 0\\ x_{\mathrm{55}}\\ x_{\mathrm{65}}\end{array}\right){=}\left(\begin{array}{cccccc}0\\ 0\\ 0\\ 0\\ 1\\ 0\end{array}\right)$

Equation system 6: ${A*x_{\mathrm{6}}=i_{\mathrm{6}}}$:

$\left(\begin{array}{cccccc}a_{\mathrm{11}}&0&0&0&0&0\\ a_{\mathrm{21}}&a_{\mathrm{22}}&0&0&0&0\\ a_{\mathrm{31}}&a_{\mathrm{32}}&a_{\mathrm{33}}&0&0&0\\ a_{\mathrm{41}}&a_{\mathrm{42}}&a_{\mathrm{43}}&a_{\mathrm{44}}&0&0\\ a_{\mathrm{51}}&a_{\mathrm{52}}&a_{\mathrm{53}}&a_{\mathrm{54}}&a_{\mathrm{55}}&0\\ a_{\mathrm{61}}&a_{\mathrm{62}}&a_{\mathrm{63}}&a_{\mathrm{64}}&a_{\mathrm{65}}&a_{\mathrm{66}}\end{array}\right){*}\left(\begin{array}{cccccc}0\\ 0\\ 0\\ 0\\ 0\\ x_{\mathrm{66}}\end{array}\right){=}\left(\begin{array}{cccccc}0\\ 0\\ 0\\ 0\\ 0\\ 1\end{array}\right)$

Now recall matrix multiplication with this example:
$\left(\begin{array}{cccccc}1&0&0&0&0&0\\ 1&2&0&0&0&0\\ 1&2&3&0&0&0\\ 1&2&3&4&0&0\\ 1&2&3&4&5&0\\ 1&2&3&4&5&6\end{array}\right){*}\left(\begin{array}{cccccc}1\\ 2\\ 3\\ 4\\ 5\\ 6\end{array}\right)$

Which has the intermediary step:
$\begin{array}{ccccccccccccc}1&+&0&+&0&+&0&+&0&+&0&=&1\\ 1&+&4&+&0&+&0&+&0&+&0&=&5\\ 1&+&4&+&9&+&0&+&0&+&0&=&14\\ 1&+&4&+&9&+&16&+&0&+&0&=&30\\ 1&+&4&+&9&+&16&+&25&+&0&=&55\\ 1&+&4&+&9&+&16&+&25&+&36&=&91\end{array}$

That is also how we will rewrite the equations systems:
Equation system 1: ${A*x_{\mathrm{1}}=i_{\mathrm{1}}}$:
$\begin{array}{ccccccccccccc}a_{\mathrm{11}}*x_{\mathrm{11}}&+&0&+&0&+&0&+&0&+&0&=&1\\ a_{\mathrm{21}}*x_{\mathrm{11}}&+&a_{\mathrm{22}}*x_{\mathrm{21}}&+&0&+&0&+&0&+&0&=&0\\ a_{\mathrm{31}}*x_{\mathrm{11}}&+&a_{\mathrm{32}}*x_{\mathrm{21}}&+&a_{\mathrm{33}}*x_{\mathrm{31}}&+&0&+&0&+&0&=&0\\ a_{\mathrm{41}}*x_{\mathrm{11}}&+&a_{\mathrm{42}}*x_{\mathrm{21}}&+&a_{\mathrm{43}}*x_{\mathrm{31}}&+&a_{\mathrm{44}}*x_{\mathrm{41}}&+&0&+&0&=&0\\ a_{\mathrm{51}}*x_{\mathrm{11}}&+&a_{\mathrm{52}}*x_{\mathrm{21}}&+&a_{\mathrm{53}}*x_{\mathrm{31}}&+&a_{\mathrm{54}}*x_{\mathrm{41}}&+&a_{\mathrm{55}}*x_{\mathrm{51}}&+&0&=&0\\ a_{\mathrm{61}}*x_{\mathrm{11}}&+&a_{\mathrm{62}}*x_{\mathrm{21}}&+&a_{\mathrm{63}}*x_{\mathrm{31}}&+&a_{\mathrm{64}}*x_{\mathrm{41}}&+&a_{\mathrm{65}}*x_{\mathrm{51}}&+&a_{\mathrm{66}}*x_{\mathrm{61}}&=&0\end{array}$

Equation system 2: ${A*x_{\mathrm{2}}=i_{\mathrm{2}}}$:
$\begin{array}{ccccccccccccc}0&+&0&+&0&+&0&+&0&+&0&=&0\\ 0&+&a_{\mathrm{22}}*x_{\mathrm{22}}&+&0&+&0&+&0&+&0&=&1\\ 0&+&a_{\mathrm{32}}*x_{\mathrm{22}}&+&a_{\mathrm{33}}*x_{\mathrm{32}}&+&0&+&0&+&0&=&0\\ 0&+&a_{\mathrm{42}}*x_{\mathrm{22}}&+&a_{\mathrm{43}}*x_{\mathrm{32}}&+&a_{\mathrm{44}}*x_{\mathrm{42}}&+&0&+&0&=&0\\ 0&+&a_{\mathrm{52}}*x_{\mathrm{22}}&+&a_{\mathrm{53}}*x_{\mathrm{32}}&+&a_{\mathrm{54}}*x_{\mathrm{42}}&+&a_{\mathrm{55}}*x_{\mathrm{52}}&+&0&=&0\\ 0&+&a_{\mathrm{62}}*x_{\mathrm{22}}&+&a_{\mathrm{63}}*x_{\mathrm{32}}&+&a_{\mathrm{64}}*x_{\mathrm{42}}&+&a_{\mathrm{65}}*x_{\mathrm{52}}&+&a_{\mathrm{66}}*x_{\mathrm{62}}&=&0\end{array}$

Equation system 3: ${A*x_{\mathrm{3}}=i_{\mathrm{3}}}$:
$\begin{array}{ccccccccccccc}0&+&0&+&0&+&0&+&0&+&0&=&0\\ 0&+&0&+&0&+&0&+&0&+&0&=&0\\ 0&+&0&+&a_{\mathrm{33}}*x_{\mathrm{33}}&+&0&+&0&+&0&=&1\\ 0&+&0&+&a_{\mathrm{43}}*x_{\mathrm{33}}&+&a_{\mathrm{44}}*x_{\mathrm{43}}&+&0&+&0&=&0\\ 0&+&0&+&a_{\mathrm{53}}*x_{\mathrm{33}}&+&a_{\mathrm{54}}*x_{\mathrm{43}}&+&a_{\mathrm{55}}*x_{\mathrm{53}}&+&0&=&0\\ 0&+&0&+&a_{\mathrm{63}}*x_{\mathrm{33}}&+&a_{\mathrm{64}}*x_{\mathrm{43}}&+&a_{\mathrm{65}}*x_{\mathrm{53}}&+&a_{\mathrm{66}}*x_{\mathrm{63}}&=&0\end{array}$

Equation system 4: ${A*x_{\mathrm{4}}=i_{\mathrm{4}}}$:
$\begin{array}{ccccccccccccc}0&+&0&+&0&+&0&+&0&+&0&=&0\\ 0&+&0&+&0&+&0&+&0&+&0&=&0\\ 0&+&0&+&0&+&0&+&0&+&0&=&0\\ 0&+&0&+&0&+&a_{\mathrm{44}}*x_{\mathrm{44}}&+&0&+&0&=&1\\ 0&+&0&+&0&+&a_{\mathrm{54}}*x_{\mathrm{44}}&+&a_{\mathrm{55}}*x_{\mathrm{54}}&+&0&=&0\\ 0&+&0&+&0&+&a_{\mathrm{64}}*x_{\mathrm{44}}&+&a_{\mathrm{65}}*x_{\mathrm{54}}&+&a_{\mathrm{66}}*x_{\mathrm{64}}&=&0\end{array}$

Equation system 5: ${A*x_{\mathrm{5}}=i_{\mathrm{5}}}$:
$\begin{array}{ccccccccccccc}0&+&0&+&0&+&0&+&0&+&0&=&0\\ 0&+&0&+&0&+&0&+&0&+&0&=&0\\ 0&+&0&+&0&+&0&+&0&+&0&=&0\\ 0&+&0&+&0&+&0&+&0&+&0&=&0\\ 0&+&0&+&0&+&0&+&a_{\mathrm{55}}*x_{\mathrm{55}}&+&0&=&1\\ 0&+&0&+&0&+&0&+&a_{\mathrm{65}}*x_{\mathrm{55}}&+&a_{\mathrm{66}}*x_{\mathrm{65}}&=&0\end{array}$

Equation system 6: ${A*x_{\mathrm{6}}=i_{\mathrm{6}}}$:
$\begin{array}{ccccccccccccc}0&+&0&+&0&+&0&+&0&+&0&=&0\\ 0&+&0&+&0&+&0&+&0&+&0&=&0\\ 0&+&0&+&0&+&0&+&0&+&0&=&0\\ 0&+&0&+&0&+&0&+&0&+&0&=&0\\ 0&+&0&+&0&+&0&+&0&+&0&=&0\\ 0&+&0&+&0&+&0&+&0&+&a_{\mathrm{66}}*x_{\mathrm{66}}&=&1\end{array}$

These equation systems are then solved by forward substitution. See wikipedia Triangular matrix, forward substitution . If the matrix to be inverted would have been upper triangular then we would have arrived at similar equations to be solved by back substitution.

Mats Granvik mats.granvik(AT)abo.fi

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

### One Response to The inverse of a triangular matrix using forward substitution

1. Nick says:

Thanks, it helped a lot

Comments are closed.