Why is PageRank an eigenvector problem?

Solution 1:

TL,DR: since the pagerank algorithm is an iterative application of the link matrix, the ultimate pagerank vector will look a lot like an eigenvector associated with the highest eigenvalue of the link matrix.

PageRank, in linear algebraic terms.

PageRank creates a vector of ranks: one element for each page; it also creates a matrix of links: each link from one page to another puts a '1' in the appropriate cell of the matrix.

Then, it takes that vector -- initially set to some default (though I don't know, and it doesn't terribly matter, how this default is set) -- and repeatedly applies the link matrix to it.

The power of eigenvectors

So... why is this an eigenvector problem?

One of the cool things that you can do with eigenvectors is Diagonalization of a matrix. Given the eigenvectors and eigenvalues of a matrix, you can create three matrices that when combined act the same way at the original... and the middle one handles all the scaling and is itself a diagonal matrix, with the eigenvalues of the matrix as its entries.

This then lets you do something amazing: exponentiating the original matrix is equivalent to exponentiating only the middle matrix of the diagonalized matrix trio. And exponentiating a diagonal matrix is equivalent to exponentiating only the entries on the diagonal.

Infinite power!

So back there we repeatedly applied the link matrix to the pagerank vector. This is equivalent to repeatedly multiplying the link matrix by itself, and then after enough self-multiplications, applying that result to the pagerank vector.

But repeated multiplication... is exponentiation. So we can do that by exponentiating the matrix, which we can do by exponentiating the diagonal matrix with the eigenvalues in it.

...but this is a really, really big exponent. Hopefully an infinite exponent, in fact. So the diagonal matrix comes to be dominated by the largest (original) eigenvalue, and so too does the ultimate link-following matrix come to be dominated by a vector associated with the largest eigenvalue, and so the ultimate pagerank vector will be dominated that vector too.