The inverse of a triangular matrix by matrix multiplication

Here follows a technique for inverting triangular matrices that was discovered together with Gary W. Adamson. His blog can be found at http://qntmpkt.blogspot.com/

Consider the lower triangular matrix A:

\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)

Divide the COLUMNS with the diagonal elements in matrix A:

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

Which gives us:

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

Then replace the first element with -1 and the rest of the elements on the main diagonal with zeros. Call this matrix B:

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

Now by matrix multiplication successively square matrix B. That is: Let C=B*B, D=C*C, E=D*D and so on, then the first column in the last matrix (E) will be a convergent. Let those elements be symbolized by the letter r.

\left(\begin{array}{cccccc}r_{\mathrm{11}}&0&0&0&0&0\\ r_{\mathrm{21}}&0&0&0&0&0\\ r_{\mathrm{31}}&0&0&0&0&0\\ r_{\mathrm{41}}&0&0&0&0&0\\ r_{\mathrm{51}}&0&0&0&0&0\\ r_{\mathrm{61}}&0&0&0&0&0\end{array}\right)

Then we only need to divide the ROWS with the elements in the main diagonal of matrix A, to get the first column of the matrix inverse of A.

\left(\begin{array}{cccccc}r_{\mathrm{11}}/a_{\mathrm{11}}&0&0&0&0&0\\ r_{\mathrm{21}}/a_{\mathrm{22}}&0&0&0&0&0\\ r_{\mathrm{31}}/a_{\mathrm{33}}&0&0&0&0&0\\ r_{\mathrm{41}}/a_{\mathrm{44}}&0&0&0&0&0\\ r_{\mathrm{51}}/a_{\mathrm{55}}&0&0&0&0&0\\ r_{\mathrm{61}}/a_{\mathrm{66}}&0&0&0&0&0\end{array}\right)

To calculate the rest of the columns in the inverse of A, repeat for submatrices:

\left(\begin{array}{ccccc}a_{\mathrm{22}}&0&0&0&0\\ a_{\mathrm{32}}&a_{\mathrm{33}}&0&0&0\\ a_{\mathrm{42}}&a_{\mathrm{43}}&a_{\mathrm{44}}&0&0\\ a_{\mathrm{52}}&a_{\mathrm{53}}&a_{\mathrm{54}}&a_{\mathrm{55}}&0\\ a_{\mathrm{62}}&a_{\mathrm{63}}&a_{\mathrm{64}}&a_{\mathrm{65}}&a_{\mathrm{66}}\end{array}\right)

\left(\begin{array}{cccc}a_{\mathrm{33}}&0&0&0\\ a_{\mathrm{43}}&a_{\mathrm{44}}&0&0\\ a_{\mathrm{53}}&a_{\mathrm{54}}&a_{\mathrm{55}}&0\\ a_{\mathrm{63}}&a_{\mathrm{64}}&a_{\mathrm{65}}&a_{\mathrm{66}}\end{array}\right)

and so on.

Edit 21.2.2011: This way of viewing the inverse of a triangular matrix seems to find its explanation when looking at the binomial series expression for inverting a triangular matrix. The inverse of triangular matrix as a binomial series

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 by matrix multiplication

  1. Pingback: The inverse of a triangular matrix using determinants « The Mobius function Blog

Comments are closed.