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

About these ads

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

Pingback: The inverse of a triangular matrix by matrix multiplication « The Mobius function Blog
slimCar says:

April 29, 2013 at 7:19 pm

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?

Mats Granvik says:

May 2, 2013 at 9:38 am

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.

	Mats Granvik on The inverse of a triangular ma…
	slimCar on The inverse of a triangular ma…
	Mats Granvik on Rough plot of the von Mangoldt…
	CK on Rough plot of the von Mangoldt…
	CK on Rough plot of the von Mangoldt…

The inverse of a triangular matrix as a binomial series

Like this:

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

Leave a Reply Cancel reply

Recent Comments

Follow “The Mobius function Blog”