Perron–Frobenius theorem

The set of Perron - Frobenius deals with the existence of a positive eigenvector to a positive amount largest eigenvalue of non-negative matrices. The statements have an important meaning for example of 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 are positive and not negative to be understood element-wise:

This will also be a partial order is introduced under matrices, to write, if applies.

Positive matrices

For positive matrices ( ie ) of the theorem states that the spectral radius of the same is a positive, simple eigenvalue of,

To which a positive eigenvector also exist, is greater than the addition amounts of all other eigenvalues ​​of the matrix,

Further, the spectral radius is a monotonic function of the positive templates,

Nonnegative Matrices

If only applies, so additional requirements must be imposed on the matrix:

For an irreducible, non-negative matrix of spectral radius is a positive, simple eigenvalue of the matrix and there is made ​​a positive eigenvector with the spectral radius depends monotonically from starting.

However, this sentence does not preclude the possibility that distinct eigenvalues ​​may exist with the amount.

Example

Consider the non-negative matrices

The matrix has the double eigenvalue, being reducible and the intrinsic value since the block is cyclically. Also, in the matrix is ​​an intrinsic value, there are two more complex eigenvalues ​​having the same amount, as is also cyclic. Until greater than the amount of one of the other eigenvalues. And for the most part of the eigenvalue 3 positive eigenvector.

Applications

The importance of sentences based on the fact that one can consider the key requirements positivity or non-negativity directly and their statements are important for the convergence of the power method and the convergence to the limit state in Markov chains.

In particular, the separation of the eigenvalue sums is important for the convergence, which is fully applicable only in case of positive matrices. Therefore, the PageRank algorithm of Google with the damping factor instead of pure link matrix is a positive matrix used.