The Math Behind Google Search
In 1998, two Stanford PhD students published a paper describing a search engine called Google. Its central idea wasn't about reading pages better than rivals did. It was about ignoring what pages said about themselves and asking what the rest of the web said about them.
The math that made that work is linear algebra: a giant matrix and one special vector. In 2006, mathematicians Kurt Bryan and Tanya Leise published an explainer in SIAM Review titled "The $25,000,000,000 Eigenvector." The title was a nod to what Google was worth at the time.
Links Matter More Than Words
Early search engines ranked pages mainly by how often they contained your search terms. That was easy to game: stuff a page with "cheap flights" 500 times and it shot up the rankings.
Larry Page and Sergey Brin borrowed an idea from academic citation analysis. A paper cited by many important papers is probably important. So a web page linked to by many important pages is probably important too. Crucially, importance is recursive: a link counts for more when it comes from a page that is itself important.
That circular definition sounds like it can't be computed. Linear algebra says it can.
The Random Surfer
Imagine someone clicking links completely at random, forever. At each page they pick one of its outgoing links with equal probability. Some pages get visited more than others over time.
PageRank is the long-run fraction of time the surfer spends on each page. Mathematically, the surfer is a Markov chain, a process where the next step depends only on where you are now.
Here's a tiny web of four pages:
- A links to B and C
- B links to C
- C links to A
- D links to C
We build a transition matrix where entry (i, j) is the probability of moving from page j to page i:
A B C D
A [ 0 0 1 0 ]
B [ 1/2 0 0 0 ]
C [ 1/2 1 0 1 ]
D [ 0 0 0 0 ]
Each column sums to 1, since a surfer must go somewhere.
The Eigenvector
PageRank is the vector r that doesn't change when you apply the matrix:
M · r = r
That's the definition of an eigenvector with eigenvalue 1. For the tiny web above, the solution is approximately:
A = 0.40, B = 0.20, C = 0.40, D = 0
Page C receives three links, but A ties it, because A receives C's entire vote. D, which nobody links to, gets nothing. You can experiment with small versions of this using the matrix multiplication calculator.
The Damping Factor
The pure random surfer has problems. Pages with no outgoing links trap it, and closed loops can absorb all the probability. Brin and Page fixed this with a damping factor d, set to 0.85 in their paper:
PR(p) = (1 − d)/N + d × Σ PR(q) / L(q)
Where the sum runs over pages q linking to p, L(q) is the number of links on page q, and N is the total number of pages.
In plain English: 85% of the time the surfer follows a link, and 15% of the time they get bored and jump to a random page anywhere on the web. That small change guarantees a single, unique PageRank vector exists, thanks to the Perron–Frobenius theorem.
Computing It at Web Scale
You can't solve M · r = r by ordinary methods when M has billions of rows. Instead Google used the power method:
- Start with every page equal: r = (1/N, 1/N, …)
- Multiply: r ← M · r
- Repeat until r stops changing
With d = 0.85, the error shrinks by a factor of about 0.85 each round. After 50 iterations, it's down to about 0.85⁵⁰ ≈ 0.03% of where it started. Page and Brin reported that on a database of 322 million links, PageRank converged to reasonable tolerance in about 52 iterations.
Relevance: TF-IDF
PageRank tells you which pages are important. You still need to know which pages are relevant to a query. A classic tool for that is TF-IDF:
- Term frequency (TF): how often a word appears in a document
- Inverse document frequency (IDF): how rare the word is across all documents
IDF(word) = log(N / number of documents containing the word)
A word like "the" appears everywhere, so its IDF is close to log(1) = 0. A word like "eigenvector" is rare, so it scores highly. The logarithm keeps rare words from completely dominating. See how quickly logs flatten out with the logarithm calculator.
Modern Search
Today's Google uses hundreds of ranking signals and large neural language models to understand queries. PageRank is still part of that picture, though it's one signal among many. The core idea of treating the web as a mathematical object that can be analyzed as a whole remains the foundation.
Two Concepts Worth Knowing
Stochastic Matrix
A stochastic matrix has non-negative entries and columns (or rows) that each sum to 1. Every such matrix has an eigenvalue of 1, which is why a stationary distribution like PageRank exists.
Vector Space Model
In the vector space model, each document becomes a vector of TF-IDF weights, with one dimension per word. Relevance is measured by the cosine of the angle between the query vector and the document vector. You can compute cosines with the cosine calculator.
Quick Answer: How Does PageRank Work?
PageRank models a random surfer who follows links 85% of the time and jumps to a random page 15% of the time. A page's rank is the long-run probability of the surfer being on it, calculated as the principal eigenvector of the web's link matrix using repeated matrix multiplication.
Try Them Yourself
- Matrix Multiplication Calculator: run a few power-method steps by hand
- Matrix Transpose Calculator: flip rows and columns of a link matrix
- Logarithm Calculator: compute IDF weights
- Cosine Calculator: measure similarity between vectors
- Statistics Formulas: probability foundations for Markov chains
- Alan Turing and the Turing Machine: the roots of computation
Draw a web of five pages on paper, write out its link matrix, and multiply a starting vector by it a few times. You'll watch PageRank emerge by hand.