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?
Best Answer
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}$.