` `

Perron Frobenius Theorem is a well-known algebra result that finds applications in a large span of fields of Mathematics. One can mention Markov chains, population growth (with the Leslie matrix model) or the famous PageRank algorithm. In this post we prove the Perron-Frobenius Theorem for stochastic matrices.

## Perron Frobenius Theorem

Let us consider some integer and a stochastic matrix, meaning that for all , . In the following, we will denote . We assume that is irreducible which means that Then the period of the point defined by does not depend on meaning that there exists some such that . Then:

- The spectral radius of is . Moreover, the eigenvalues of of modulus 1 are exactly the p p-th roots of unity and have algebraic multiplicity of 1.
- The spectrum of is invariant by rotation of angle .
- If , it exists a permutation matrix such that

## Proof.

#### Step 0 : Preliminaries

Let us recall that on a finite state space, an irreducible matrix has a unique invariant probability distribution .

**Claim 0.1: **

Let us assume that for some it holds . Since is a probability measure on a finite space, there exists some such that . Using that is invariant for we get directly that is also an invariant distribution of the matrix for any which means that

Considering the line number in the previous equality, we get that . But all terms in the previous sum are non-negative so they must be all equal to zero. In particular we have which leads to since . Hence, we proved that for all , which is in contradiction with the irreducibility of the matrix . This concludes the proof of Claim 0.1.

**Claim 0.2: Denoting , **** is an irreducible stochastic matrix**

Claim 0.2 follows from a direct computation using the fact that is an irreducible stochastic matrix.

#### Step 1 : Eigenspace associated with the eigenvalue 1

Let us denote . It is a eigenvector of related to the eigenvalue 1.

**Claim 1.1: The spectral radius of is 1.**

Let us denote an (complex) eigenvalue of with the largest modulus and an non-zero associated eigenvector. Let . Since , taking the module and using the triangle inequality gives

where the last inequality comes from the fact that is a stochastic matrix. By definition of and since , we have that and the previous inequality leads to . Since 1 is an eigenvalue of , we deduce that the spectral radius of is 1.

**Claim 1.2: For two vectors , we write to state that for all . Then, for any such that and , it holds that and there exists some such that .**

Let us consider . Then for any , we have

where the first equality comes from the irreducibility of , the second inequality comes from the definition of and the fact that and the last is obtained by taking the i-th line in the assumption . We deduce that all the above inqualities are actually equalities which implies that for any such that , it holds . This result is true for any and since for nay there exists some such that , we deduce that

Hence we proved that with and .

**Claim 1.3: If is a complex eigenvector realted to an eigenvalue of modulus 1 of , then is an nonnegative eigenvector related to the eigenvalue 1. This implies that the eigenspace related to 1 is .**

For all , . Hence, taking the modulus in the previous inequality and using the triangle inequality leads to i.e. Using Claim 1.2, we deduce that and that , which concludes the proof.

#### Step 2 : Algebraic multiplicity of the eigenvalue 1

In the following, we will denote the caracteristic polynomial of the matrix and the conjugate of the comatrice of . Claim 2.1 is a classical result of differential calculus.

**Claim 2.1: .**

**Claim 2.2: Every column of belongs to .**

From Step 1, we know that has rank . Hence and we get that

This means that the subspace spanned by the columns of is included in the nullspace of which is . Hence, each columns of belongs to .

**Claim 2.3: Every line of is proportional to .**

From Step 0, we know that is an irreducible stochastic matrix and we deduce that this is also the case for . Hence, remarking that Claim 2.2 holds for any irreducible stochastic matrix, we get that every column of is proportional to , meaning that for all , there exists some such that for all where we have denote the cofactor application related to line and column . Hence, for all

Hence we proved that for all , . We deduce that each line of is proportional to

**Claim 2.4: All entries of are non-zero and share the same sign.**

From Step 1, the rank of the matrix is 1 and thus the dimension of its nullspace is . We deduce that there exists a submatrix from with size which is invertible. This implies that the matrix has at least one non-zero coefficient and we note its location. From Claim 2.2, we deduce that all the entries of the j-th column of are non-zero (and have the same sign since they are equal). Then, using Claim 2.3 together with the fact that from Step 0, we get the Claim 2.4.

**Conclusion**

From Claims 2.1 and 2.4, we have . This proves that is a root with multiplicity of the caracteristic polynomial of .

#### Step 3 : The other eigenvalues of modulus 1

We consider an eigenvector (complex) related to an eigenvalue with modulus 1 of Using Claim 1.2, we can immediately that is independent of and thus we can consider without loss of generality that .

**Claim 3.1: If then .**

Since , taking the modulus and using the triangle inequality gives . From Claim 1.2, we get that there exists some such that .

**Claim 3.2: If then .**

Let us consider some . Taking the modulus in leads to

where we used Claim 3.1 and the fact that is a stochastic matrix. We deduce that all inequalities in are equalities and the equality condition in the triangle inequality gives that the such that are positively colinear. From Claim 3.1, we get that such that are equal to some . Hence,

Hence for any such that , it holds .

**Claim 3.3: is a p-th root of unity.**

Let us consider such that . For all , since , Claim 3.2 gives and since (see Claim 3.1), we have that . Hence is an integer and divides . We deduce that divides meaning that there exists some such that . We have found that is a p-th root of unity.

**Conversely, let us consider a p-th root of unity. We define the vector by and if .**

**Claim 3.4: The vector is well-defined and is an eigenvector associated with the eigenvalue .**

We first show that is well-defined. Let us consider some . By irreducibility of the matrix , there exists some such that . Then, for all such that , we have

Hence, divides . Since is a p-th root of unity, we deduce that for any such and , we have

Hence, the vector is well-defined.

For all , we consider some integer such that . One can easily remark that for all , if then since

Hence, for all ,

(1)

From here, we get that for all ,Hence we proved that meaning that is an eigenvector of for the eigenvalue .

**Claim 3.5: Let be the diagonal matrix with diagonal coefficients . It holds . This gives that the eigenvalues associated with the p-th roots of unity of have algebraic multiplicity and the spectrum of is invariant under rotation of angle .**

(2)

\eqref{claim35} clearly holds if . Hence we consider such that . From \eqref{claim34}, we have and \eqref{claim35} is satisfied.Now we prove that all p-th roots of unity are eigenvalues of with multiplicity 1. Let us consider some p-th root of unity . Denoting for any the cofactor of some matrix at location , one can easily check that

We deduce that

where we used the conclusion of Step 1 to state that . This shows that has multiplicity 1.

Let us consider some eigenvalue of . We set and the diagonal matrix with diagonal coefficients . Then,

where the last equality holds because is an eigenvalue of . This proves that the spectrum of is invariant under rotation of angle and concludes the proof of Claim 3.5.

### Extension of the Theorem

The **Kreinâ€“Rutman theorem** is a generalisation of the Perron-Frobenius theorem to infinite-dimensional Banach spaces and complex integral operators.