# Rate of convergence for the Perron–Frobenius theorem

The Perron–Frobenius Theorem states the following.

Let $A = (a_{ij})$ be an $n \times n$ irreducible, non-negative matrix ($a_{ij} \geq 0, \forall i,j: 1\leq i,j \leq n$). Then the following statements are true.

• $A$ has a real eigenvalue $c \geq 0$ such that $c > |c'|$ for all other eigenvalues $c'$.
• There is an eigenvector $v$ with non-negative real components corresponding to the largest eigenvalue $c: Av = cv, v_i \ge 0, 1 \leq i \leq n$, and $v$ is unique up to multiplication by a constant.
• If the largest eigenvalue $c$ is equal to $1$, then for any starting vector $x^{\langle 0\rangle} \neq 0$ with non-negative components, the sequence of vectors $A^k x^{\langle 0\rangle}$ converge to a vector in the direction of $v$ as $k \rightarrow \infty$.

But the theorem does not say how fast the sequence of vectors $A^k x^{\langle 0\rangle}$ will converge. Are there any known results on the rate of convergence? What are some good, polynomial-time algorithms to compute this limiting vector?

• The theorem as stated is not correct. Consider for example $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$, which has $c = 1$ and an eigenvalue $-1$. Another bad example is $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$, where again $c = 1$ but the eigenvalue appears twice. – Yuval Filmus Mar 25 '15 at 22:02
• I presume he meant irreducible non-negative matrices. – Ramprasad Mar 26 '15 at 9:43