## 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

1. Nick says: