My matrices are non-negative,stochastic, irreducible and aperiodic, I want to know whether they always converge in power iteration.

142 Views Asked by At

I am working on a problem of SCC graph. The matrix representation of graph will be a square non-negative matrix that is column stochastic, irreducible. I will make it aperiodic by adding a self-loop on each node so that I can use the power method.
I will write a program of power method. Now I want to know whether my matrix always converges.
I know that diagonalizable matrix always converges. But if my matrix is not diagonalizable for some graph then will it converge? So what should I do if I want my matrix to converge always? Or my matrix's property(non-negative, stochastic, irreducible, aperiodic) is enough to converge always?
(My program will take input any SCC graph, I will add self-loop on each node. And write a program of power method. )

1

There are 1 best solutions below

2
On

Your matrices are primitive which means that every entry is a positive real number. In particular, it means that we may apply the Perron-Frobenius theorem, one consequence of which is that if $M$ is a primitive matrix with (dominant) PF-eigenvalue $\lambda$, and associated left- and right-PF eigenvectors $\textbf{l},\textbf{r}$, respectively (normalised so that $\mathbf{l}^T\mathbf{r} = 1$), and we have $$\lim_{n \to \infty}M^n/\lambda^n = \mathbf{r}\mathbf{l}^T.$$

Is that the kind of thing you were looking for?