Perron Frobenius Theorem modified

659 Views Asked by At

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!

1

There are 1 best solutions below

1
On BEST ANSWER

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).