Perron-Frobenius' theorem

The Perron-Frobenius theorem deals with the existence of a positive eigenvector to a positive amount largest eigenvalues of non-negative matrices . The statements have an important meaning for example for the power method and Markov chains .

The theorem was first shown by Oskar Perron for the simpler case of positive matrices and then generalized by Ferdinand Georg Frobenius .

The terms positive and non-negative are to be understood element-wise:

${\displaystyle A={\begin{pmatrix}a_{11}&\ldots &a_{1n}\\\vdots &&\vdots \\a_{n1}&\ldots &a_{nn}\end{pmatrix}}>0\iff a_{ij}>0,\ i,j=1,\ldots ,n.}$

This also introduces a partial order among matrices, one writes if applies. ${\displaystyle A\leq B}$ ${\displaystyle B-A\geq 0}$

Positive matrices

For positive matrices the theorem says that the spectral radius of is at the same time a positive, simple eigenvalue of , ${\displaystyle A>0}$ ${\displaystyle \varrho (A)}$ ${\displaystyle A}$ ${\displaystyle A}$

${\displaystyle \lambda _{1}=\varrho (A)>0,}$

for which there is also a positive eigenvector , is also greater than the amounts of all other eigenvalues ​​of the matrix, ${\displaystyle x>0}$ ${\displaystyle Ax=\varrho (A)x.}$ ${\displaystyle \lambda _{1}}$

${\displaystyle \lambda _{1}>|\lambda _{j}|,\ j=2,\ldots ,n.}$

Furthermore, the spectral radius is a monotonous mapping of positive matrices,

${\displaystyle 0<A<B\ \Rightarrow \ 0<\varrho (A)<\varrho (B).}$

More generally the theorem also applies to primitive matrices .

Non-negative matrices

If only applies, then additional requirements must be made on the matrix: ${\displaystyle A\geq 0}$

For an irreducible non-negative matrix is spectral radius is a positive, simple eigenvalue of the matrix and there to a positive eigenvector with the spectral radius depends monotonically from off . ${\displaystyle A\geq 0}$ ${\displaystyle \varrho (A)}$ ${\displaystyle x>0}$ ${\displaystyle Ax=\varrho (A)x.}$ ${\displaystyle A}$ ${\displaystyle 0\leq A\leq B\Rightarrow \varrho (A)\leq \varrho (B)}$

However, this theorem does not exclude that different eigenvalues can exist with the absolute value . However, if is primitive , that is, a power for one is positive, then there is only one eigenvalue of with . ${\displaystyle |\lambda |=\varrho (A)}$ ${\displaystyle A}$ ${\displaystyle A^{m}}$ ${\displaystyle m\in \mathbb {N} }$ ${\displaystyle \lambda }$ ${\displaystyle A}$ ${\displaystyle |\lambda |=\varrho (A)}$

example

Consider the nonnegative matrices

${\displaystyle A={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}},\ B={\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}},\ C={\begin{pmatrix}0&3&0\\0&2&1\\1&0&2\end{pmatrix}}.}$

The matrix has twice the eigenvalue because it is reducible and the eigenvalue because the block is cyclic . There is also an eigenvalue for the matrix , but there are two more complex eigenvalues ​​with the same amount, since it is also cyclic . Only when is greater than the amount one of the other eigenvalues . And the positive eigenvector belongs to the greatest eigenvalue 3 . ${\displaystyle A}$ ${\displaystyle 1=\varrho (A)}$ ${\displaystyle -1}$ ${\displaystyle A_{MM}}$ ${\displaystyle B}$ ${\displaystyle \varrho (B)=1}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle \lambda _{1}=3=\varrho (C)}$ ${\displaystyle {\frac {1}{2}}(1\pm i{\sqrt {3}})}$ ${\displaystyle (1,1,1)^{T}}$

Applications

The meaning of the sentences is based on the fact that one can check the essential prerequisites positivity or nonnegativity directly and their statements are important for the convergence of the power method and the convergence against the stationary distribution in Markov chains .

Particular by removing the intrinsic value amounts it is for the convergence of important which fully applies only to primitive (and thus particularly in positive) matrices. This is why Google's PageRank algorithm uses a positive matrix with the damping factor instead of the pure link matrix. ${\displaystyle \varrho (A)>|\lambda |}$ ${\displaystyle \lambda \not =\varrho (A)}$ ${\displaystyle d>0}$ ${\displaystyle T\geq 0}$

literature

• Bertram Huppert : Applied Linear Algebra , Walter de Gruyter (1990). ISBN 3-11-012107-7 .
• O. Perron: On the theory of matrices , Math. Ann. 64: 248-263 (1907).
• G. Frobenius: About matrices from non-negative elements , Berl. Ber. 1912, 456-477.
• Thomas W. Hawkins : Continued fractions and the origins of the Perron-Frobenius theorem , Archive History Exact Sciences, 62, 2008, 655-717