The inimitable
quip-fuckin'-master forced a
comment which is worth expanding a little more.
Ever since I found that the PageRank vector of the web-graph is the dominant eigenvector of its matrix representation, I have been meaning to get to the bottom of this eigenvector-eigenvalue concept. I am still snorkeling; long time to scuba dive.
Most of us studied concepts like simultaneous equations in our high school algebra classes, but never really wondered about them deeply, or even more so, felt that they were difficult. Problems like - 3 oranges and 4 apples cost 17 rupees; 2 oranges and 3 apples cost 12 rupees; how much does each apple cost? - never seemed that difficult. We knew that the equations that represented these statements were 'fluid,' and need not apply to just these statements, and an overall tool was being mastered.
Somehow, the same never happened to tools like primal-dual, or eigenvalues-eigenvectors, or other tools from linear algebra, statistics, calculus, etc. Somewhere, the learning process got fucked because of an emphasis on just the concept, and a palpable lack of intuitive visualization. When people talk about a matrix, I never think in terms of transformations. If I did, I could see that some transformations would leave some 'victims' unchanged. And these victims were the eigenvectors of that transformation. Maybe they could change in terms of scale, but not in terms of what they fundamentally are. Here is an example from the
Wikipedia entry on Eigenvalue:
As the Earth rotates, every arrow pointing outward from the center of the Earth also rotates, except those arrows that lie on the axis of rotation. Consider the transformation of the Earth after one hour of rotation: An arrow from the center of the Earth to the Geographic South Pole would be an eigenvector of this transformation, but an arrow from the center of the Earth to anywhere on the equator would not be an eigenvector. Since the arrow pointing at the pole is not stretched by the rotation of the Earth, its eigenvalue is 1.
So, was Neo an Eigenvector of The Matrix? I wonder...
As for what it means when
they say that PageRank is the dominant eigenvector of the web-graph, we have to visualize the web-graph's matrix representation as a transformation. The matrix representation has all web-pages in rows and columns, and if a web-page in row
i has a hyperlink to a web-page in column
j, the
[i, j] entry is 1, else 0. What does it mean to say that this matrix is a transformation? And what does it mean to say that it can act on 'victims' to change them? And if the 'victim' happens to be a vector which has the pages' pagerank values, the transformation doesn't affect it. What does that say about PageRank, and how is that related to our intuitive perception of pagerank as the importance of each page on a global scale?
We will get to primal-dual some other time. My head hurts. It hurts.
ps: And these are all just tools; albeit mental in nature. If we don't master them, well, it's ok I guess. We can always go back to intellectual stone age, or whatever was there before that. I mean, I always fancied myself as a Cro-Magnon.
Labels: computer science