Matrix inverse equals power-series

[Mårten]

Hi!

In an economics book about input-output analysis the following statement is presented, but I cannot find the proof:

(I - A)^{-1} = (I + A + A^2 + A^3 + ... + A^n)

Can someone help me show why this is the case?

P.s. I think there is some assumptions made about A such that all elements a_{ij} is less than 1 and greater than 0. Btw, n goes to infty.

 

[adriank]

So you mean (I - A)^{-1} = \sum_{k=0}^\infty A^k. This is true if the right side converges, which is true if and only if all of the eigenvalues of A have absolute value smaller than 1.

To prove it, multiply both sides by I - A.

 

[Mårten]

Thanks a lot! Easier than I thought.

Now I found another assumption regarding A, and that is that the row sums are all less than 1, and the column sums are also all less than 1. Could that be the same as saying that all eigenvalues have to be less than |1|, and in that case why are these statements equivalent?

 

[adriank]

What exactly do you mean by row sums and column sums?

 

[Mårten]

If the matrix A is

\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix}

then the rowsums are a_{11} + a_{12} < 1 and a_{21} + a_{22} < 1. The columnsums are a_{11} + a_{21} < 1 and a_{12} + a_{22} < 1.

 

[adriank]

Well then that's certainly not true. Maybe you meant absolute values, or something?

An equivalent condition to the eigenvalue condition is that \lvert Ax \rvert < 1 for all x such that \lvert x \rvert = 1.

 

[Mårten]

But if, at the same time, all a_{ij} > 0, it doesn't work then?

Anyhow, is there a way to set up criteria for A making all its eigenvalues less than |1|?

 

[Fredrik]

So you mean (I - A)^{-1} = \sum_{k=0}^\infty A^k. This is true if the right side converges, which is true if and only if all of the eigenvalues of A have absolute value smaller than 1.

To prove it, multiply both sides by I - A.

Thanks a lot! Easier than I thought.

Now I found another assumption regarding A, and that is that the row sums are all less than 1, and the column sums are also all less than 1. Could that be the same as saying that all eigenvalues have to be less than |1|, and in that case why are these statements equivalent?

This isn't a valid proof. If you multiply both sides by I-A and simplify the right-hand side, you're making assumptions about the infinite sum that you can't make at this point. And if you intend to consider the equality in post #1 with a finite number of terms in the sum, the two sides aren't actually equal, so you'd be starting with an equality that's false.

(Maybe you understand this already, but it didn't look that way to me, and you did say that you're an economy student. )

What you need to do is to calculate

\left(\lim_{n\rightarrow\infty}(I+A+A^2+\cdots+A^n)\right)(I-A)

Start by rewriting it as

=\lim_{n\rightarrow\infty}\left((I+A+A^2+\cdots+A^n)(I-A)\right)

and then prove that this is =I. This result implies that I-A is invertible, and that the inverse is that series. The information you were given about the components of A is needed to see that the unwanted term goes to zero in that limit.

 

[Mårten]

Thanks a lot! I really appreciate this help, I think I understand it pretty well now.

Adriank, it seems that my conditions given about A satisfy your condition that \lvert Ax \rvert < 1 for all x such that \lvert x \rvert = 1. I cannot prove it formally that these two conditions are the same (or that my condition follows from Adriank's), but some easy calculations and checks I've made, makes it reasonable. (If someone has the energy to prove it, I wouldn't be late to look at it.)

My conditions about A once more (sorry to not have given them at the same time before): Row sums and column sums are all, one by one, less than 1, and at the same time 0 \leq a_{ij} < 1.

P.s. Actually, I didn't say I'm an economics student, I just said I read an economics book.

 

[Mårten]

Btw, it occurred to me that I don't understand really why all eigenvalues of A have to have absolute value less than 1 in order to make the series above converge. Why does that eigenvalue condition affect the convergence property of the series?

Another follow-up question: Now when we have this nice power expansion for the inverse matrix, is that actually the way (some) matrix inverses is calculated in computers?

 

[adriank]

Following on what Fredrik said, note that
\Bigl(\sum_{k=0}^n A^k\Bigr) (I - A) = I - A^{n+1}.
Now we want to take the limit as n \to \infty to show that
\Bigl(\sum_{k=0}^\infty A^k\Bigr) (I - A) = I.
But for that to be true, you need that
\lim_{n \to \infty} A^{n+1} = 0.
This is true if and only if the operator norm of A is less than 1. And it turns out that the operator norm of A is the largest absolute value of the eigenvalues of A. If you have some other condition that implies this, then that works too.

As for computation, usually that's a very inefficient way to calculate it directly, unless A is nilpotent (so that the series only has finitely many nonzero terms). However, if A is n by n, then you can express Aⁿ in terms of lower powers of A by the Cayley-Hamilton theorem. You could also apply various numerical techniques to directly find the inverse of I - A; a lot of times, all you care about is (I - A)^-1x for some vector x, which can often be done even more efficiently than calculating the full matrix inverse.

 

[Fredrik]

Let's try the Hilbert-Schmidt norm, defined by

\langle A,B\rangle=\operatorname{Tr}A^\dagger B

\|A\|^2=\langle A,A\rangle=\sum_{i,j}a_{ji}^*a_{ji}=\sum_{i,j}|a_{ij}|^2

\|A\|\geq 0

This definition and the information given together imply that if A is a m×m matrix,

\|A\|^2<\sum_{i,j}1=m^2

The norm satisfies

\|AB\|\leq\|A\|\|B\|

so

\|A^{n+1}\|\leq\|A\|^{n+1}=m^{n+1}

but this doesn't converge as n→∞. It looks like the assumption |a_{ij}|<1 isn't strong enough to guarantee convergence. It looks like we would need something like |a_{ij}|<1/m (or another norm to define convergence). Hmm...

 

[Mårten]

It looks like the assumption |a_{ij}|<1 isn't strong enough to guarantee convergence. It looks like we would need something like |a_{ij}|<1/m (or another norm to define convergence). Hmm...

Did you take into account that my assumption wasn't just that |a_{ij}|<1 (actually 0 \leq a_{ij}<1), but also that the row sums and column sums are, one by one, less than 1? In a way, the latter thing seems to imply that |a_{ij}|<1/m, "on the average" at least.

I'll take a look at the operator room in the meantime.

 

[adriank]

Well, the Hilbert-Schmidt norm \lVert \cdot \rVert_{HS} is always bigger than the operator norm, so if A has Hilbert-Schmidt norm less than 1, then its operator norm is also less than 1.

And the Hilbert-Schmidt norm happens to satisfy
\lVert A \rVert_{HS}^2 = \sum_{i,j} \lvert a_{ij} \rvert^2.

 

[Fredrik]

Did you take into account that my assumption wasn't just that |a_{ij}|<1 (actually 0 \leq a_{ij}<1), but also that the row sums and column sums are, one by one, less than 1? In a way, the latter thing seems to imply that |a_{ij}|<1/m, "on the average" at least.

No, I didn't take that into account. When I do, I get

\|A\|^2=\langle A,A\rangle=\sum_{i,j}|a_{ij}|^2<\sum_{i,j}|a_{ij}|=\sum_i\bigg(\sum_j a_{ij}\bigg)<\sum_i 1=m

which is better, but not good enough. We want \|A\|&lt;1. The condition on the "row sums" and "column sums" allows the possibility of a diagonal matrix with entries close to 1 on the diagonal. Such a matrix doesn't have a Hilbert-Schmidt norm <1 (unless m=1). Edit: On the other hand, the components of Aⁿ⁺¹ go to 0 individually for such an A, so the problem with such an A isn't that Aⁿ⁺¹ doesn't go to zero in the H-S norm. It's just that the usual way of showing that it goes to zero doesn't work. The first step of "the usual way" is \|A^{n+1}\|\leq\|A\|^{n+1}, and the right-hand side is simply too big to be useful.

 

[Mårten]

No, I didn't take that into account. When I do, I get

\|A\|^2=\langle A,A\rangle=\sum_{i,j}|a_{ij}|^2&lt;\sum_{i,j}|a_{ij}|=\sum_i\bigg(\sum_j a_{ij}\bigg)&lt;\sum_i 1=m

which is better, but not good enough. We want \|A\|&lt;1. The condition on the "row sums" and "column sums" allows the possibility of a diagonal matrix with entries close to 1 on the diagonal. Such a matrix doesn't have a Hilbert-Schmidt norm <1 (unless m=1). Edit: On the other hand, the components of Aⁿ⁺¹ go to 0 individually for such an A, so the problem with such an A isn't that Aⁿ⁺¹ doesn't go to zero in the H-S norm.

Hm, that was interesting! Could you explain more in detail how your equation above imply that all the components of Aⁿ⁺¹ go to zero when n goes to infty? Where exactly in the equation above does one see that? It was a couple of years ago I took my classes in linear algebra...

(Edit: I do understand that it's enough to show that the elements of A² is less than the elements of A, because then the elements in A³ should be even less, and so on, but I cannot yet see why the elements of A² is less than the elements of A.)

 

[Fredrik]

Hm, that was interesting! Could you explain more in detail how your equation above imply that all the components of Aⁿ⁺¹ go to zero when n goes to infty? Where exactly in the equation above does one see that?

It doesn't, and you don't. For this method of proof to work, we needed the norm of A to be <1.

But I realized something last night. Both Adrian and I have been making this more complicated than it needs to be. We may not need to consider the "fancy" Hilbert-Schmidt and operator norms. We can define the norm of A to be the absolute value of its largest component. For arbitrary B, and an A that satisfies the conditions we've been given, this norm satisfies

\|BA\|=\max\{|(BA)_{ij}|\}=\max\Big\{\Big|\sum_k b_{ik}a_{kj}\Big|\Big\} \leq \max\Big\{\sum_k|b_{ik}a_{kj}|\Big\}\leq\max\Big\{\|B\|\sum_k|a_{kj}|\Big\}&lt;\|B\|a

where a is the largest column sum of A. This a is <1.

So

\|A^{n+1}\|&lt;\|A^{n}\|a&lt;\|A^{n-1}\|a^2\cdots&lt;\|A\|a^n&lt;a^n\rightarrow 0

Since the left-hand side is the largest component of Aⁿ⁺¹, all components of Aⁿ⁺¹ go to zero.

 

[Mårten]

Thanks a lot for this derivation, it was really a nifty one! Just a minor thing, I think the rightmost inequality in the uppermost equation above should say "= ||B||a" not "<||B||a", since you already defined a to be the largest column sum of A, with a<1.

I actually found, just the other day, another proof in Miller & Blair (1985): Input-output analysis: Foundations and extensions, p. 23, which uses the ||A||₁ definition of a matrix norm (that is the maximum column sum according to http://en.wikipedia.org/wiki/Matrix_norm#Induced_norm"), and then uses a similar reasoning as in your lowermost equation above, but uses the Cauchy-Schwarz inequality instead. I think that's not as intuitive as your proof above.

Some more information about input-output analysis in economics for the interested reader. The columns of matrix A describes one by one the input industry j needs from all the different industries i in the rows, to be able to produce an output worth 1 dollar. The rows correspondingly describe the outputs from industry i. (I-A)^-1 is called the Leontief inverse matrix, and column j there describes the total amount of output all industries i have to produce as a result of the consumption of products worth 1 dollar from industry j. This could be useful, when you want to know the energy needed (or any other environmental pressure) resulting from consumption of x dollar's worth of products from a certain industry (if you at the same time know the energy intensities, i.e. J/$, for the industries). The power series is a result of the recursive procedure happening when industries need input from industries, which in turn need input from industries, and so on.

P.s. Sorry for this late reply, I've done some other things for a while.

 

[Mårten]

Correction

I looked through this again, and realized that I was wrong about the condition I gave that the rowsums are less than 1. Fortunately, this doesn't have any implications for the proof above, since it just makes use of that the column sums are less than 1. So the proof still holds!

For anyone surfing by this thread, the following background information could therefore be useful: What you start out with in input-output analysis, is the input-output table which could be written as

Fi + C = x,

where f_ij represents input of products from industry i to industry j, i is a unit column vector (with just ones in it), C is a column vector representing final demand (non-industry use from households, government, et.c.), and x is a column vector representing total ouput (as well as total input). Not included in the above equation is a row of value-added (VA) below the F-matrix - this row could be interpreted as the labour force input (i.e., salaries) required for the industries to produce their products. The different inputs of products and labor for a certain industry j is shown in the rows of column j in the F-matrix and the VA-row; the sum of this column equals the total inputs x_j. This value is the same as the total output x_j from that industry, which is the rowsum of F and C for row j. That is, total costs equal total revenues.

Now, if the matrix A is generated via a_ij = f_ij/x_j, the cells in a certain column j in A, represent the shares of total input x_j. That implies that each column sum of A are less than 1. And that's not the same as saying that the row sums of A are less than 1, since the cells in a row of A doesn't represent the shares of that row's rowsum, according to a_ij = f_ij/x_j. Finally, the above equation can now be written as

Ax + C = x \Leftrightarrow x = (I-A)^{-1}C

(where x becomes a function of the final demand C), and that explains why the topic of this thread was about matrix inverses.