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

  • $\begingroup$ what does it mean for a matrix to converge? $\endgroup$ – Dan Rust Sep 14 '19 at 10:56
  • $\begingroup$ We can get the dominant eigenvalue of a square matrix if it is Diagonalizable and has s dominant eigenvalue by power method. If the matrix has a dominant eigenvalue then in power method the initial vector converges to a dominant eigenvector value. @DanRust $\endgroup$ – criticalmind Sep 14 '19 at 11:17

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?

  • $\begingroup$ Sir,my matrices are primitive but not positive,but some power of it is positive. I know my matrix is primitive and the Perron-Frobenius theorem is applicable here. I am working here with only the right eigenvector. I know that dominant eigenvalue is 1 and all other absolute value of eigenvalue is strictly less than 1 according to PF theorem. But I have seen in some blogs/books that a matrix should be diagonalizable for power method to work. I want to know whether it is true that only diagonalizable matrix converges? What about my matrix? @DanRust $\endgroup$ – criticalmind Sep 14 '19 at 11:44
  • $\begingroup$ Sorry yes, I forgot to mention you can be primitive also if some power is positive. The result that I mentioned is true in general, without assuming diagonalisability. $\endgroup$ – Dan Rust Sep 14 '19 at 12:46

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.