1
$\begingroup$

On this site I found a modified version of Perron Frobenius Theorem

Perron-Frobenius Theorem: If M is a positive, column stochastic matrix, then:

1 is an eigenvalue of multiplicity one.

1 is the largest eigenvalue: all the other eigenvalues have absolute value smaller than 1.

the eigenvectors corresponding to the eigenvalue 1 have either only positive entries or only negative entries. In particular, for the eigenvalue 1 there exists a unique eigenvector with the sum of its entries equal to 1.

In this same site, in Disconnected components section there is a matrix

$$ \begin{matrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1/2 & 1/2 \\ 0 & 0 & 1/2 & 0 & 1/2 \\ 0 & 0 & 1/2 & 1/2 & 0 \\ \end{matrix} $$

This matrix satisfies the conditions therefore for the eigenvalue 1 there exists a unique eigenvector with the sum of its entries equal to 1.

but at least exists two vectors

$u = (1/2,1/2,0,0,0)$

$v = (0,0,1/3,1/3,1/3)$

what happened? Is modified theorem incorrect?

Thank you!

$\endgroup$
2
$\begingroup$

The $5\times5$ matrix is not positive. It has zero entries.

Remark. And that was probably the reason why Brin et al. introduced the so-called damping factor in their PageRank paper. Without the damping factor, their matrix is merely nonnegative and it might not possess a unique nonnegative eigenvector, i.e. the ranking is not unique. However, by introducing the damping factor (i.e. by considering a convex combination of their matrix with an all-one matrix), the matrix becomes positive and there is now a unique positive eigenvector (and thus a unique ranking).

$\endgroup$
1
  • 1
    $\begingroup$ You could, however, apply the theorem to non-negative matrices that satisfy additional criteria. For instance, a unique eigenvector will exist if the matrix is irreducible and aperiodic (i.e. if the associated Markov chain is ergodic ) $\endgroup$ – Ben Grossmann Nov 27 '18 at 5:17

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.