Perron–Frobenius theorem

From Wikipedia, the free encyclopedia

In linear algebra, the Perron–Frobenius theorem, named after Oskar Perron and Georg Frobenius, asserts that a real square matrix with positive entries has a unique largest real eigenvalue and that the corresponding eigenvector has strictly positive components. This theorem has important applications to probability theory (ergodicity of Markov chains) and the theory of dynamical systems (subshifts of finite type).

Contents 1 Statement for positive matrices 2 Application to stochastic matrices 3 Perron-Frobenius theorem for non-negative matrices 4 Generalizations 5 References

[edit] Statement for positive matrices

Let A = (a_ij) be a real n × n matrix with strictly positive entries a_ij > 0. Then the following statements hold.

1. There is a positive real number r, called the Perron–Frobenius eigenvalue, such that r is an eigenvalue of A and any other eigenvalue λ (possibly complex) is strictly smaller than r in absolute value, |λ| < r. In particular, the spectral radius ρ(A) is equal to r.
2. The Perron–Frobenius eigenvalue is simple: r is a simple root of the characteristic polynomial of A. Consequently, both the right and the left eigenspace associated to r is one-dimensional.
3. There exists a left eigenvector v of A associated with r, v = (v₁,…,v_n) (row vector), having strictly positive components:

Likewise, there exists a right eigenvector w associated with r (column vector) having strictly positive components.

Eigenvectors v and w are usually normalized so that the sum of their components is equal to 1; in this case, they are sometimes called stochastic eigenvectors. The Perron–Frobenius eigenvalue satisfies the estimate

[edit] Application to stochastic matrices

Let A be a strictly positive stochastic matrix. Then r = 1 is the Perron–Frobenius eigenvalue. Thus, all other eigenvalues of A are strictly less than 1 in absolute value, 1 is a simple eigenvalue of A and admits left and right eigenvectors v (row vector) and w (column vector) with strictly positive entries and the sum of the components equal to 1. These properties can then be used to show that the limit

exists and is a positive stochastic matrix of matrix rank one, whose entries b_ij are determined by the appropriate (left or right) Perron–Frobenius eigenvector. If the matrix A is left stochastic then for all j holds b_ij = w_i, the ith entry of the normalized Perron–Frobenius right eigenvector w. If A is right stochastic then similarly for all i holds b_ij = v_j.

[edit] Perron-Frobenius theorem for non-negative matrices

Let A = (a_ij) be a real matrix with non-negative entries and irreducible. Then the following statements hold:

1. there is a real eigenvalue r of A such that any other eigenvalue λ satisfies . This property may also be stated more concisely by saying that the spectral radius of A is an eigenvalue.
2. there is a left (respectively right) eigenvector associated with r having non-negative entries.
3. one has the eigenvalue estimate

Some simple examples are provided by (0,1)-matrices: the identity matrix has entries of 1s and 0s, and the single eigenvalue 1, with multiplicity n. Similarly, a nilpotent matrix (such as 1s above the diagonal, 0s elsewhere) has eigenvalue 0, with algebraic multiplicity n and geometric multiplicity 1. These show that the bounds are sharp, and that r need not be positive (but remains nonnegative). Permutation matrices provide further instructive examples, where all eigenvalues are roots of unity.

With respect to the theorem above related to positive matrices, the left and right eigenvectors associated with the Perron root r are no longer guaranteed to be positive; but remain non-negative. Furthermore, the Perron root is no longer necessarily simple. If one requires the matrix A to be irreducible as well as non-negative, the eigenvector has (strictly) positive entries. Note that a positive matrix is irreducible (as its associated graph is fully connected) but the converse is not necessarily true. And if A is primitive (A^k > 0 for some k), then all the results above given for the case of a positive matrix apply.

This generalization of the Perron-Frobenius theorem has particular use in algebraic graph theory. The "underlying graph" of a nonnegative real matrix is the graph with vertices and arc ij if and only if . If the underlying graph of such a matrix is strongly connected, then the matrix is irreducible, and thus the generalized Perron-Frobenius theorem applies. In particular, the adjacency matrix of a connected graph is irreducible.

This result has a natural interpretation in the theory of finite Markov chains (where it is the matrix-theoretic equivalent of the convergence of an irreducible finite Markov chain to its stationary distribution, formulated in terms of the transition matrix of the chain; see, for example, the article on the subshift of finite type). More generally, it is frequently applied in the theory of transfer operators, where it is commonly known as the Ruelle-Perron–Frobenius theorem (named after David Ruelle). In this case, the leading eigenvalue corresponds to the thermodynamic equilibrium of a dynamical system, and the lesser eigenvalues to the decay modes of a system that is not in equilibrium.

[edit] Generalizations

These results extend rather naturally to quasipositive matrices and essentially nonnegative matrices which occur in the study of continuous-time processes. Is also closely related to Z-matrix theory and M-matrix theory. The Gershgorin circle theorem also predicts the possible range of eigenvalues of general matrices.

[edit] References

1. R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, 1990 (chapter 8).
2. A. Graham, Nonnegative Matrices and Applicable Topics in Linear Algebra, John Wiley&Sons, New York, 1987.
3. Henryk Minc, Nonnegative matrices, John Wiley&Sons, New York, 1988, ISBN 0-471-83966-3
4. C. Godsil and G. Royle, Algebraic Graph Theory, Springer, 2001 (chapter 8).
5. A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Academic Press, 1979 (chapter 2), ISBN 0-12-092250-9