<p>See the power method for computing eigenvectors:
<a href="http://en.wikipedia.org/wiki/Power_iteration">http://en.wikipedia.org/wiki/Power_iteration</a></p>

<p>Convergence is exponential (geometric in the ratio of the top two eigenvalues).</p>

CC BY-SA 3.0
2015-03-25T21:28:57.763Z
2015-03-25T21:28:57.763Z
Aryeh
<p>The <a href="http://en.wikipedia.org/wiki/Perron-Frobenius_theorem" rel="nofollow">Perron–Frobenius Theorem</a> states the following.</p>

<p>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.</p>

<ul>
<li>$A$ has a real eigenvalue $c \geq 0$ such that $c &gt; |c'|$ for all other eigenvalues $c'$.</li>
<li>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.</li>
<li>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$.</li>
</ul>

<p>But the theorem does not say <strong><em>how fast</em></strong> 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?</p>

CC BY-SA 3.0
2015-03-25T22:02:41.237Z
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
CC BY-SA 3.0
2015-03-26T09:43:42.183Z
I presume he meant [irreducible](http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem#Non-negative_matrices) non-negative matrices.
Ramprasad
<ds.algorithms><linear-algebra><matrices>
Rate of convergence for the Perron–Frobenius theorem
Arindam Pal
# Rate of convergence for the Perron–Frobenius theorem

(Asked by: username_0 on 2015-03-25)

The [Perron–Frobenius Theorem](http://en.wikipedia.org/wiki/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?

**Tags:** ds.algorithms, linear-algebra, matrices

> **Comments:**
> **username_1**: 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.  
> **username_2**: I presume he meant [irreducible](http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem#Non-negative_matrices) non-negative matrices.  

---

## 1 answers

### Answer by username_3 on 2015-03-25. Score: 5

See the power method for computing eigenvectors:
<http://en.wikipedia.org/wiki/Power_iteration>

Convergence is exponential (geometric in the ratio of the top two eigenvalues).


---

