# Why does this Matrix not converge with the Power Method?

Assume a $$Page-Rank$$ $$\textit{Markov}$$ Matrix:

$$M = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \frac{1}{2} & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 & \frac{1}{3}\\ 0 & \frac{1}{2} & 0 & 0 & \frac{1}{2} & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{3}\\ \frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0\\ 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & \frac{1}{3}\\ 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 \end{bmatrix}$$

My lecturer told me, that the convergence rate of the Power Method is defined by $$\frac{|\lambda_2|}{|\lambda_1|}$$ (dividing the absolute value of the second largest Eigenvalue by the largest Eigenvalue) - but $$\textbf{only}$$ if $$\lambda_1$$ is real and if $$\lambda_1$$ has algebraic multiplicity of 1!

numpy said, $$M$$ has these Eigenvalues:

$$\lambda_1 = 1 + 0i\\ \lambda_2 = -0.49999999999999967 + 0.866025403784438i\\ \lambda_3 = -0.49999999999999967 - 0.866025403784438i\\ \lambda_4 = -1.3877787807814457 \cdot 10^{-17} + 0.33816678863999095i\\ \lambda_5 = -1.3877787807814457 \cdot 10^{-17} - 0.33816678863999095i\\ \lambda_6 = -0.6036197287523702 + 0i\\ \lambda_7 = 0.6036197287523702 + 0i\\ \lambda_8 = -0.5 + 0i\\ \lambda_9 = 0.5 + 0i$$

So the absolute value of $$(-0.49999999999999967 + 0.866025403784438i)$$ is $$0.9999978$$, therefore I would consider this as $$\lambda_2$$ with $$\lambda_1 = 1$$. So convergence rate would be $$\frac{0.9999978}{1} = 0.9999978$$. If I try to solve this with my implementation of the Power Method it does not convergence (only like 4 or 5 steps).

Am I right with my calcuation of the convergence rate?

• There are numerical errors here (note: the imaginary part is only to 4 d.p., so why calculate the magnitude to 7 d.p.?). The eigenvalues are actually $\frac12(-1\pm\sqrt{-3})$, as there is a deterministic period 3 orbit $3\to 4\to 8\to 3$. Jun 5, 2019 at 16:33
• I updated my post and added all eigenvalues with all digits (which numpy computes for me). I can't really follow with deterministic period 3 oribt. How did you get to $\frac{1}{2}(-1 +/- \sqrt{-3})$? Jun 5, 2019 at 17:08
• Your $M$ (or rather, should be $M^T$ in the usual Markov chain setup) is the transition probabilities of a Markov chain. A deterministic period-$n$ orbit tells you if you assign mass $\zeta^j$ on the $j$-th point of the orbit (and $0$ outside the orbit), then the effect of the transition matrix is to multiply by $\zeta$ ($\zeta^n=1$), i.e., you have the eigenvalue $\zeta$ and the corresponding eigenvector of your matrix. Jun 5, 2019 at 17:33
• So you are basically telling me, the eigenvalues calculated by numpy.eig are wrong because instead they are multiples of $\frac{1}{2}(-1 +/- \sqrt{-3})$? Jun 5, 2019 at 18:26
• @binaryBigInt It does not hold because the matrix does not have a dominant eigenvalue. Jun 6, 2019 at 9:27

In fact, that matrix does not have a dominant eigenvalue. You have that $$|\lambda_1| = |\lambda_2|=|\lambda_3| =1$$ and so there is no reason why the method should converge, unless you take as initial approximation an eigenvector associated with $$\lambda_1$$. The exact values for $$\lambda_2, \lambda_3$$ are $$-\frac 12 \pm \frac{\sqrt{3}}{2}$$.