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$
    – user10354138
    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$
    – binaryBigInt
    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$
    – user10354138
    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$
    – binaryBigInt
    Jun 5, 2019 at 18:26
  • 1
    $\begingroup$ @binaryBigInt It does not hold because the matrix does not have a dominant eigenvalue. $\endgroup$
    – PierreCarre
    Jun 6, 2019 at 9:27

1 Answer 1

Reset to default
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$
    – ryanwebjackson
    Nov 24, 2021 at 19:35

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.