Perron–Frobenius theorem

From Wikipedia, the free encyclopedia

In mathematics, the Perron–Frobenius theorem, named after Oskar Perron and Ferdinand Georg Frobenius, is a theorem in matrix theory about the eigenvalues and eigenvectors of a real positive $n \times n$ matrix:

Let $A = (a i j)$ be a real $n \times n$ matrix with positive entries $a i j > 0$ . Then the following statements hold:

there is a positive real eigenvalue $r$ of $A$ such that any other eigenvalue $λ$ satisfies $| λ | < r$ (i.e. the spectral radius $ρ(A) = r$ ).
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$ are 1-dimensional.
there is a left and a right eigenvector associated with $r$ having positive entries. This means that there exists a row-vector $v=(v_1,\ldots,v_n)$ and a column-vector $w=(w_1,\ldots,w_n)^t$ with positive entries $\,v_i>0,\; w_i>0$ such that $vA=rv, \;\;\; Aw=rw$ . The vectors $v$ and $w$ are then called the left and right (respectively) eigenvectors associated with $r$ In particular there exist two uniquely determined positive eigenvectors $v$ and $w$ associated with $r$ (sometimes also called "stochastic" eigenvectors) $v norm$ and $w norm$ such that ${\sum_i{v_i}}^{}={\sum_i{w_i}}^{}=1$ .
one has the eigenvalue estimate $\min_i \sum_{j} a_{ij} \le r \le \max_i \sum_{j} a_{ij}$

The theorem applies in particular to a positive stochastic matrix. In this case the Perron–Frobenius theorem asserts that (provided all entries are strictly positive) the eigenvalue $λ = 1$ is simple and all other eigenvalues $\lambda \ne 1$ of $A$ satisfy $| λ | < 1$ . Also, in this case there exists a vector having positive entries, summing to $1$ , which is a positive eigenvector associated to the eigenvalue $λ = 1$ . Both properties can then be used in combination to show that the limit $A_{\infty}:= \lim_{k \rightarrow \infty} A^k$ exists and is a positive stochastic matrix of matrix rank one. If $A$ is left or right stochastic then $A_{\infty}$ is again left or right stochastic. Its entries are determined by the (left or right) stochastic eigenvectors $v norm$ and $w norm$ introduced above. If $A$ is right stochastic then the entry $a i j$ of $A_{\infty}$ is equal to the $j$ th entry of $v norm$ ; if $A$ is left stochastic, it is equal to the $i$ th entry of $w norm$ ).

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

Let $A = a i j$ be a real $n \times n$ matrix with non-negative entries $a_{ij} \geq 0$ . Then the following statements hold:

there is a real eigenvalue $r$ of $A$ such that any other eigenvalue $λ$ satisfies $|\lambda| \leq r$ . This property may also be stated more concisely by saying that the spectral radius of $A$ is an eigenvalue.
there is a left (respectively right) eigenvector associated with $r$ having non-negative entries.
one has the eigenvalue estimate $\min_i \sum_{j} a_{ij} \le r \le \max_i \sum_{j} a_{ij}$

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 $n \times n$ matrix is the graph with vertices $1, \ldots, n$ and arc $i j$ if and only if $A_{ij}\neq 0$ . 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 a finite Markov chain, 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] References

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