4
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Mar 25, 2015 at 22:02
  • 1
    $\begingroup$ I presume he meant irreducible non-negative matrices. $\endgroup$
    – Ramprasad
    Commented Mar 26, 2015 at 9:43

1 Answer 1

Reset to default
5
$\begingroup$

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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.