3
$\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?

$\endgroup$
  • $\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 Mar 25 '15 at 22:02
  • 1
    $\begingroup$ I presume he meant irreducible non-negative matrices. $\endgroup$ – Ramprasad Mar 26 '15 at 9:43
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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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