1
$\begingroup$

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?

$\endgroup$
7
  • 1
    $\begingroup$ 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$. $\endgroup$ Jun 5, 2019 at 16:33
  • $\begingroup$ 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})$? $\endgroup$ Jun 5, 2019 at 17:08
  • $\begingroup$ 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. $\endgroup$ Jun 5, 2019 at 17:33
  • $\begingroup$ 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})$? $\endgroup$ Jun 5, 2019 at 18:26
  • 1
    $\begingroup$ @binaryBigInt It does not hold because the matrix does not have a dominant eigenvalue. $\endgroup$ Jun 6, 2019 at 9:27

1 Answer 1

3
$\begingroup$

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}$.

$\endgroup$
1
  • $\begingroup$ What does the last statement here mean? Do those values approximate to a magnitude of 1? $\endgroup$ Nov 24, 2021 at 19:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .