How Google PageRank Uses Linear Algebra

When Google appeared in 1998, its search results were dramatically better than its rivals', and the secret was a single idea from linear algebra. Larry Page and Sergey Brin, then PhD students at Stanford, treated the whole web as a giant matrix and ranked pages using its eigenvector. This article explains PageRank from first principles, with small examples you can calculate by hand.

The Idea: Links as Votes

Early search engines ranked pages mostly by how often your search words appeared, which was easy to cheat. Page and Brin's insight was that a link from one page to another is a kind of vote of confidence. But not all votes are equal:

• A link from an important page should count more than a link from an obscure one.
• A page that links to 100 others should pass on less to each than a page that links to just one.

This sounds circular, since a page's importance depends on the importance of pages linking to it, and that circularity is exactly what an eigenvector equation captures.

The Random Surfer Model

Imagine a surfer who starts on a random page and repeatedly clicks a random link on the current page. Over a long time, the fraction of time spent on each page settles down. PageRank is that long-run fraction. Pages that many routes lead to, especially from other popular pages, get visited more often.

Mathematically, the surfer is a Markov chain: where they go next depends only on where they are now.

Building the Link Matrix

Number the pages \( 1, 2, \ldots, n \). Define the matrix \( M \) by

$$ M_{ij} = \begin{cases} \dfrac{1}{L_j} & \text{if page } j \text{ links to page } i \\ 0 & \text{otherwise} \end{cases} $$

where \( L_j \) is the number of outgoing links on page \( j \). Each column sums to 1, so \( M \) is column-stochastic: column \( j \) lists the probabilities of moving from page \( j \) to each other page.

If \( \mathbf{r} \) holds the current probabilities of being on each page, then after one click they become \( M\mathbf{r} \). The long-run distribution satisfies

$$ M\mathbf{r} = \mathbf{r} $$

In other words, \( \mathbf{r} \) is an eigenvector of \( M \) with eigenvalue 1, scaled so its entries add to 1.

Worked Example 1: A Three-Page Web

Pages A, B, C have these links: A links to B and C; B links to C; C links to A.

Step 1. Build \( M \) (columns are "from", rows are "to"). A has 2 links, so B and C each get \( \tfrac12 \) from A. B has 1 link (to C). C has 1 link (to A):

$$ M = \begin{pmatrix} 0 & 0 & 1 \\ \tfrac12 & 0 & 0 \\ \tfrac12 & 1 & 0 \end{pmatrix} $$

Step 2. Write \( M\mathbf{r} = \mathbf{r} \) as equations, with \( \mathbf{r} = (a, b, c) \):

• \( a = c \)
• \( b = \tfrac12 a \)
• \( c = \tfrac12 a + b \)

Step 3. Solve. From the second equation \( b = \tfrac12 a \). Substituting into the third: \( c = \tfrac12 a + \tfrac12 a = a \), consistent with the first.

Step 4. Normalise. \( a + b + c = a + \tfrac12 a + a = 2.5a = 1 \), so \( a = 0.4 \).

$$ \mathbf{r} = (0.4,\ 0.2,\ 0.4) $$

Step 5. Interpret. A and C tie for top rank. C receives links from two pages; A receives only one link, but it comes from C, the important page, with C's full vote. B gets only half of A's vote. Check: \( M\mathbf{r} = (0.4,\ 0.2,\ 0.2 + 0.2) = (0.4, 0.2, 0.4) \). Correct.

Problems in the Real Web and the Damping Factor

The pure model breaks on the real web:

• Dangling nodes: pages with no outgoing links (such as a PDF) give a column of zeros, and the surfer gets stuck.
• Spider traps: a group of pages that only link to each other would soak up all the importance.
• Disconnected pieces: the eigenvector may not be unique.

Page and Brin's fix was the damping factor \( d \), typically \( 0.85 \). At each step the surfer follows a link with probability \( d \), and with probability \( 1 - d \) gets bored and jumps to a completely random page. The PageRank equation becomes

$$ \mathbf{r} = \frac{1 - d}{n}\mathbf{1} + d\,M\mathbf{r} $$

where \( \mathbf{1} \) is a vector of ones. (Dangling pages are handled by treating them as linking to every page.) The resulting "Google matrix" has all positive entries, and the Perron-Frobenius theorem then guarantees a unique positive eigenvector with eigenvalue 1, so the ranking is always well defined.

Power Iteration: Computing the Ranking

Solving the equations directly is impossible for billions of pages. Instead, Google used power iteration: start with equal ranks and repeatedly apply the update. Because 1 is the largest eigenvalue and the others are at most \( d \) in size, the error shrinks by a factor of about \( d \) each round.

Worked Example 2: Power Iteration with Damping

Use the three-page web with \( d = 0.85 \), \( n = 3 \), so \( \frac{1 - d}{n} = 0.05 \). Start with \( \mathbf{r}_0 = (\tfrac13, \tfrac13, \tfrac13) \).

The update equations are:

• \( a_{\text{new}} = 0.05 + 0.85\,c \)
• \( b_{\text{new}} = 0.05 + 0.85 \times \tfrac12 a \)
• \( c_{\text{new}} = 0.05 + 0.85\left(\tfrac12 a + b\right) \)

Iteration 1 (using \( a = b = c = 0.3333 \)):

• \( a_1 = 0.05 + 0.85(0.3333) = 0.3333 \)
• \( b_1 = 0.05 + 0.425(0.3333) = 0.1917 \)
• \( c_1 = 0.05 + 0.85(0.1667 + 0.3333) = 0.05 + 0.425 = 0.4750 \)

Iteration 2 (using \( \mathbf{r}_1 \)):

• \( a_2 = 0.05 + 0.85(0.4750) = 0.4538 \)
• \( b_2 = 0.05 + 0.425(0.3333) = 0.1917 \)
• \( c_2 = 0.05 + 0.85(0.1667 + 0.1917) = 0.05 + 0.3046 = 0.3546 \)

Check: each vector sums to 1, as it should (\( 0.4538 + 0.1917 + 0.3546 \approx 1 \)).

Continuing for a few dozen iterations, the values settle at approximately

$$ \mathbf{r} \approx (0.388,\ 0.215,\ 0.397) $$

Interpret. Damping pulls the scores slightly towards equality: B rises from 0.2 to 0.215, because random jumps give every page a minimum share. Now C edges ahead of A, since C collects votes from two pages. The ordering C, A, B is the search ranking among these pages.

Why Linear Algebra Makes It Scale

The real web matrix has billions of rows, but it is sparse: a typical page has only a few dozen links, so almost all entries are zero. Multiplying a sparse matrix by a vector costs time proportional to the number of links, not \( n^2 \). Page and Brin reported that around 50 iterations were enough for their 322-million-link database to converge. Today PageRank is only one of hundreds of ranking signals, but the eigenvector idea remains a cornerstone of network analysis, used for ranking scientific papers, finding influential users on social media and even studying protein interactions.

Did You Know?

• PageRank is named after Larry Page, not after web pages, a pun that suited the founders perfectly.
• The patent on PageRank was owned by Stanford University, which licensed it to Google in exchange for shares later sold for around 336 million US dollars.
• Similar eigenvector ranking ideas appeared earlier, for example in Gabriel Pinski and Francis Narin's 1976 method for ranking scientific journals by citations.

Key Takeaways

• PageRank treats links as weighted votes and models a random surfer as a Markov chain.
• The ranking vector is an eigenvector of the link matrix with eigenvalue 1.
• The damping factor (usually 0.85) fixes dead ends and spider traps and guarantees a unique answer.
• Power iteration computes the ranking efficiently by repeated matrix-vector multiplication.
• Sparsity lets the method scale to billions of pages.

If eigenvectors, Markov chains or a linear algebra assignment are giving you trouble, Amathify's subject experts and PhD scholars can provide step-by-step solutions; contact us on WhatsApp or through the Ask a Question form.