Perron–Frobenius theorem: Definition from Answers.com

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).

1 Statement for positive matrices
- 1.1 Example
- 1.2 Towards proofs
2 Application to stochastic matrices
3 Perron-Frobenius theorem for non-negative matrices
4 Generalizations
5 References

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.

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.
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.
There exists a left eigenvector v of A associated with r, v = (v₁,…,v_n) (row vector), having strictly positive components:

$vA=rv, \quad v_i>0, 1\leq i\leq n.$

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

4. The left eigenvector v (respectively right w) associated with r, is the only eigenvector which has positive components, i.e. for all other eigenvectors of A there exists a component which is not positive.

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

$\min_i \sum_{j} a_{ij} \le r \le \max_i \sum_{j} a_{ij}.$

Actually the second inequality is a particular case of the general inequality: any induced norm satisfies the inequality $\left \| A \right \| \ge |\lambda| ,$ for any eigenvalue $λ$ . The infinity norm of matrix is just the maximum of row sums $\left \| A \right \| _\infty = \max \limits _{1 \leq i \leq m} \sum _{j=1} ^n | a_{ij} |.$ Hence the second inequality is a corollary of $\left \| A \right \|_\infty \ge |\lambda|,$ while the first inequality is specific for positive matrices.

Other way to see the second inequality is Gershgorin circle theorem, however the first method is more straight-forward.

Example

Consider a right stochastic matrix - a square matrix each of whose rows consists of nonnegative real numbers, with each row summing to 1. Then its right Perron–Frobenius eigenvector is just a vector (1,1,...,1). And the corresponding eigenvalue is 1.

The proof is simple: (1,1,...,1) is right eigenvector with eigenvalue 1 - self-evident. The proof that 1 is maximum eigenvalue immediately follows from the inequality above: $r \le \max_i \sum_{j} a_{ij},$ since all sums equal to 1.

Towards proofs

The existence of the strictly positive eigenvector and eigenvalue can be actually argued in a very simple way. Recall that power method states that the sequence of vectors $b_{k+1} = Ab_k / \|Ab_k\|$ converges to the eigenvector with the maximum eigenvalue, starting from any vector b₀ except measure zero set. Let us start with strictly positive starting vector b₀ (which does not belong to this measure zero set). All vectors b_k will also be strictly positive. Hence the limiting vector - i.e. the dominant eigenvector for A will have non-negative components and corresponding eigenvalue will be real positive number. The final step is to ensure strict positivity of components. Av=r v, it is obvious that Aw has strictly positive components for any non-negative, non-zero vector w. Hence v=Av/r has strictly positive components.

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

$B = \lim_{k \rightarrow \infty} A^k$

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.

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$ and irreducible. 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}.$

In the book 'Nonnegative matrices and applications' By R. B. Bapat, T. E. S. Raghavan, this theory is divided into two parts, theorem 1.4.4 and theorem 1.7.3, for irreducible matrices and reducible ones respectively, which may indicate some incompleteness or inaccuracy of the summary above.

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 $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 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.

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.

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

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	Perron-Frobenius theory (mathematics)
	Frobenius theorem
	Oskar Perron

	The pythagorean theorem can? Read answer...
	What is Lagrange's Theorem? Read answer...
	What is the Zero Theorem? Read answer...

	What is theorems?
	Vietnam War was norman j. perron in vietnam?
	Find Robert F Perrone LSU?

		Sci-Tech Dictionary. McGraw-Hill Dictionary of Scientific and Technical Terms. Copyright © 2003, 1994, 1989, 1984, 1978, 1976, 1974 by McGraw-Hill Companies, Inc. All rights reserved. Read more
		Wikipedia. This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article "Perron–Frobenius theorem". Read more

Perron–Frobenius theorem

Contents