jaytsairenaker
commented
1 month ago Hi Ava! I'm going to take a swing at this question, this also stood out to me. Disclaimer: I used a combination of ChatGPT, this matrix problem set, and the Deeper Inside PageRank paper to think about this. I'm also still a little unclear on the exact line of causality through these concepts.
TLDR: According to Planet Math, if a matrix is non-negative, irreducible, and has a positive element on the main diagonal, then it is primitive.
1.) In the quiz definition of a primitive matrix, "a non-negative, irreducible matrix with only one eigenvalue in its spectral circle", our attention is drawn to the existence of a unique, greatest eigenvalue. This fact is important, but think of it as a step in the primitivity process, not the end-all-be-all reason why a matrix is primitive.
2.) In the paper, the authors write that "The irreducibility adjustment also insures that $\bar{ \bar P}$ is primitive, which implies that the power method will converge to the stationary PageRank vector $π^T$ ". Here, they emphasize that the irreducibility adjustment leads to primitivity.
2.1) Irreducible: On a graph, every node is reachable from every other node.
3.) If you adjust your matrix to be irreducible, ($ \bar P$ to $\bar{ \bar P}$), this guarantees that you will never be stuck in a cluster of only some nodes without eventually reaching all the nodes. Thus, all the nodes/states are part of one big happy family, instead of being separated into unreachable components.
4.) Then, the power method can be implemented, leading to convergence to a unique, stationary probability distribution. This distribution applies to the whole matrix, instead of one isolated component (hence the necessity of irreducibility).
4.1) Power method: an iterative algorithm that functions by repeatedly multiplying an initial vector, representing an initial guess for the stationary distribution, by the matrix $\bar{ \bar P}$
5.) To bring it back to the quiz definition, the speed at which the power method converges is affected by the difference between the 1st and 2nd greatest eigenvalues. The closer they are, the slower it converges. And if there are two equal highest values, it will never converge. That's why there must be a unique greatest eigenvalue. See the left photo for Prof. Izbicki's office hours depiction of this process.
6.) Hope that helped in getting at some of the concepts. Regarding your second question: if you just want to look at a matrix and determine primitivity, according to Planet Math a matrix that is non-negative, irreducible, and has a positive element on the main diagonal, is primitive.
7.) Bonus photo, I tried asking Dall-E to draw the power method and it had an interesting result
Hope this opens some conversation! I would love anyone else's input on these concepts, I'm still shaky on them.
Hi,
I had a question regarding the relationship between $\bar{P}$ & $\bar{\bar{P}}$ and irreducibility specifically related to Note 3 in PageRank Notes 1.
I understand that P is not stochastic, irreducible, nor primitive, and $\bar{P}$ is stochastic but not irreducible or primitive. I am a bit confused on how the "irreducibility adjustment" from $\bar{P}$ to $\bar{\bar{P}}$ ensures that $\bar{\bar{P}}$ is primitive. Is this just because if you were to solve for the eigenvalues you would get the PageRank vector as the greatest value? Are there other ways when looking at a matrix to know it will only have one top eigenvalue?
Thanks!