Next: The spectrum of a Up: The spectrum of a Previous: Linear algebra

# Perron-Frobenius Theory

Let be a real matrix with nonnegative entries. is called primitive if for some we have ; is called irreducible if for all there is a such that .

(Here, for a matrix (or vector) , means that all its entries are positive (nonnegative). The matrix is irreducible if and only if the directed graph with vertices and edges whenever is strongly connected. Note that if is irreducible, then is primitive.)

The period of an irreducible matrix is the greatest common divisor of the integers for which . It is independent of the chosen.

Theorem 1.3.1   Let be irreducible. Then there is a (unique) positive real number with the following properties:

1. There is a real vector with .

2. has geometric and algebraic multiplicity one.

3. For each eigenvalue of we have . If is primitive, then implies . In general, if has period , then has precisely eigenvalues with , namely for . In fact the entire spectrum of is invariant under rotation of the complex plane over an angle about the origin.

4. Any (nonzero) nonnegative left or right eigenvector of has eigenvalue . More generally, if , and , then and ; moreover, if and only if .

5. If or if is a principal minor of , and has eigenvalue , then ; if , then .

Proof:     (i) Let . Then and . Let . Define for :

Now for , , and (, implies , so) ; in fact unless is an eigenvector of . Put and . Then since is compact and is continuous on (but not in general on !), there is an such that

Now and is an eigenvector of , so , and .

(ii) For a vector , write . If , then by the triangle inequality we have . For nonzero this means . If, for some vector , we have , then is eigenvector of (otherwise ), and since we have . Now if is any eigenvector of with eigenvalue , then if is real consider , where is chosen such that but not ; now , i.e., , so is a multiple of . In the general case, both the real and imaginary parts of are multiples of . This shows that the eigenspace of has dimension 1, i.e., that the geometric multiplicity of is 1. We shall look at the algebraic multiplicity later.

(iii) We have seen . If and , then and we had equality in the triangle inequality ; this means that all numbers () have the same angular part (argument). If is primitive, then we can apply this reasoning with instead of , where , and conclude that all have the same angular part. Consequently, in this case is a multiple of a real vector and may be taken real, nonnegative. Now shows that is real, and that . In the general case, is a direct sum of primitive matrices , and if is the corresponding decomposition of an eigenvector of (with eigenvalue ), then also is an eigenvector of , with eigenvalue , for any -th root of unity . (Here we assume that the are ordered in such a way that in the arrows point from the subset corresponding to to the subset corresponding to .) Since has a unique eigenvalue of maximum modulus (let be the (nonsquare) submatrix of describing the arrows in between the subset corresponding to to the subset corresponding to ; then and if , then where , so that all have the same eigenvalue of maximum modulus), it follows that has precisely such eigenvalues.

(iv) Doing the above for left eigenvectors instead of right ones, we find with . If and , then . It follows that either or . Taking , or , we see that ( ). Similarly, if , then so that ; also , so . If , then so .

(v) If , , then , so . But if then is eigenvector of and and , so .

(vi) Finally, in order to prove that is a simple root of , the characteristic polynomial of , we have to show that is nonzero for . But and , and by (v) we have for .

Remark In case but not necessarily irreducible, we can say the following.

(i) The spectral radius of is an eigenvalue, and there are nonnegative left and right eigenvectors corresponding to it.

(ii) If and has eigenvalue , then .

( Proof:    (i) Use continuity arguments; (ii) the old proof still applies.)

For more details, see the exposition of the Perron-Frobenius theory in Gantmacher [12], Chapter XIII; cf. also Varga [33], Marcus & Minc [27], Berman & Plemmons [2], Seneta [29], Chapter 1.

Next: The spectrum of a Up: The spectrum of a Previous: Linear algebra
Andries Brouwer 2003-09-30