Two Problems, One Mathematics (2 of 2)

4.0 Mathematical Notes
4.1 Questions of Existence and Uniqueness
Sections 2 and 3 of the first part present two problems in which the following system of linear equations is derived:

p^T A = p^T

The elements of A are all non-negative, and each row sums to unity. For a non-trivial solution to exist, unity must be an eigenvalue of A. In a physically-meaningful solution, a corresponding left-hand eigenvector must have non-negative entries, with at least some being strictly positive. Furthermore, we would like the solution to be unique, up to a multiple. (In the economics case, multiplying prices by a constant corresponds to a change in the numeraire.) As a matter of fact, the problems as stated do not yet guarantee uniqueness.

It is easy to show that unity is an eigenvalue for right-hand eigenvectors of A. Let e be the n-element column vector where all elements are unity. Since the rows of A all add up to unity, the following equation must hold:

A e = e

So unity is an eigenvalue of A. (This proof relies on the property that the set of eigenvalues for left-hand eigenvectors of A is the same as the set of eigenvalues for right-hand eigenvectors of A.) Non-negativity and uniqueness, when it obtains are less obvious.

4.2 Irreducible Matrices
The left-hand eigenvector P^T corresponding to the eigenvalue unity contains all positive elements if A is irreducible. Furthermore, if A is irreducible, the left-hand eigenvector P^T is unique, up to a multiple. A matrix is irreducible, obviously, if it is not reducible. To explain this, I need to define what it means for a matrix to be reducible.

Suppose A is transformed by interchanging a pair of rows and then interchanging the corresponding columns. Any permutation of rows and columns can be performed by repeating this operation for an appropriate sequence of pairs of row and column indices. In the economics case, such a sequence of operations corresponds to selecting a different ordering of the industries in which to express A. In the case of page ranks, such a sequence consists in taking a different ordering for the (unranked) pages. In both cases, the ordering is arbitrary, so no problem arises here.

The non-negative matrix A is reducible if there exists such a sequence of operations that transform A into the block structure form:

A1,1	A1,2
0	A2,2

where A_1,1 is a square non-negative irreducible matrix.

I think the meaning of reducibility in the two problems is suggested under the special case where:

• All the elements of A_1,2 are zero, and
• A_2,2 is irreducible (as well as A_1,1)

The economics problem would then correspond to two non-trading islands, each in a self-replacing state with no surplus. The web pages would consist of two islands of web pages, in which links can be used to get from any one page on an island to any other page on that island, but with no path between these islands of pages.

Unity would be a repeated eigenvalue for a reducible A. One solution vector P^T has strictly positive prices for the industries corresponding to A_1,1 and zero prices for the remaining industries. The other solution has zero prices for the industries corresponding to A_1,1 and strictly positive prices corresponding to industries for A_2,2. It seems reasonable to me to assume in the economics model one is considering a single economy. I don't see why in the page rank case, some set of pages cannot be partially isolated in some sense from the remaining pages. A page ranking algorithm needs to address this possibility.

I might as well mention a condition for an interesting generalization of the economics problem. Let A be a non-negative, reducible matrix with no row sums that exceed unity. Suppose the maximum eigenvalue of A_1,1 exceeds the maximum eigenvalue of A_2,2. Then A is a Sraffa matrix. I'm not sure if the definition of a Sraffa matrix requires some of the elements of A_1,2 to be non-negative so that this input-output matrix hangs together to describe a single economy. Some such condition makes sense to me for an analysis of an economy with a surplus.

4.3 Perron-Frobenius Theorems
I state a theorem, or rather, a combination of eight theorems:

Theorem: Let A be an irreducible non-negative nxn matrix. Then:

1. λ_m, the maximum eigenvalue of the matrix A is bounded below by the minimimum row-sum of A and is bounded above by the maximum row-sum of A.
2. The maximum eigenvalue of A is a continuous, increasing function of the elements of A.
3. Let μ = 1/ν be strictly positive. If μ > λ_m, then all the elements of the matrices (μ I - A)^-1 and (I - ν A)^-1 are strictly positive.
4. Any eigenvalue α of A is bounded above in modulus by the maximum eigenvalue of A:

|α| ≤ λ_m

5. The maximum eigenvalue of A is associated with a left-hand eigenvector p^T whose elements are strictly positive:

p^T A = λ_m p^T

p_i > 0, for i = 1, 2, ..., n,

6. The maximum eigenvalue of A is associated with a right-hand eigenvector q whose elements are strictly positive:

A q = λ_m q

q_i > 0, for i = 1, 2, ..., n,

7. To each eigenvalue α of A different from the maximum eigenvalue λ_m there corresponds a non-zero left-hand eigenvector which has at least one negative component.
8. To each eigenvalue α of A different from the maximum eigenvalue λ_m there corresponds a non-zero right-hand eigenvector which has at least one negative component.

I deliberately included more Perron-Frobenius theorems above than I need for this problem. Perron-Forbenius theorems of a slightly different form have also been stated for reducible matrices.

Anyways, from the first condition, one sees that unity is the maximum eigenvalue for an irreducible A in both the economics and page rank problems. From the fifth conditon, it follows that there exists a set of strictly positive prices, in the economics case, or of strictly positive page ranks in the other case. And by the seventh condition, I guess, this is an unique solution (up to a multiple of the eigenvector).

5.0 References

• Kurt Bryan and Tanya Leise, "The $25,000,000,000 Eigenvector: The Linear Algebra Behind Google"
• Luigi L. Pasinetti (1977) Lectures on the Theory of Production, Columbia University Press
• Piero Sraffa (1960) Production of Commodities by Means of Commodities: Prelude to a Critique of Economic Theory, Cambridge University Press