Imagine you’re standing in the world’s largest library — billions of books, no catalog, no librarian. Someone hands you a scrap of paper with two words on it and says, “Find the most relevant book.” Where do you even begin?
That’s roughly the problem Google faced in 1998. And the answer they came up with wasn’t just clever engineering — it was a beautiful piece of mathematics called linear algebra, wrapped around an even more elegant idea about what it means for something to be important.
Let’s build it from the ground up.
The Web as a Graph
First, a quick mental model. Forget pages for a moment and think of the internet as a giant network of dots and arrows. Each dot is a webpage. Each arrow points from one page to another whenever there’s a hyperlink. If Wikipedia links to NASA’s homepage, there’s an arrow from Wikipedia to NASA.
This is exactly the kind of graph we explored in a previous article — but now we’re going to put numbers on it, and those numbers are going to do something remarkable.
The key insight of Google’s founders, Larry Page and Sergey Brin, was this: a link is a vote of confidence. If a page links to you, it’s saying, in some sense, “this other page is worth visiting.” And a vote from an important page should count more than a vote from a nobody page.
That’s circular, of course — importance depends on who links to you, and who links to you depends on importance. But mathematics has a wonderful way of handling circular definitions: it turns them into equations and then solves them.
Surfing at Random
Here’s the intuition that unlocks everything. Imagine a random web surfer — someone who starts on a random page and, at each step, picks one of the outgoing links at random and clicks it. They do this forever, bouncing around the web like a pinball.
Now ask: in the long run, what fraction of time does the surfer spend on each page?
Pages that many important pages link to will get visited more often. Pages that are dead ends, or only linked from obscure corners of the web, will be visited rarely. The fraction of time the surfer spends on a page is, in a very precise sense, that page’s importance score — and this score is exactly what Google calls PageRank.
The beautiful thing is that this “long-run fraction” question has a clean mathematical answer. It’s the solution to a linear algebra problem.
Matrices and the Magic of Eigenvectors
Let’s make this concrete with a tiny web — just four pages: A, B, C, and D.
Suppose the links are:
- A → B, A → C
- B → D
- C → A, C → B, C → D
- D → B
We can encode the entire web in a single table called a matrix. Each column represents a page that’s doing the linking. Each row represents a page being linked to. The entry in row i, column j is the probability that the surfer, currently on page j, will next move to page i.
Since the surfer picks links uniformly at random, each column’s entries sum to 1. Page A has two outgoing links (to B and C), so each gets probability 1/2. Page B has one outgoing link (to D), so D gets probability 1. And so on.
Our matrix M looks like this:
A B C D
A [ 0 0 1/3 0 ]
B [ 1/2 0 1/3 1 ]
C [ 1/2 0 0 0 ]
D [ 0 1 1/3 0 ]
Now here’s where linear algebra enters the room. If r is a vector representing the current probability distribution of where our surfer is (so r[A] is the probability they’re on page A right now), then after one click the new distribution is simply M × r.
After two clicks, it’s M × M × r = M² × r. After n clicks, it’s Mⁿ × r.
The claim — and this is a theorem, not a hand-wave — is that for well-behaved matrices, Mⁿ × r converges to the same vector no matter what r you start with. Our tiny raw matrix below is not quite well-behaved, because B and D form a closed two-cycle; the damping fix described later is what makes the PageRank calculation converge. When a limiting vector r* does exist, it satisfies:
M × r* = r*
In other words, multiplying by M doesn’t change it. r* is called an eigenvector of M with eigenvalue 1. The PageRank of each page is simply the corresponding entry in this eigenvector.
The word “eigenvector” sounds intimidating, but the idea is just this: it’s a special direction in space that a matrix leaves unchanged (or scales by a fixed factor). Here, the factor is 1 — the PageRank vector is so perfectly balanced that one step of random surfing leaves it exactly the same.
Worked Numbers: Finding PageRank
Let’s actually compute the PageRank for our four-page web. Rather than solving the eigenvector equation symbolically, we’ll use the power iteration method — the same approach Google originally used on a web with billions of pages.
Start: Give every page equal rank. With 4 pages, each starts at 1/4.
r = [0.25, 0.25, 0.25, 0.25] (for pages A, B, C, D)
Iteration 1: Multiply M × r.
- r[A] = 0×0.25 + 0×0.25 + (1/3)×0.25 + 0×0.25 = 0.083
- r[B] = (1/2)×0.25 + 0×0.25 + (1/3)×0.25 + 1×0.25 = 0.125 + 0 + 0.0833 + 0.25 = 0.458
- r[C] = (1/2)×0.25 + 0 + 0 + 0 = 0.125
- r[D] = 0 + 1×0.25 + (1/3)×0.25 + 0 = 0.25 + 0.0833 = 0.333
After just one iteration: r ≈ [0.083, 0.458, 0.125, 0.333].
Iteration 2: Multiply M × r again.
- r[A] = (1/3)×0.125 = 0.042
- r[B] = (1/2)×0.083 + (1/3)×0.125 + 1×0.333 = 0.042 + 0.042 + 0.333 = 0.417
- r[C] = (1/2)×0.083 = 0.042
- r[D] = 1×0.458 + (1/3)×0.125 = 0.458 + 0.042 = 0.500
After two iterations: r ≈ [0.042, 0.417, 0.042, 0.500].
If we keep going without damping, the numbers do not settle down. Probability drains out of A and C, then oscillates between B and D because B links only to D and D links only to B. Applying the standard damping factor d = 0.85 gives the final PageRank (approximately):
| Page | PageRank |
|---|---|
| A | 0.055 |
| B | 0.449 |
| C | 0.061 |
| D | 0.436 |
Pages B and D dominate. Why? Because B receives links from A, C, and D, while D receives a strong link from B and another from C. Page C, despite linking to three pages, is only linked to by A — so it stays obscure. The math captures exactly what our intuition says: the most central pages are the ones that receive support from other well-supported pages.
The Dangling Node Problem (And the Damping Fix)
Real webs have a problem: dangling nodes — pages with no outgoing links. If our surfer lands on one, they’re stuck. Mathematically, the column for that page is all zeros, which breaks our “columns sum to 1” guarantee. Closed cycles can also trap the surfer and prevent the raw power iteration from converging.
Page and Brin’s fix is elegant: when the surfer gets stuck (or just randomly, with some small probability), they teleport to a random page anywhere on the web. This is called the damping factor, typically set to d = 0.85.
The modified PageRank formula becomes:
r = (1 − d)/N + d × M × r
where N is the total number of pages. The first term, (1 − d)/N, is a tiny baseline probability of landing on any given page via teleportation. The second term is the normal link-following probability, scaled down by d.
This small tweak has a big mathematical consequence: it guarantees the matrix is now fully connected (every page can reach every other page in one step via teleportation), which guarantees a unique PageRank solution exists. The theorem that backs this up is called the Perron–Frobenius theorem, and it’s one of the workhorses of applied linear algebra.
Why This Scales to Billions of Pages
You might wonder: how do you find the eigenvector of a matrix with billions of rows and columns? That sounds impossible.
The key is that the web’s link matrix is sparse — each page links to only a tiny fraction of all other pages. A matrix with a billion rows and columns would have 10¹⁸ entries, but the actual number of links is only in the tens of billions. So almost every entry is zero, and you only need to store the non-zero ones.
Power iteration — the “keep multiplying by M” trick we used above — converges in roughly 50–100 iterations for the real web, and each iteration only touches the non-zero entries. Google’s original 1998 paper reported computing PageRank on a web of 322 million links in just a few hours on a cluster of workstations. The algorithm scaled because the math was clean.
The Usable Insight
Here’s what I want you to carry away from all this, even if the matrix arithmetic fades:
Importance is recursive. A page is important if important pages link to it. A paper is influential if influential papers cite it. A person is well-connected if well-connected people know them. Wherever you see this kind of circular definition, linear algebra has a tool for it: find the eigenvector. The eigenvector is the self-consistent answer — the unique ranking that doesn’t contradict itself.
This idea shows up far beyond search engines. Scientists use the same eigenvector centrality to find the most influential proteins in a biological network. Economists use it to rank industries by how much the rest of the economy depends on them. Sports analysts use it to rank teams when head-to-head records are circular (A beat B, B beat C, C beat A — who’s best?).
The next time you type something into a search bar and a ranked list appears in milliseconds, you’re seeing the legacy of that eigenvector idea — one foundational signal among many in modern search ranking. That’s not magic. That’s math — and now you know the core idea behind how it works.
Leave a Reply