The inverse of a triangular matrix as a binomial series

Consider the lower triangular matrix A:

{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 matrix B:

{B=}\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)

Now replace the all the ones on the main diagonal with zeros:

{C=}\left(\begin{array}{cccccc}0&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)

Then calculate matrix powers as follows:  {D=C^0-C^1+C^2-C^3+C^4-C^5+C^6-C^7+C^8-...} Which is exactly as the binomial series: {(1+x)^{-1}=1-x+x^2-x^3+x^4-x^5+x^6-x^7+x^8-...} except that here it is applied to a triangular matrix and the result is a new triangular matrix D. Notice that {C^0} is the identity matrix.

And then finally divide the ROWS in matrix D with the diagonal elements in A:

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

mats.granvik(AT)abo.fi

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

4 Responses to The inverse of a triangular matrix as a binomial series

  1. Pingback: The inverse of a triangular matrix by matrix multiplication « The Mobius function Blog

  2. slimCar says:

    What is the rate of convergence for calculating the matrix D above, i.e. – how many powers of C is it necessary to compute before arriving at a reasonable approximation fo D? Similarly, is this a feasible algorithm for inverting large, sparse, triangular matrices? What is it’s computational complexity?

  3. Mats Granvik says:

    I believe that the rate of convergence is at minimum one correct row per matrix power in the binomial series. Could be faster or slower but I don’t remember for sure. This is probably not the fastest way to invert a matrix, but is a very nice way since I believe that this called a “formal power series” when you take powers of matrices. Gaussian elimination is probably faster. I have no idea what the computational complexity could be.

  4. Every weekend i used to pay a visit this web page, for the reason that i
    want enjoyment, for the reason that this this site conations really good funny information too.

Comments are closed.