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

a_{ij}>0

. Then the following statements hold:

there is a real eigenvalue r of A such that any other eigenvalue $\lambda$ satifies $| \lambda| .$
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.
there is a left (respectively 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 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) $v_{\mbox{norm}}$ and $w_{\mbox{norm}}$ such that ${\sum_i{v_i}}^{}={\sum_i{w_i}}^{}=1$ .
one has the eigenvalue estimate $\mbox{min}_i \sum_{j} a_{ij} \le r \le \mbox{max}_i \sum_{j} a_{ij}$

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

\lambda=1

. In this case the Perron-Frobenius theorem asserts that the eigenvalue

\lambda=1

is simple and all other eigenvalues

\lambda \ne 1

of A satisfy

| \lambda | <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 (resp. right) stochastic then

A_{\infty}

is again left (resp. right) stochastic. Its entries are determined by the stochastic left resp. right eigenvectors

v_{\mbox{norm}}

and

w_{\mbox{norm}}

introduced above. If A is right (resp. left) stochastic then the entry a_ij of

A_{\infty}

is equal to the jth entry of

v_{\mbox{norm}}

(resp. the ith entry of

w_{\mbox{norm}}

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

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

<< Previous

Word Browser

Next >>

kitchen confidential
3c48
nitrene
doug henwood
don mills centre
brigstock
duckpin bowling
baitware
hungarian autonomous province
crystal planet
christian parenti

avalon school
the outward urge
klingon blood wine
stair
james mcclelland
pioneer zephyr
grand street
giussani
arunachal dragon force
list of 00 zip codes
riband wave

the pink panther strikes again
declaration of boulogne
stafford house college
shoot and scoot
googlepedia
operation leo
jane mayer
list of cities in morocco and western sahara
suppression fire
cosmism (russian)
martin classical lectures

john tempesta
madeira cake
thomas love moore
judy feld carr
john haldane
collection (oxford colleges)
uisko class transport vessel
elizabeth haldane
canadian federal budget, 2001
assembly of first nations leadership conventions
past paper