Skip to main content

PageRank

Rank the pages of a web by where a random surfer spends their time. Build the link matrix and the Google matrix, use Perron-Frobenius to get one ranking, prove that damping shrinks every other eigenvalue by d, and compute the ranks of a four-page web from scratch.
M03.9.4L2 Intermediate25 min
In review

The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.

Before this lesson: M03.9.3 Graphs as matrices M03.9.2 Steady states and Perron-Frobenius

What you will be able to do
  • Build the link matrix M of a web, with uniform rows for pages that have no links, and the Google matrix G = d M + (1 - d)/n times the all-ones matrix.
  • Explain with Perron-Frobenius why the PageRank vector exists, is unique and positive, and is reached by power iteration from any start.
  • Prove that every eigenvalue of M other than 1 is multiplied by d in G, so the iteration converges at a rate no slower than d.
  • Compute PageRank from scratch in NumPy without forming G, and check it against the eigenvector of G-transpose.

The question

Counting the links into a page is a poor way to rank it: a thousand links from pages nobody visits should count for less than one link from a famous page. “A page is important if important pages link to it” sounds circular. How does an eigenvector turn that circle into one set of numbers, and why does Google’s version always have exactly one answer?

From the last lesson

1. What is entry \((i, j)\) of the adjacency matrix of a directed graph, and what do its row sums give?

Show answer

It is 1 when there is an edge from \(i\) to \(j\) and 0 otherwise. Row sums are the out-degrees.

2. What does \((\mat{A}_G^k)_{ij}\) count?

Show answer

The walks of length \(k\) from \(i\) to \(j\).

Intuition

Picture a random surfer. On each click they either follow one of the links on the current page, chosen at random, or, with a fixed small chance, get bored and jump to a page chosen at random from the whole web. Run this for a very long time. The share of time spent on each page is its PageRank.

Two panels. Left, titled Size equals PageRank: the four-page web with links from 1 to 2, 1 to 3, 2 to 3, 3 to 1 and 4 to 3. Each page is a blue circle sized by its rank: page 1 is large, 0.373; page 2 medium, 0.196; page 3 largest, 0.394; page 4 small, 0.0375. Right, titled The ranks add up to 1: grey bars for pages 1 to 4 at 0.373, 0.196, 0.394 and 0.0375.
M03.9.4-F1

The PageRank of the running web with damping \(d = 0.85\). Page 3, with three links in, ranks first; page 1, with only one link in, ranks a close second, because that one link comes from page 3.

A link is a vote, and a page’s votes are worth what the page itself is worth, shared among everything it links to. The circle in the definition is exactly an eigenvector equation, and the random jumps are what make its answer unique.

Build it up

Step 1. The link matrix. If page \(i\) has \(k\) links, the surfer follows each with probability \(1/k\). So \(m_{ij} = 1/(\text{out-degree of } i)\) when \(i\) links to \(j\), and 0 otherwise: the adjacency matrix of M03.9.3 with each row divided by its sum. A page with no links at all, a dangling page, gets the uniform row \(1/n\): from a dead end the surfer jumps anywhere. Either way \(\mat{M}\) is a Markov matrix. The running web has no dangling page.

Step 2. Links alone are not enough. Following links only, nobody ever arrives at page 4: after one click its chance is 0 for good. A web can also split into pieces that never link to each other, or contain a loop that flips back and forth, the two failures of M03.9.2. The chain of \(\mat{M}\) alone gives no guarantee.

Step 3. The jump. With probability \(d\), the damping factor, the surfer follows a link; with probability \(1 - d\) they jump to any of the \(n\) pages, each with chance \(1/n\). Writing \(\mat{J}\) for the \(n \times n\) matrix of ones, the transition matrix is the Google matrix

\[ \mat{G} = d\,\mat{M} + \frac{1 - d}{n}\,\mat{J} . \]

Each row adds to \({d + (1 - d)} = 1\), and every entry is at least \({(1 - d)/n} > 0\).

Two matrices. Left, titled Link matrix M: rows 0, one half, one half, 0; 0, 0, 1, 0; 1, 0, 0, 0; and 0, 0, 1, 0, with the note each row: 1 split over the links. Right, titled Google matrix G, d equals 0.85: rows 0.0375, 0.4625, 0.4625, 0.0375; 0.0375, 0.0375, 0.8875, 0.0375; 0.8875, 0.0375, 0.0375, 0.0375; and 0.0375, 0.0375, 0.8875, 0.0375, with the note 0.85 m i j plus 0.15/4: every entry greater than 0.
M03.9.4-F2

From links to the Google matrix of the running web. Damping scales \(\mat{M}\) by 0.85 and spreads the remaining 0.15 evenly, so no entry of \(\mat{G}\) is zero.

Step 4. The PageRank equation. The ranks \(\vect{r}\) are the steady state of \(\mat{G}\): \(\vect{r} = \mat{G}\T\vect{r}\) with entries adding to 1. Since \(\mat{J}\vect{r}\) has every entry equal to \({\vect{1}\T\vect{r}} = 1\), this is

\[ \vect{r} = d\,\mat{M}\T\vect{r} + \frac{1 - d}{n}\,\vect{1}, \]

and entry by entry, for each page \(j\),

\[ r_j = \frac{1 - d}{n} + d \sum_{i \to j} \frac{r_i}{\text{out-degree of } i} . \]

Each page passes its rank in equal shares along its links, and everyone gets a floor of \({(1 - d)/n}\). Page 4 has no links in, so the sum is empty and \({r_4 = 0.15/4} = 0.0375\) exactly.

The formal statement

NoteTheorem: PageRank is well defined

Let \(\mat{M}\) be the link matrix of any web, with uniform rows for dangling pages, and let \(0 < d < 1\).

  1. \(\mat{G}\) is a positive Markov matrix, so it has exactly one stationary distribution \(\vect{r}\), the PageRank vector, with all entries positive, and power iteration reaches it from every start (M03.9.2).
  2. If \(\mu \ne 1\) is an eigenvalue of \(\mat{M}\), then \(d\mu\) is an eigenvalue of \(\mat{G}\), and every eigenvalue of \(\mat{G}\) other than 1 is \(d\) times an eigenvalue of \(\mat{M}\). So the second-largest eigenvalue modulus of \(\mat{G}\) is at most \(d\), and the error of power iteration shrinks at least as fast as \(d^t\), roughly.

Part 1 is Perron-Frobenius, since every entry of \(\mat{G}\) is positive. For part 2 the transpose is convenient: \({\mat{G}\T = d\,\mat{M}\T + \tfrac{1 - d}{n}\vect{1}\vect{1}\T}\), because \(\mat{J} = \vect{1}\vect{1}\T\).

Proof of 2. Let \(\mat{M}\T\vect{y} = \mu\vect{y}\) with \(\vect{y} \ne \vect{0}\) and \(\mu \ne 1\). By Step 2 of M03.9.2, applied to \(\mat{M}\), the entries of \(\vect{y}\) add to 0: \({\vect{1}\T\vect{y} = 0}\). Then

\[ \begin{aligned} \mat{G}\T\vect{y} &= d\,\mat{M}\T\vect{y} + \tfrac{1 - d}{n}\,\vect{1}\,(\vect{1}\T\vect{y}) \\ &= d\mu\,\vect{y} + \vect{0} = d\mu\,\vect{y} . \end{aligned} \]

So \(\vect{y}\) is an eigenvector of \(\mat{G}\T\) with eigenvalue \(d\mu\), and \(\mat{G}\) and \(\mat{G}\T\) share eigenvalues.

Conversely, let \(\mat{G}\T\vect{y} = \lambda\vect{y}\) with \(\vect{y} \ne \vect{0}\) and \(\lambda \ne 1\). Step 2 of M03.9.2, applied to the Markov matrix \(\mat{G}\) this time, gives \(\vect{1}\T\vect{y} = 0\), the jump term vanishes again, and \({\mat{G}\T\vect{y} = d\,\mat{M}\T\vect{y}}\). So \({\mat{M}\T\vect{y} = (\lambda/d)\,\vect{y}}\): the number \(\lambda/d\) is an eigenvalue of \(\mat{M}\), its modulus is at most 1 (M03.9.1), and so \(\abs{\lambda} \le d\). \(\blacksquare\)

The bound can be reached. If the links alone split into two or more closed pieces, \(\mat{M}\) has two different steady states (M03.9.2). Their difference \(\vect{y}\) has entries adding to 0 and \(\mat{M}\T\vect{y} = \vect{y}\), so \({\mat{G}\T\vect{y} = d\,\vect{y}}\) and \(\lambda_2 = d\). Haveliwala and Kamvar first proved both facts about \(\lambda_2\); Nussbaum gives short proofs.

The complex plane with the unit circle and a dashed circle of radius d equals 0.85. Hollow orange dots mark the eigenvalues of M: 1, minus one half plus one half i, its conjugate, and 0. Filled orange dots mark the eigenvalues of G: 1 again, 0, and the complex pair moved towards the origin along dotted green rays from 0, labelled times 0.85. Notes read solid circle: radius 1, dashed circle: radius 0.85, hollow: eigenvalues of M, filled: eigenvalues of G, and the modulus of lambda 2 of G equals 0.85 over root 2, about 0.601.
M03.9.4-F3

The eigenvalues of \(\mat{M}\) and \(\mat{G}\) for the running web. The eigenvalue 1 stays; every other one is multiplied by \(d = 0.85\). The complex pair \(-\frac12 \pm \frac12 i\) has modulus \(1/\sqrt2\), so in \(\mat{G}\) the second-largest modulus is \(0.85/\sqrt2 \approx 0.601\).

The eigenvalues of \(\mat{M}\) for the running web are \(1\), \(-\tfrac12 \pm \tfrac12 i\) and \(0\); they add to 0, the trace of \(\mat{M}\), as they must. The complex pair is why the error in the next section wobbles as it shrinks: a complex eigenvalue turns as well as scales.

Two panels against the damping factor d from 0.5 to 1. Left, titled Second eigenvalue modulus of G: a dashed grey line labelled bound d and, below it, an orange line labelled d over root 2, with a dot at d equals 0.85. Right, titled Steps to change less than 1e minus 10: green dots rising from 23 steps at d equals 0.5 to 65 at d equals 0.99, with 47 at 0.85 labelled.
M03.9.4-F6

The price of the damping factor on the running web. The second eigenvalue modulus of \(\mat{G}\) is \(d/\sqrt2\), below the general bound \(d\), and the number of power-iteration steps grows as \(d\) approaches 1.

Worked example

Find the PageRank of the running web with \(d = 0.85\), by hand.

Write the equation of Step 4 for each page. Page 1 hears only from page 3 (one link out), page 2 only from page 1 (two links out), and page 3 from pages 1, 2 and 4:

\[ \begin{aligned} r_4 &= 0.0375, \\ r_1 &= 0.0375 + 0.85\,r_3, \\ r_2 &= 0.0375 + 0.425\,r_1, \\ r_3 &= 0.0375 + 0.85\big(\tfrac12 r_1 + r_2 + r_4\big). \end{aligned} \]

Put \(r_4\) and \(r_2\) into the last line and collect:

\[ \begin{aligned} r_3 &= 0.0375 + 0.031875 \\ &\quad + 0.425\,r_1 + 0.85\,r_2 \\ &= 0.069375 + 0.425\,r_1 \\ &\quad + 0.85\,(0.0375 + 0.425\,r_1) \\ &= 0.10125 + 0.78625\,r_1 . \end{aligned} \]

Now the line for \(r_1\):

\[ \begin{aligned} r_1 &= 0.0375 + 0.85\,(0.10125 \\ &\qquad + 0.78625\,r_1) \\ &= 0.1235625 + 0.6683125\,r_1, \end{aligned} \]

so \({0.3316875\,r_1 = 0.1235625}\) and \(r_1 \approx 0.3725\). Back-substitute: \({r_3 = 0.10125 + 0.78625 \times 0.3725} \approx 0.3941\) and \({r_2 = 0.0375 + 0.425 \times 0.3725} \approx 0.1958\). The four ranks add to 1:

\[ \vect{r} \approx (0.373,\; 0.196,\; 0.394,\; 0.0375). \]

The exact value is \({r_1 = 659/1769}\). A real web has billions of pages, so nobody eliminates by hand; the power method of M03.2.4 does the work instead. From the uniform start, the link terms of one step are \({0.85 \times 0.25} = 0.2125\) into page 1, \({0.425 \times 0.25} = 0.10625\) into page 2 and \({0.85 \times 0.625} = 0.53125\) into page 3, where \(0.625\) is the \({0.125 + 0.25 + 0.25}\) arriving from pages 1, 2 and 4. So

\[ \begin{aligned} r_1 &= 0.0375 + 0.2125 = 0.25, \\ r_2 &= 0.0375 + 0.10625 = 0.14375, \\ r_3 &= 0.0375 + 0.53125 = 0.56875, \\ r_4 &= 0.0375 . \end{aligned} \]

Two panels. Left, titled Ranks r t, from one quarter each: four green lines with different markers against the step t from 0 to 12. All start at 0.25; page 4 drops to 0.0375 at step 1 and stays; the others swing for a few steps and settle at 0.394 for page 3, 0.373 for page 1 and 0.196 for page 2, each labelled at the right. Right, titled Error, the sum of absolute differences from r: a log scale from 1 down to below 1e minus 7 against the step t from 0 to 30; green dots fall in a slightly wavy straight line beside a dashed orange line labelled 0.601 to the t.
M03.9.4-F4

Power iteration on the running web. Page 4 reaches its rank after one step. The error shrinks by about 0.601 per step on average, the second eigenvalue modulus of \(\mat{G}\), with a wobble from the complex eigenvalues.

Code

PageRank from scratch. A real web is stored as lists of links, never as a dense \(n \times n\) matrix, so the function below never forms \(\mat{G}\) or even \(\mat{M}\): each step passes every page’s rank along its links, spreads the rank of dangling pages evenly, and adds the jump.

import numpy as np

def pagerank(links, n, d=0.85, tol=1e-10, max_steps=1000):
    """links: dict page -> list of pages it links to (pages 0..n-1). Returns ranks and steps."""
    r = np.full(n, 1.0 / n)
    for step in range(1, max_steps + 1):
        new = np.zeros(n)
        dangling = 0.0
        for i in range(n):
            out = links.get(i, [])
            if out:
                for j in out:
                    new[j] += d * r[i] / len(out)     # follow a link
            else:
                dangling += d * r[i]                   # a dead end: jump anywhere
        new += (1 - d) / n + dangling / n              # the random jump
        if np.abs(new - r).sum() < tol:
            return new, step
        r = new
    return r, max_steps

web = {0: [1, 2], 1: [2], 2: [0], 3: [2]}             # the running web, pages counted from 0
r, steps = pagerank(web, 4)
print("PageRank:", r.round(4), "  steps:", steps)
PageRank: [0.3725 0.1958 0.3941 0.0375]   steps: 47

The library check builds the dense matrices, as one can for four pages, and takes the eigenvector of \(\mat{G}\T\) for the eigenvalue 1.

M = np.zeros((4, 4))
for i, out in web.items():
    M[i, out] = 1 / len(out)
d = 0.85
G = d * M + (1 - d) / 4 * np.ones((4, 4))
w, V = np.linalg.eig(G.T)
k = np.argmin(np.abs(w - 1))
r_eig = (V[:, k] / V[:, k].sum()).real
moduli = np.sort(np.abs(w))[::-1]
print("from eig:", r_eig.round(4))
print("eigenvalues of M:", np.round(np.linalg.eigvals(M), 3))
print("moduli for G:", moduli.round(4), "  0.85/sqrt(2) =", round(d / np.sqrt(2), 4))
from eig: [0.3725 0.1958 0.3941 0.0375]
eigenvalues of M: [ 0. +0.j  -0.5+0.5j -0.5-0.5j  1. +0.j ]
moduli for G: [1.    0.601 0.601 0.   ]   0.85/sqrt(2) = 0.601

Both routes agree to eight decimal places. The second-largest modulus is \(0.6010\), which is \(0.85/\sqrt2\), as the theorem predicted from \(\mat{M}\)’s eigenvalue \(-\tfrac12 + \tfrac12 i\). About 47 steps reach a change below \(10^{-10}\), and \(0.601^{47} \approx 4 \times 10^{-11}\). Storing only the links is what makes this scale to a real web; module M10.7 does it with sparse matrices.

Explore

M03.9-X1

Random surfer

Press step to move the surfer’s probability one click, or play to watch it settle. Drag the damping factor towards 1 and watch the second eigenvalue modulus, and the number of steps, grow; switch off the link from 1 to 2 at \(d = 1\) to make pages 1 and 3 flip for ever.

The four-page web with each page drawn at a size set by its PageRank, 0.373, 0.196, 0.394 and 0.0375, beside bars of the same four ranks, which add up to 1.

Pitfalls

Two panels of the total chance, summed over the four pages, against the step t from 0 to 10, for the web with the link from 3 to 1 removed so that page 3 links nowhere. Left, marked with a cross and titled Leave a zero row: vermillion dots fall from 1 to 0.79, 0.34 and then stay at 0.26, below a dashed line at 1, with the note total chance sinks to 0.26. Right, marked with a tick and titled Use a uniform row: green dots stay at 1, with the note total chance stays 1.
M03.9.4-F5

Wrong beside right, on the web with the link from 3 to 1 removed. Leaving page 3’s row as zeros lets probability fall out of the web at that dead end. Replacing it by the uniform row keeps \(\mat{M}\) a Markov matrix.

“A page with more links in ranks higher.”

Pages 1 and 2 each have exactly one link in, yet page 1’s rank is almost twice page 2’s. Page 1’s link comes from page 3, which passes all its rank to page 1; page 2’s comes from page 1, which splits its rank in two. In-links are weighted by the rank of the page they come from.

“A page with no links can simply be left as a row of zeros.”

Then \(\mat{M}\) is no longer a Markov matrix: each step loses the rank sitting on that page, and the “ranks” no longer add to 1. The figure shows the total falling to 0.26. The uniform row, or the equivalent dangling / n term in the code, puts the lost probability back.

“The closer \(d\) is to 1, the better, because the jump is an artificial extra.”

The convergence rate is up to \(d\), so \(d = 0.99\) needs many more steps than \(0.85\), and at \(d = 1\) the guarantees of Perron-Frobenius are gone: two separate pieces give several rankings and a flipping loop gives none. Brin and Page report \(d = 0.85\) as their usual setting, and Austin explains such a value as a compromise between following the links faithfully and converging fast.

Check yourself

Recall

1. How is the link matrix \(\mat{M}\) built from the links of a web?

Show answer

\(m_{ij} = 1/(\text{out-degree of } i)\) when page \(i\) links to page \(j\), and 0 otherwise; a page with no links gets the uniform row \(1/n\).

2. What is the Google matrix, and why is it positive?

Show answer

\(\mat{G} = d\,\mat{M} + \tfrac{1 - d}{n}\mat{J}\). Every entry is at least \((1 - d)/n > 0\), because of the random jump.

3. Write the PageRank equation for a single page \(j\).

Show answer

\(r_j = \tfrac{1 - d}{n} + d\sum_{i \to j} r_i/(\text{out-degree of } i)\).

4. How do the eigenvalues of \(\mat{G}\) relate to those of \(\mat{M}\)?

Show answer

The eigenvalue 1 stays, and every other eigenvalue \(\mu\) of \(\mat{M}\) becomes \(d\mu\). So the second-largest modulus of \(\mat{G}\) is at most \(d\).

5. What is the PageRank of the running web, and why is page 4’s exactly \(0.0375\)?

Show answer

About \((0.373, 0.196, 0.394, 0.0375)\). Nothing links to page 4, so it receives only the jump: \({(1 - 0.85)/4} = 0.0375\).

Exercises

1. ★ Start the surfer on page 4, \(\vect{r}_0 = (0, 0, 0, 1)\). Find \(\vect{r}_1\) for the running web with \(d = 0.85\).

Show solution

Page 4 links only to page 3, so \(\mat{M}\T\vect{r}_0 = (0, 0, 1, 0)\). Then

\[ \begin{aligned} \vect{r}_1 &= 0.85\,(0, 0, 1, 0) \\ &\quad + 0.0375\,(1, 1, 1, 1) \\ &= (0.0375,\; 0.0375, \\ &\qquad\ 0.8875,\; 0.0375), \end{aligned} \]

which is the fourth row of \(\mat{G}\), as it must be.

2. ★★ Two pages link only to each other. Find \(\mat{G}\), its eigenvalues and the PageRank, and say how fast power iteration converges.

Show solution

\(\mat{M}\) is the flip of M03.9.2, with eigenvalues 1 and \(-1\). With \(d\),

\[ \mat{G} = \begin{bmatrix} \frac{1 - d}{2} & \frac{1 + d}{2} \\[2pt] \frac{1 + d}{2} & \frac{1 - d}{2} \end{bmatrix}. \]

By the theorem its eigenvalues are 1 and \(-d\) (check: the trace is \({1 - d}\)). By symmetry the PageRank is \((\tfrac12, \tfrac12)\). The second eigenvalue modulus is exactly \(d\), so the error shrinks by \(d\) per step, flipping sign each time: the flip has been tamed, but only just.

3. ★★★ Show that \(\mat{I} - d\,\mat{M}\T\) is invertible for \(0 \le d < 1\), so that \({\vect{r} = \tfrac{1 - d}{n}(\mat{I} - d\,\mat{M}\T)^{-1}\vect{1}}\), and expand the inverse as a series. What does the series say about the random surfer?

Show solution

The 1-norm of \(\mat{M}\T\) is its largest column sum (M03.8.1), which is the largest row sum of \(\mat{M}\), namely 1. If \({(\mat{I} - d\mat{M}\T)\vect{x} = \vect{0}}\), then \(\vect{x} = d\,\mat{M}\T\vect{x}\) and \({\norm{\vect{x}}_1 \le d\,\norm{\vect{x}}_1}\), which forces \(\vect{x} = \vect{0}\). So the matrix is invertible, and the PageRank equation of Step 4 rearranges to the formula. Since \({\norm{d\mat{M}\T}_1 = d < 1}\), the geometric series converges:

\[ \vect{r} = \tfrac{1 - d}{n}\textstyle\sum_{k \ge 0} d^k (\mat{M}\T)^k\vect{1}. \]

Read it as the surfer’s story: after each jump, which lands uniformly, they follow exactly \(k\) links with probability \({(1 - d)d^k}\) before the next jump, and \((\mat{M}\T)^k\vect{1}/n\) is where \(k\) clicks from a uniform start lead.

Summary card

PageRank is the steady state of a random surfer who follows links and sometimes jumps.

The anchor figure again: the four-page web with each page sized by its PageRank, 0.373, 0.196, 0.394 and 0.0375, beside the same ranks as bars.
M03.9.4-F1

Size is time spent there.

  • Link matrix. \(m_{ij}\) is one over the out-degree of \(i\) for each link; dangling rows are uniform.
  • Google matrix. \(\mat{G} = d\,\mat{M} + \tfrac{1 - d}{n}\mat{J}\), positive and Markov.
  • Ranks. \(\vect{r} = d\,\mat{M}\T\vect{r} + \tfrac{1 - d}{n}\vect{1}\), unique by Perron-Frobenius.
  • Speed. Eigenvalues \(\mu \ne 1\) become \(d\mu\): rate at most \(d\); \(0.601\) here.
  • Running web, \(d = 0.85\): \(\vect{r} \approx {(0.373, 0.196,}\) \({0.394, 0.0375)}\).

Sources and next steps

Sources. Each was opened and checked against this lesson on 15 November 2026.

  • Sergey Brin and Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems 30 (1998), 107 to 117. Section 2.1.1: the PageRank formula with damping factor \(d\), “usually set to 0.85”, ranks forming a probability distribution, and an iterative computation as the principal eigenvector of the normalised link matrix. Section 2.1.2: the random surfer. (Its formula writes the jump term as \(1 - d\) without dividing by the number of pages; the version here divides, so that the ranks add to 1.)
  • Dan Margalit and Joseph Rabinoff, Interactive Linear Algebra, section 5.6 Stochastic matrices (Georgia Tech). Subsection 5.6.3: dangling pages replaced by columns of \(1/n\), and the Google matrix as a mixture of the importance matrix with the matrix of all entries \(1/n\). It writes the jump weight as \(p = 0.15\) and uses columns, so its matrix is our \(\mat{G}\T\).
  • David Austin, Understanding Linear Algebra, section Markov chains and Google’s PageRank algorithm (open textbook). The modified Google matrix \(\alpha G + (1 - \alpha)H_n\) with \(\alpha = 0.85\) thought to be Google’s choice, and the trade-off between a smaller \(\alpha\) converging faster and staying close to the link structure.
  • Roger Nussbaum, Notes on the second eigenvalue of the Google matrix (arXiv, 2003), for row-stochastic matrices as here. Corollary 1: for \({A = cP + (1 - c)E}\) with \(E\) row-stochastic of rank 1, \(\abs{\lambda_2} \le c\). Corollary 2: \(\lambda_2 = c\) when \(P\) has more than one independent fixed vector, which Remark 1 equates with at least two closed pieces. Both reprove theorems of Haveliwala and Kamvar.

Next. This closes the module. Module M03.10 turns to tensors and index notation; M10.7 stores graphs with billions of edges as sparse matrices, and M10.5 meets faster eigenvalue algorithms than the power method.

This lesson unlocks

M03.10 Tensors and index notation for deep learning M10.7 Sparse matrices and graphs (planned)

Your progress is saved in this browser only. No account, no tracking.
Back to top