Perron-Frobenius theorem

In mathematics, the Perron-Frobenius theorem is a theorem in matrix theory about the eigenvalues and eigenvectors of a real positive n×n matrix:

Let A = (a_ij) be a real n×n matrix with positive entries <math>a_{ij}>0<math>. Then the following statements hold:

1. there is a real eigenvalue r of A such that any other eigenvalue <math>\lambda<math> satisfies <math>| \lambda|
2. the eigenvalue r is simple: r is a simple root of the characteristic polynomial of A. In particular both the right and left eigenspace associated to r is 1-dimensional.
3. there is a left (respectively right) eigenvector associated with r having positive entries. This means that there exists a row-vector <math>v=(v_1,\ldots,v_n)<math> and a column-vector <math>w=(w_1,\ldots,w_n)^t<math> with positive entries <math>\,v_i>0,\; w_i>0<math> such that <math> vA=rv, \;\;\; Aw=rw <math>. The vector v (resp. w) is then called a left (resp. right) eigenvector associated with r. In particular there exist two uniquely determined left (resp. right) positive eigenvectors associated with r (sometimes also called "stochastic" eigenvectors) <math>v_{\mbox{norm}}<math> and <math>w_{\mbox{norm}}<math> such that <math> {\sum_i{v_i}}^{}={\sum_i{w_i}}^{}=1<math>.
4. one has the eigenvalue estimate <math>\mbox{min}_i \sum_{j} a_{ij} \le r \le \mbox{max}_i \sum_{j} a_{ij}<math>

The first statement says that the spectral radius of the matrix A coincides with r. The theorem applies in particular to a positive stochastic matrix. A right (respectively left) stochastic matrix A is a non-negative real matrix such that its row sums (respectively column sums) are all equal to 1. In this case the vector having constant entries equal to 1 is a right (resp. left) positive eigenvector associated to the eigenvalue <math>\lambda=1<math>. In this case the Perron-Frobenius theorem asserts that the eigenvalue <math>\lambda=1<math> is simple and all other eigenvalues <math>\lambda \ne 1<math> of A satisfy <math>| \lambda | <1<math>. Both properties can then be used in combination to show that the limit <math> A_{\infty}:= \lim_{k \rightarrow \infty} A^k <math> exists and is a positive stochastic matrix of matrix rank one. If A is left (resp. right) stochastic then <math> A_{\infty}<math> is again left (resp. right) stochastic. Its entries are determined by the stochastic left resp. right eigenvectors <math>v_{\mbox{norm}}<math> and <math>w_{\mbox{norm}}<math> introduced above. If A is right (resp. left) stochastic then the entry a_ij of <math> A_{\infty}<math> is equal to the jth entry of <math>v_{\mbox{norm}}<math> (resp. the ith entry of <math>w_{\mbox{norm}}<math>). This result has a natural interpretation in the theory of finite Markov chains (where it is the matrix-theoretic equivalent of the convergence of a finite Markov chain, formulated in terms of the transition matrix of the chain).

The Perron-Frobenius theorem can be further generalized to the class of block-indecomposable non-negative matrices (called "irreducible" in reference [1] below, also called regular in the stochastic case). In particular it also holds if some positive power B = A^k, k > 0 of the non-negative matrix A has positive entries.

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