Back in 2021, when I was a second-year undergraduate and a member of the physics club at VNU University of Science, I stumbled upon a paper that changed the way I thought about linear algebra. It was titled "The $25,000,000,000 Eigenvector" by Kurt Bryan and Tanya Leise, published in SIAM Review. I presented it during a small club seminar, fumbling through the proofs on a whiteboard in a borrowed classroom. What captivated me then — and still does four years later — was one deceptively simple idea: that one of the most valuable technology companies ever built owed its existence to a single eigenvector problem. Not machine learning. Not deep neural networks. Just a matrix, an eigenvalue of one, and a convergent iteration. This post is my attempt to retell that story, with a bit more mathematical maturity and a physicist's eye for structure.
1. The Democracy of the Web
Before Google, search engines were, frankly, terrible. They ranked pages primarily by keyword density — how many times a search term appeared on a page, perhaps weighted by its position in headings or metadata. This approach was trivially easy to game. Stuff a page with invisible text repeating "cheap flights" a thousand times, and you would climb to the top of the results. The web of the late 1990s was drowning in spam, and no one had a principled way to separate signal from noise.
Larry Page and Sergey Brin's insight was disarmingly elegant: treat every hyperlink as a vote. If page \(A\) links to page \(B\), that link is an endorsement — a declaration that \(B\) has something worth reading. But not all votes are equal. A link from a highly cited, authoritative page should carry more weight than a link from a forgotten corner of the web. The New York Times pointing to your blog means more than a random spam page doing the same.
This sounds natural enough, but it immediately creates a circular definition. The importance of a page depends on the importance of pages that link to it, which in turn depend on the importance of pages that link to them, and so on forever. The question is: can we resolve this circularity? Can we assign a single, self-consistent importance score to every page on the web?
The answer, it turns out, is an eigenvector.
2. Building the Link Matrix
Let us make the problem concrete. Model the web as a directed graph: each page is a node, and each hyperlink is a directed edge from the linking page to the linked page. Suppose there are \(n\) pages in total. If page \(j\) contains \(n_j\) outgoing links, and one of them points to page \(k\), then page \(j\) contributes a fraction \(1/n_j\) of its importance to page \(k\). This is the "equal sharing" rule — a page distributes its vote evenly among all the pages it links to.
Write \(x_k\) for the importance score of page \(k\), and let \(L_k\) denote the set of pages that link to page \(k\). The self-consistency condition becomes:
This is a system of \(n\) linear equations in \(n\) unknowns. Define the \(n \times n\) matrix \(\mathbf{A}\) by
$$A_{ij} = \begin{cases} 1/n_j & \text{if page } j \text{ links to page } i, \\ 0 & \text{otherwise.} \end{cases}$$Then the entire system collapses to a single matrix equation:
This is the equation \(\mathbf{A}\mathbf{x} = \lambda \mathbf{x}\) with \(\lambda = 1\). The importance vector \(\mathbf{x}\) is literally an eigenvector of the link matrix \(\mathbf{A}\) corresponding to eigenvalue 1.
Bryan and Leise illustrate this with a miniature web of four pages. The link structure gives rise to the matrix:
$$\mathbf{A} = \begin{bmatrix} 0 & 0 & 0 & 1/2 \\ 1/3 & 0 & 0 & 0 \\ 1/3 & 1/2 & 0 & 1/2 \\ 1/3 & 1/2 & 1 & 0 \end{bmatrix}$$Solving \(\mathbf{A}\mathbf{x} = \mathbf{x}\), one obtains (up to normalization) \(\mathbf{x} = [12,\, 4,\, 9,\, 6]^T\). Page 1 is the most important — not because it has the most content, but because the link structure funnels the most "authority" toward it. The ranking emerges entirely from topology, not from anything written on the pages themselves.
3. Two Shortcomings of the Naive Approach
The formulation above is beautiful in its simplicity, but it breaks in two important ways when applied to the real web.
The real web is not a single connected graph. It consists of many clusters — "islands" — with no links between them. When the link graph is disconnected, the matrix \(\mathbf{A}\) takes a block diagonal form, and the eigenspace associated with \(\lambda = 1\) can have dimension greater than one. Multiple linearly independent eigenvectors mean there is no unique ranking: you cannot compare pages on different islands because there is no common frame of reference. It is like trying to rank football teams that have never played each other, not even indirectly.
A dangling node is a page with no outgoing links — a dead end. This could be a PDF, an image, or simply a page whose author never bothered to link anywhere. In our matrix, a dangling node produces a column of all zeros, because it distributes no importance at all. This means the column sums of \(\mathbf{A}\) are no longer all equal to 1 — the matrix is not column-stochastic. Without column-stochasticity, the eigenvalue 1 may not even exist, and the probabilistic interpretation collapses.
Both problems are structural: they arise not from errors in the data, but from the inherent topology of hyperlinked documents. Solving them requires modifying the matrix itself.
4. Google's Fix — The Modified Matrix M
Google's solution is one of those ideas so clean that it seems obvious in retrospect, yet it took genuine insight to propose. First, handle dangling nodes by replacing every all-zero column with the uniform vector \(1/n\) — effectively saying that a surfer who hits a dead end teleports randomly to any page on the web. Call the resulting matrix \(\hat{\mathbf{A}}\). Then blend \(\hat{\mathbf{A}}\) with a uniform "teleportation" matrix \(\mathbf{S}\), where every entry of \(\mathbf{S}\) is \(1/n\):
The parameter \(m\) is called the damping factor (or teleportation probability). Its interpretation comes from the random surfer model: imagine a bored person clicking through the web. At each step, with probability \((1-m)\) they follow a randomly chosen link on the current page. With probability \(m\), they get bored and jump to a completely random page — any page on the entire web, with equal likelihood. The value \(m = 0.15\) was the one Google originally used, meaning the surfer follows links 85% of the time and teleports 15% of the time.
This simple modification has profound consequences for the matrix \(\mathbf{M}\):
- Every entry of \(\mathbf{M}\) is strictly positive (since the \(m\mathbf{S}\) term contributes \(m/n > 0\) to each entry).
- \(\mathbf{M}\) is column-stochastic: each column sums to 1.
- The eigenspace \(V_1(\mathbf{M})\) is guaranteed to be one-dimensional — there is a unique ranking.
The guarantee that the ranking is unique comes from the Perron-Frobenius theorem: a square matrix with all entries strictly positive has a unique largest eigenvalue, and the corresponding eigenvector can be chosen to have all entries positive. Since \(\mathbf{M}\) is both positive and column-stochastic, its largest eigenvalue is exactly 1, and the corresponding eigenvector — the PageRank vector — is unique and has all positive entries. No ambiguity, no degeneracy, no multiple solutions. This is one of the most elegant applications of Perron-Frobenius in all of applied mathematics.
Bryan, K. & Leise, T. (2006). "The $25,000,000,000 Eigenvector: The Linear Algebra Behind Google." SIAM Review, 48(3), 569–581. DOI: 10.1137/050623280
Brin, S. & Page, L. (1998). "The anatomy of a large-scale hypertextual web search engine." Computer Networks and ISDN Systems, 30(1–7), 107–117.
5. Why \(V_1(\mathbf{M})\) Is One-Dimensional — The Math
The claim that the PageRank vector is unique rests on three results that Bryan and Leise present with admirable clarity. Here they are, distilled to their essential content.
Proposition 1 — Every Column-Stochastic Matrix Has Eigenvalue 1
If every column of \(\mathbf{M}\) sums to 1, let \(\mathbf{e} = [1, 1, \ldots, 1]^T\). Then \(\mathbf{M}^T \mathbf{e} = \mathbf{e}\), because the row sums of \(\mathbf{M}^T\) are the column sums of \(\mathbf{M}\). So \(\lambda = 1\) is an eigenvalue of \(\mathbf{M}^T\), and since a matrix and its transpose share the same eigenvalues, \(\lambda = 1\) is also an eigenvalue of \(\mathbf{M}\). The eigenvector exists — the question is whether it is unique.
Proposition 2 — Positivity Forces Uniform Sign
Suppose \(\mathbf{M}\) has all entries strictly positive and is column-stochastic. If \(\mathbf{q}\) is an eigenvector with \(\mathbf{M}\mathbf{q} = \mathbf{q}\), then all entries of \(\mathbf{q}\) must have the same sign. The proof uses the triangle inequality: take \(\|\mathbf{q}\|_1 = \sum |q_i|\), and observe that \(\|\mathbf{M}\mathbf{q}\|_1 \leq \|\mathbf{q}\|_1\) for any column-stochastic matrix. But if \(\mathbf{q}\) has entries of mixed sign and \(\mathbf{M}\) is strictly positive, the inequality becomes strict — a contradiction with \(\mathbf{M}\mathbf{q} = \mathbf{q}\). Therefore no mixed-sign eigenvector can exist in \(V_1(\mathbf{M})\).
Lemma — The Eigenspace Is One-Dimensional
Suppose for contradiction that \(\dim(V_1(\mathbf{M})) \geq 2\). Then there exist two linearly independent eigenvectors \(\mathbf{q}_1\) and \(\mathbf{q}_2\), both with all entries of the same sign (by Proposition 2). We may assume both are positive. But then the combination \(\mathbf{q}_1 - c\,\mathbf{q}_2\) for a suitable scalar \(c > 0\) produces an eigenvector with at least one zero entry and entries of mixed sign — contradicting Proposition 2. Therefore \(\dim(V_1(\mathbf{M})) = 1\), and the PageRank vector is unique up to normalization.
Three short arguments, each building on the last, and together they lock down the entire theoretical foundation of PageRank. The beauty of this chain is its economy — no heavy functional analysis, no spectral theory beyond the basics, just careful reasoning with inequalities and linear independence.
6. Computing PageRank — The Power Method
Knowing that a unique eigenvector exists is one thing. Computing it for a web of billions of pages is another entirely. As of 2024, Google indexes roughly 8 billion pages. The matrix \(\mathbf{M}\) is therefore \(8 \times 10^9 \times 8 \times 10^9\) — far too large to diagonalize, decompose, or even store as a dense matrix. Direct eigenvalue solvers are out of the question.
The method Google used (and, in spirit, still uses) is the power method — arguably the simplest iterative algorithm in all of numerical linear algebra. Start with any initial vector \(\mathbf{x}_0\) (say, the uniform distribution \(x_0^{(i)} = 1/n\)) and repeatedly multiply by the matrix:
Under the conditions satisfied by \(\mathbf{M}\) — positive, column-stochastic, with a dominant eigenvalue of 1 — the iterates \(\mathbf{x}_k\) converge to the unique eigenvector \(\mathbf{q}\). The convergence rate is governed by the ratio of the second-largest eigenvalue to the largest. For the Google matrix, this can be bounded:
With \(m = 0.15\), the error shrinks by a factor of at least 0.85 per iteration. After 50 iterations, the error is reduced by a factor of \(0.85^{50} \approx 3 \times 10^{-4}\). After 100 iterations, it is below \(10^{-7}\). For a web-scale computation, 50–100 iterations is remarkably cheap.
But there is a crucial computational trick. Naively multiplying \(\mathbf{M}\mathbf{x}\) for a dense \(n \times n\) matrix costs \(O(n^2)\) operations — impossibly expensive when \(n\) is in the billions. The key observation is that \(\mathbf{M}\) is not actually stored as a dense matrix. Instead, the multiplication is decomposed:
where \(\mathbf{s} = [1/n, \ldots, 1/n]^T\) is just a constant vector. The matrix \(\hat{\mathbf{A}}\) is sparse — each column has only as many nonzero entries as the corresponding page has outgoing links, typically a few dozen. So the product \(\hat{\mathbf{A}}\mathbf{x}\) costs only \(O(\text{number of links})\) operations, not \(O(n^2)\). The dense \(m\mathbf{S}\mathbf{x}\) term reduces to the scalar \(m/n\) added to every entry. Each iteration is linear in the number of hyperlinks, which is entirely feasible even for billions of pages.
To see the convergence in action, Bryan and Leise work through a 5-page example network. Starting from the uniform distribution, the iterates stabilize within about 60 steps to four decimal places:
| Iteration | Page 1 | Page 2 | Page 3 | Page 4 | Page 5 |
|---|---|---|---|---|---|
| \(k=0\) | 0.2000 | 0.2000 | 0.2000 | 0.2000 | 0.2000 |
| \(k=1\) | 0.2300 | 0.1700 | 0.1700 | 0.2300 | 0.2000 |
| \(k=10\) | 0.2015 | 0.1802 | 0.1260 | 0.2878 | 0.2045 |
| \(k=\infty\) | 0.2018 | 0.1799 | 0.1266 | 0.2873 | 0.2044 |
Page 4 wins — it accumulates the most authority from the network topology. And the convergence is rapid, exactly as the bound predicts.
7. The Probabilistic Interpretation
There is a second, equally illuminating way to read the PageRank equation. The vector \(\mathbf{q}\) is not just an eigenvector — it is the stationary distribution of a Markov chain.
Think of the random surfer as a particle hopping between states (pages) according to the transition probabilities encoded in \(\mathbf{M}\). The entry \(q_j\) gives the long-run fraction of time the surfer spends on page \(j\). No matter where the surfer starts, after enough steps the probability of being on page \(j\) converges to \(q_j\). The system "forgets" its initial condition.
To a physicist, this is immediately familiar. The convergence of the random surfer to a stationary distribution is exactly analogous to a thermodynamic system relaxing to equilibrium. The pages are microstates. The links define the transition rates. The teleportation term plays the role of a heat bath, ensuring ergodicity — that the system can reach any state from any other state. And the stationary distribution \(\mathbf{q}\) is the equilibrium distribution, the one that maximizes an appropriate entropy. The power method is the system evolving in time until memory of its initial configuration has been erased. In statistical mechanics, we call this mixing. In Markov chain theory, the same concept goes by the name of ergodicity.
This dual identity — algebraic (eigenvector) and probabilistic (stationary distribution) — is what gives PageRank its power. The algebraic formulation yields rigorous uniqueness guarantees. The probabilistic formulation provides intuition and suggests computational methods. Together, they form a complete picture.
8. Connections and Extensions
PageRank vs. Sports Rankings
The idea of ranking competitors via eigenvectors predates Google by decades. James Keener (1993) proposed a method for ranking American football teams based on head-to-head scores: construct a matrix \(\mathbf{A}\) from game results, find its dominant eigenvector, and use it as the ranking. The mathematical structure is identical — \(\mathbf{A}\mathbf{x} = \lambda\mathbf{x}\) — only the semantics of the matrix entries change. Links become game outcomes. PageRank and sports ranking are two instances of the same underlying mathematical problem.
The Markov Chain Perspective
PageRank is, at its core, an application of Markov chain theory. The Google matrix \(\mathbf{M}\) defines an irreducible, aperiodic Markov chain on the state space of web pages. The Perron-Frobenius theorem guarantees a unique stationary distribution. The power method computes it. Every theorem about mixing times, convergence rates, and spectral gaps from the theory of finite Markov chains applies directly. This connection has inspired a rich body of work on "personalized PageRank," where the teleportation distribution is non-uniform, and on "topic-sensitive PageRank," where different surfer profiles produce different rankings.
Beyond PageRank
Modern Google search relies on far more than PageRank alone. The introduction of machine learning models — RankBrain (2015), BERT (2019), and more recently the MUM and Gemini architectures — means that relevance scoring now incorporates natural language understanding, user intent modeling, and real-time signals. But PageRank remains foundational: it solved the problem of measuring authority independently of content, and that distinction is still a pillar of information retrieval. The eigenvector might be one signal among hundreds today, but it was the signal that made web search work.
9. Closing Reflection
When I first presented this paper in 2021, I was drawn to it for a reason I could not fully articulate. Something about the gap between the simplicity of the mathematics and the enormity of its consequences felt important — almost like a parable. A company worth tens of billions of dollars, a product used by billions of people, and at its origin, a system of linear equations and an eigenvalue of one.
Four years later, having spent time with density functional theory, neural network potentials, and the Hamiltonian eigenvalue problems that run through quantum mechanics, I recognize the deeper pattern. Linear algebra is not a toolbox. It is the grammar of structured relationships — between particles, between web pages, between anything that interacts in a network. The eigenvector does not "solve" Google's ranking problem any more than the Schrödinger equation "solves" the hydrogen atom. Rather, it reveals that the problem has a structure, and that the structure implies a unique, elegant answer.
If you are a student encountering this for the first time, I encourage you to read the original paper by Bryan and Leise. It is freely available, beautifully written, and requires nothing beyond a first course in linear algebra. It is one of those rare papers that makes you feel like the authors are sitting across from you, explaining things over coffee. And it may just change how you think about the linear algebra course you are taking right now.
