19.8 PageRank

A search engine that finds thousands of pages containing a word must decide which to list first. One answer, which made a search engine famous, is to let the pages vote. Each page spreads its vote over the pages it links to, a vote counts for more when it comes from a page that is itself important, and “important” is whatever this circular description settles on. Written out, the circle is an eigenvector equation for a stochastic matrix. This section sets up that matrix, shows why the raw web does not give a well-defined ranking, repairs it with a single parameter, and uses Perron’s theorem (Theorem 19.1.5) to prove that the repaired matrix has exactly one ranking, with every entry positive. We then prove how fast the ranking can be computed, and work a small web exactly.

Throughout, the field is $\mathbb{R}$ , inequalities between vectors and matrices are entrywise as in §01, and stochastic means column-stochastic (Definition 9.11.1): nonnegative entries, every column adding up to $1$ . Many accounts of PageRank use rows instead; their matrices are the transposes of ours. We write $\mathbf{1}$ for the all-ones vector and $\mathbf{J} = \mathbf{1}\mathbf{1}^{\top}$ for the all-ones matrix.

19.8.1. The web as a Markov chain

Number the pages $1, \dots, n$ . Page $j$ links to page $i$ if it contains a link to it; we ignore links from a page to itself, and several links from $j$ to $i$ count as one. Let $d_j$ be the number of pages that page $j$ links to, its out-degree. A page with $d_j = 0$ is called dangling: a document with no links out, such as an image or a file.

Imagine a surfer who, on page $j$ , clicks one of its $d_j$ links, each with probability $1/d_j$ . If $\mathbf{x}_k$ is the probability vector of the surfer’s position after $k$ clicks, then, exactly as in Chapter 9 §11, $\mathbf{x}_{k+1} = \mathbf{H}\mathbf{x}_k$ , where $h_{ij} = 1/d_j$ if $j$ links to $i$ and $h_{ij} = 0$ otherwise. This hyperlink matrix $\mathbf{H}$ is local to this section; elsewhere in the book $\mathbf{H}$ is a Hessian. The long-run share of time the surfer spends on page $i$ is the candidate for page $i$ ’s importance. It captures the circular description: page $i$ receives, from each page $j$ linking to it, the share $1/d_j$ of $j$ ’s own weight.

At a dangling page the surfer has nowhere to go, and column $j$ of $\mathbf{H}$ is zero. The standard patch sends the surfer to a page chosen uniformly at random.

Definition 19.8.1 (Link Matrix)

Let a web have pages $1, \dots, n$ , with $n \ge 1$ , and out-degrees $d_1, \dots, d_n$ . Its link matrix is the $n \times n$ matrix $\mathbf{P}$ whose column $j$ is:

(a) if $d_j \ge 1$ : the vector with entry $1/d_j$ in each position $i$ such that page $j$ links to page $i$ , and $0$ elsewhere;
(b) if $d_j = 0$ (page $j$ is dangling): the vector $\tfrac1n\mathbf{1}$ .

Each column is a probability vector: in case (a) it has $d_j$ entries equal to $1/d_j$ , and in case (b) $n$ entries equal to $1/n$ . So $\mathbf{P}$ is stochastic. For instance, the web on three pages in which page $1$ links to pages $2$ and $3$ , page $2$ links to page $3$ , and page $3$ links nowhere, has $\mathbf{P} = \begin{pmatrix} 0 & 0 & \tfrac13 \\ \tfrac12 & 0 & \tfrac13 \\ \tfrac12 & 1 & \tfrac13 \end{pmatrix} .$

A ranking should then be a steady state of $\mathbf{P}$ (Definition 9.11.2): a probability vector $\mathbf{x}$ with $\mathbf{P}\mathbf{x} = \mathbf{x}$ . When $\mathbf{P}$ is irreducible (Definition 19.2.3), there is exactly one, with every entry positive, by Proposition 19.6.1 (c); part (a) of the same proposition gives $\rho(\mathbf{P}) = 1$ for every stochastic $\mathbf{P}$ . The real web is very far from irreducible, and the three failures below are the typical ones.

Example (Three ways a web can fail to rank)

For each web, describe what goes wrong with the surfer’s chain.

(a) Two pages; page $1$ links to page $2$ , and page $2$ is dangling, but we use $\mathbf{H}$ , without the patch.
(b) Four pages; pages $1$ and $2$ link to each other, and so do pages $3$ and $4$ .
(c) Two pages that link to each other.

Solution.

(a) $\mathbf{H} = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}$ has a zero column, so it is not stochastic, and $\mathbf{H}^2 = \mathbf{O}$ . From any start the surfer is gone after two clicks: $\mathbf{H}^2\mathbf{x}_0 = \mathbf{0}$ is not a probability vector, and $\mathbf{H}$ has no steady state at all, since $\mathbf{H}\mathbf{x} = \mathbf{x}$ forces $x_1 = 0$ and then $x_2 = x_1 = 0$ . The patched $\mathbf{P}$ has second column $(\tfrac12, \tfrac12)$ and the steady state $(\tfrac13, \tfrac23)$ , since $\mathbf{P}(1, 2) = (0 \cdot 1 + \tfrac12 \cdot 2,\ 1 \cdot 1 + \tfrac12 \cdot 2) = (1, 2)$ .
(b) $\mathbf{P}$ is block diagonal with two copies of the swap $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ . Both $(\tfrac12, \tfrac12, 0, 0)$ and $(0, 0, \tfrac12, \tfrac12)$ are steady states, and so is every average of the two. The chain cannot say whether page $1$ matters more than page $3$ : the ranking is not unique.
(c) $\mathbf{P}$ is the swap. Its steady state $(\tfrac12, \tfrac12)$ is unique, but from $\mathbf{x}_0 = \mathbf{e}_1$ the chain alternates $\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_1, \dots$ and never settles. The eigenvalue $-1$ of the swap has the same modulus as $1$ .

In (b) the matrix is reducible, and in (c) it is irreducible but not primitive (Definition 19.5.1): the powers of the swap are $\mathbf{I}$ and the swap, and neither is positive. Real webs have all three features, on a vast scale.

19.8.2. The Google matrix

The dangling patch of Definition 19.8.1 already repairs failure (a). One modification repairs the remaining two at once. Let the surfer, at every step, toss a biased coin: with probability $\alpha$ follow a link as before, and with probability $1 - \alpha$ get bored and jump to a page chosen uniformly at random from all $n$ . The jump is called teleportation, and $\alpha$ the damping factor; a value around $0.85$ is customary.

The Google matrix mixes following links with jumping to a random page; its fixed probability vector is the ranking.

Definition 19.8.2 (Google Matrix, PageRank Vector)

Let $\mathbf{P} \in M_n(\mathbb{R})$ be the link matrix of a web with $n \ge 1$ pages, and let $0 < \alpha < 1$ . The matrix $\mathbf{G} = \alpha\mathbf{P} + \frac{1 - \alpha}{n}\,\mathbf{J}$ is called the Google matrix in the literature, with damping factor $\alpha$ . A PageRank vector of the web is a probability vector $\boldsymbol{\uppi} \in \mathbb{R}^n$ with $\mathbf{G}\boldsymbol{\uppi} = \boldsymbol{\uppi}$ . Page $i$ is ranked above page $k$ when $\pi_i > \pi_k$ .

In words: column $j$ of $\mathbf{G}$ is $\alpha$ times column $j$ of $\mathbf{P}$ , the link step, plus $1 - \alpha$ times the uniform vector $\tfrac1n\mathbf{1}$ , the jump. A PageRank vector is a steady state of the surfer’s new chain. The letter $\mathbf{G}$ is local to this section; elsewhere in the book $\mathbf{G}$ is a Gram matrix. The theorem below shows that there is exactly one, which justifies calling it the PageRank vector.

Two properties of $\mathbf{G}$ do all the work.

$\mathbf{G}$ is stochastic. Its entries are nonnegative, and column $j$ adds up to $\alpha \cdot 1 + (1 - \alpha)\cdot\tfrac1n \cdot n = 1$ .
$\mathbf{G}$ is positive. Every entry is at least $\tfrac{1 - \alpha}{n} > 0$ , because $\alpha\mathbf{P} \ge \mathbf{O}$ and $\alpha < 1$ strictly.

Two degenerate values of $\alpha$ are excluded, and each shows why. With $\alpha = 1$ , $\mathbf{G} = \mathbf{P}$ , and the failures (b) and (c) of Example (Three ways a web can fail to rank) come back. With $\alpha = 0$ , $\mathbf{G} = \tfrac1n\mathbf{J}$ for every web, the PageRank vector is $\tfrac1n\mathbf{1}$ , and the links are ignored: every page ties. The damping factor trades faithfulness to the links against the good behavior of the chain, and we will see that the speed of the computation is governed by $\alpha$ alone.

For the three-page web above, with $\alpha = \tfrac12$ , $\mathbf{G} = \frac12\mathbf{P} + \frac16\mathbf{J} = \begin{pmatrix} \tfrac16 & \tfrac16 & \tfrac13 \\ \tfrac5{12} & \tfrac16 & \tfrac13 \\ \tfrac5{12} & \tfrac23 & \tfrac13 \end{pmatrix} ,$ with columns adding up to $1$ and every entry positive.

A nonexample by minimal change. Replace the uniform jump by a jump to page $1$ only: $\mathbf{G}' = \alpha\mathbf{P} + (1 - \alpha)\mathbf{e}_1\mathbf{1}^{\top}$ . It is still stochastic, since each column of $\mathbf{e}_1\mathbf{1}^{\top}$ is $\mathbf{e}_1$ . What fails is positivity: in the web of Example (Three ways a web can fail to rank) (b), $\mathbf{G}'$ has zeros in rows $3$ and $4$ of columns $1$ and $2$ , so Perron’s theorem no longer applies. (Here the ranking is still unique, but it gives pages $3$ and $4$ weight zero, since no surfer ever returns to them from pages $1$ and $2$ .) Exercise B3 shows that any jump distribution with all entries positive works as well as the uniform one.

Warning. PageRank is not a count of incoming links. A link is worth the rank of the page it comes from, divided by that page’s out-degree. In the four-page example at the end of this section, page $3$ has more incoming links than any other page, yet page $1$ , with a single incoming link, ranks above it, because that link comes from page $3$ and is page $3$ ’s only link.

19.8.3. A unique positive ranking

Perron’s theorem, applied to the positive matrix $\mathbf{G}$ , settles existence, uniqueness, and positivity at once. It also turns the eigenvector problem into a linear system.

Theorem 19.8.1 (The PageRank Vector)

Let $\mathbf{P} \in M_n(\mathbb{R})$ be stochastic, $0 < \alpha < 1$ , and $\mathbf{G} = \alpha\mathbf{P} + \frac{1-\alpha}{n}\mathbf{J}$ . Then:

(a) $\rho(\mathbf{G}) = 1$ , and $1$ is an eigenvalue of $\mathbf{G}$ of algebraic multiplicity one;
(b) there is exactly one probability vector $\boldsymbol{\uppi}$ with $\mathbf{G}\boldsymbol{\uppi} = \boldsymbol{\uppi}$ , and every entry of $\boldsymbol{\uppi}$ is positive;
(c) $\mathbf{I} - \alpha\mathbf{P}$ is invertible, and $\boldsymbol{\uppi}$ is the unique solution of $(\mathbf{I} - \alpha\mathbf{P})\,\boldsymbol{\uppi} = \frac{1 - \alpha}{n}\,\mathbf{1} .$

Idea. Perron’s theorem hands us a simple eigenvalue $\rho(\mathbf{G})$ with a positive eigenvector, so the only question is the value of $\rho(\mathbf{G})$ ; the column sums pin it at $1$ . For (c), on probability vectors the rank-one part $\frac{1-\alpha}{n}\mathbf{J}\mathbf{x}$ is the constant vector $\frac{1-\alpha}{n}\mathbf{1}$ , so the eigenvector equation becomes linear with a right-hand side.

Proof.

(a) By Theorem 16.3.3 (a), $\left\| \mathbf{G} \right\|_1$ is the largest column sum of $\lvert\mathbf{G}\rvert$ , which is $1$ since $\mathbf{G}$ is stochastic; so $\rho(\mathbf{G}) \le 1$ by Theorem 16.4.1 (a). By Proposition 9.11.3 (c), $1$ is an eigenvalue of $\mathbf{G}$ . Hence $\rho(\mathbf{G}) = 1$ . Since every entry of $\mathbf{G}$ is at least $\frac{1-\alpha}{n} > 0$ , Perron’s theorem (Theorem 19.1.5) applies: by its parts (a) and (b), $\rho(\mathbf{G}) = 1$ is an eigenvalue of algebraic multiplicity one, with an eigenvector $\mathbf{v} > \mathbf{0}$ spanning $E_1(\mathbf{G})$ .
(b) Put $\boldsymbol{\uppi} = \mathbf{v}/(\mathbf{1}^{\top}\mathbf{v})$ , which is defined because $\mathbf{1}^{\top}\mathbf{v} > 0$ . It is a probability vector with positive entries and $\mathbf{G}\boldsymbol{\uppi} = \boldsymbol{\uppi}$ . If $\boldsymbol{\uppi}'$ is another probability vector with $\mathbf{G}\boldsymbol{\uppi}' = \boldsymbol{\uppi}'$ , then $\boldsymbol{\uppi}'$ lies in $E_1(\mathbf{G}) = \operatorname{span}(\mathbf{v})$ , so $\boldsymbol{\uppi}' = c\boldsymbol{\uppi}$ for some $c$ , and comparing entry sums gives $1 = c$ . Hence $\boldsymbol{\uppi}' = \boldsymbol{\uppi}$ . In the language of §01, $\boldsymbol{\uppi}$ is the Perron vector of $\mathbf{G}$ (Definition 19.1.2).
(c) If $(\mathbf{I} - \alpha\mathbf{P})\mathbf{z} = \mathbf{0}$ with $\mathbf{z} \ne \mathbf{0}$ , then $\mathbf{P}\mathbf{z} = \alpha^{-1}\mathbf{z}$ , so $\alpha^{-1} > 1$ is an eigenvalue of $\mathbf{P}$ ; but $\rho(\mathbf{P}) \le \left\| \mathbf{P} \right\|_1 = 1$ as in (a). So $0$ is not an eigenvalue of $\mathbf{I} - \alpha\mathbf{P}$ , and $\mathbf{I} - \alpha\mathbf{P}$ is invertible by Theorem 9.2.6. For a probability vector $\mathbf{x}$ , $\mathbf{J}\mathbf{x} = \mathbf{1}(\mathbf{1}^{\top}\mathbf{x}) = \mathbf{1}$ , so $\mathbf{G}\mathbf{x} = \alpha\mathbf{P}\mathbf{x} + \frac{1 - \alpha}{n}\,\mathbf{1} ,$ and $\mathbf{G}\boldsymbol{\uppi} = \boldsymbol{\uppi}$ is the equation $(\mathbf{I} - \alpha\mathbf{P})\boldsymbol{\uppi} = \frac{1-\alpha}{n}\mathbf{1}$ . So $\boldsymbol{\uppi}$ solves the system, and by invertibility it is the only solution.

So the ranking exists, is unique, and gives every page a positive score: no page is ignored, however obscure. Part (c) is how one computes it for a small web: solve an $n \times n$ linear system, with no eigenvalue in sight. A useful bonus is that the solution of (c) is automatically a probability vector. Multiplying the system on the left by $\mathbf{1}^{\top}$ , and using $\mathbf{1}^{\top}\mathbf{P} = \mathbf{1}^{\top}$ , $(1 - \alpha)\,\mathbf{1}^{\top}\boldsymbol{\uppi} = \frac{1 - \alpha}{n}\,\mathbf{1}^{\top}\mathbf{1} = 1 - \alpha ,$ so $\mathbf{1}^{\top}\boldsymbol{\uppi} = 1$ without being imposed.

Quick check. Two pages link to each other, and $\alpha = \tfrac12$ . Write down $\mathbf{G}$ , find $\boldsymbol{\uppi}$ , and find the eigenvalues of $\mathbf{G}$ .

Solution. $\mathbf{P}$ is the swap, so $\mathbf{G} = \frac12\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} + \frac14\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} \tfrac14 & \tfrac34 \\ \tfrac34 & \tfrac14 \end{pmatrix} .$ Then $\mathbf{G}(1, 1) = (1, 1)$ and $\mathbf{G}(1, -1) = (-\tfrac12, \tfrac12) = -\tfrac12(1, -1)$ . So $\boldsymbol{\uppi} = (\tfrac12, \tfrac12)$ , and the eigenvalues are $1$ and $-\tfrac12$ . The swap has eigenvalues $1$ and $-1$ : the second one has been multiplied by $\alpha$ . The next theorem says that this always happens.

19.8.4. The second eigenvalue

The PageRank vector of a real web is computed by iterating $\mathbf{x}_{k+1} = \mathbf{G}\mathbf{x}_k$ , since the web has billions of pages and no one solves a system of that size exactly. How fast the iterates settle depends on the eigenvalues of $\mathbf{G}$ other than $1$ . For a general positive matrix, Perron’s theorem says only that they are strictly smaller than $\rho$ in modulus, with no bound on how much smaller. For the Google matrix there is an exact description.

Theorem 19.8.2 (The Eigenvalues of the Google Matrix)

Let $n \ge 2$ , let $\mathbf{P} \in M_n(\mathbb{R})$ be stochastic, let $0 \le \alpha \le 1$ , and let $\mathbf{G} = \alpha\mathbf{P} + \frac{1-\alpha}{n}\mathbf{J}$ . Since $1$ is an eigenvalue of $\mathbf{P}$ (Proposition 9.11.3) and $p_{\mathbf{P}}$ splits over $\mathbb{C}$ (Theorem 6.5.1), it factors as $p_{\mathbf{P}}(x) = (x - 1)(x - \mu_2)\cdots(x - \mu_n)$ with $\mu_2, \dots, \mu_n \in \mathbb{C}$ . Then $p_{\mathbf{G}}(x) = (x - 1)(x - \alpha\mu_2)\cdots(x - \alpha\mu_n) .$ In particular, if $\alpha < 1$ , every eigenvalue $\lambda \ne 1$ of $\mathbf{G}$ satisfies $\lvert\lambda\rvert \le \alpha$ .

Idea. Both $\mathbf{P}$ and $\mathbf{G}$ have $\mathbf{1}^{\top}$ as a left eigenvector for $1$ . Change basis so that $\mathbf{1}^{\top}$ becomes the first coordinate functional $\mathbf{e}_1^{\top}$ ; then both matrices become block lower triangular with a $1$ in the corner. The teleportation term $\frac1n\mathbf{J} = \frac1n\mathbf{1}\mathbf{1}^{\top}$ only touches the first column in the new basis, so the lower-right blocks are $\mathbf{P}_1$ and $\alpha\mathbf{P}_1$ for the same $\mathbf{P}_1$ . The eigenvalues of $\mathbf{P}$ other than the $1$ in the corner are those of $\mathbf{P}_1$ ; those of $\mathbf{G}$ are $\alpha$ times them.

Proof. Let $\mathbf{N} = \mathbf{e}_1(\mathbf{1} - \mathbf{e}_1)^{\top}$ , the matrix whose first row is $(0, 1, \dots, 1)$ and whose other rows are zero, and let $\mathbf{S} = \mathbf{I} + \mathbf{N}$ . Its first row is $\mathbf{1}^{\top}$ and its other rows are those of $\mathbf{I}$ , so $\mathbf{e}_1^{\top}\mathbf{S} = \mathbf{1}^{\top}$ . Since $(\mathbf{1} - \mathbf{e}_1)^{\top}\mathbf{e}_1 = 0$ , $\mathbf{N}^2 = \mathbf{e}_1\bigl((\mathbf{1} - \mathbf{e}_1)^{\top}\mathbf{e}_1\bigr)(\mathbf{1} - \mathbf{e}_1)^{\top} = \mathbf{O}$ , and therefore $(\mathbf{I} + \mathbf{N})(\mathbf{I} - \mathbf{N}) = \mathbf{I} - \mathbf{N}^2 = \mathbf{I}$ . So $\mathbf{S}$ is invertible with $\mathbf{S}^{-1} = \mathbf{I} - \mathbf{N}$ (Theorem 3.4.5).

Claim. Claim. If $\mathbf{M} \in M_n(\mathbb{R})$ satisfies $\mathbf{1}^{\top}\mathbf{M} = \mathbf{1}^{\top}$ , then the first row of $\mathbf{S}\mathbf{M}\mathbf{S}^{-1}$ is $\mathbf{e}_1^{\top}$ .

Proof. The first row is $\mathbf{e}_1^{\top}\mathbf{S}\mathbf{M}\mathbf{S}^{-1} = \mathbf{1}^{\top}\mathbf{M}\mathbf{S}^{-1} = \mathbf{1}^{\top}\mathbf{S}^{-1} = \mathbf{e}_1^{\top}\mathbf{S}\mathbf{S}^{-1} = \mathbf{e}_1^{\top}$ .

Since $\mathbf{P}$ is stochastic, $\mathbf{1}^{\top}\mathbf{P} = \mathbf{1}^{\top}$ , and the claim gives $\mathbf{S}\mathbf{P}\mathbf{S}^{-1} = \begin{pmatrix} 1 & \mathbf{0}^{\top} \\ \mathbf{b} & \mathbf{P}_1 \end{pmatrix}$ for some $\mathbf{b} \in \mathbb{R}^{n-1}$ and $\mathbf{P}_1 \in M_{n-1}(\mathbb{R})$ . For the teleportation term, $\mathbf{S}\bigl(\tfrac1n\mathbf{1}\mathbf{1}^{\top}\bigr)\mathbf{S}^{-1} = \tfrac1n(\mathbf{S}\mathbf{1})(\mathbf{1}^{\top}\mathbf{S}^{-1}) = \tfrac1n(\mathbf{S}\mathbf{1})\,\mathbf{e}_1^{\top} ,$ using $\mathbf{1}^{\top}\mathbf{S}^{-1} = \mathbf{e}_1^{\top}$ from the proof of the claim. Its only nonzero column is the first, $\tfrac1n\mathbf{S}\mathbf{1}$ , whose first entry is $\tfrac1n\mathbf{1}^{\top}\mathbf{1} = 1$ . So it equals $\begin{pmatrix} 1 & \mathbf{0}^{\top} \\ \mathbf{c} & \mathbf{O} \end{pmatrix}$ for some $\mathbf{c} \in \mathbb{R}^{n-1}$ , and $\begin{aligned} \mathbf{S}\mathbf{G}\mathbf{S}^{-1} &= \alpha\,\mathbf{S}\mathbf{P}\mathbf{S}^{-1} + (1 - \alpha)\,\mathbf{S}\bigl(\tfrac1n\mathbf{J}\bigr)\mathbf{S}^{-1} \\ &= \begin{pmatrix} 1 & \mathbf{0}^{\top} \\ \alpha\mathbf{b} + (1-\alpha)\mathbf{c} & \alpha\mathbf{P}_1 \end{pmatrix} . \end{aligned}$ Similar matrices have the same characteristic polynomial (Theorem 7.10.3), and $x\mathbf{I}$ minus a block lower triangular matrix is block lower triangular, so by Theorem 7.8.4 $p_{\mathbf{P}}(x) = (x - 1)\,p_{\mathbf{P}_1}(x) , \qquad p_{\mathbf{G}}(x) = (x - 1)\,p_{\alpha\mathbf{P}_1}(x) .$ Comparing the first with $p_{\mathbf{P}}(x) = (x - 1)(x - \mu_2)\cdots(x - \mu_n)$ and canceling the nonzero factor $x - 1$ (in $\mathbb{C}[x]$ , a product of nonzero polynomials is nonzero) gives $p_{\mathbf{P}_1}(x) = (x - \mu_2)\cdots(x - \mu_n)$ . If $\alpha > 0$ , then $\begin{aligned} p_{\alpha\mathbf{P}_1}(x) &= \det(x\mathbf{I} - \alpha\mathbf{P}_1) = \alpha^{n-1}\det\bigl(\tfrac{x}{\alpha}\mathbf{I} - \mathbf{P}_1\bigr) \\ &= \alpha^{n-1}\prod_{j=2}^{n}\Bigl(\frac{x}{\alpha} - \mu_j\Bigr) = \prod_{j=2}^{n}(x - \alpha\mu_j) , \end{aligned}$ where the second step takes the factor $\alpha$ out of each of the $n - 1$ rows. If $\alpha = 0$ , then $p_{\alpha\mathbf{P}_1}(x) = \det(x\mathbf{I}) = x^{n-1} = \prod_j(x - 0\cdot\mu_j)$ . Either way the formula for $p_{\mathbf{G}}$ follows.

For the last sentence, each $\mu_j$ is an eigenvalue of $\mathbf{P}$ , so $\lvert\mu_j\rvert \le \rho(\mathbf{P}) \le \left\| \mathbf{P} \right\|_1 = 1$ by Theorem 16.4.1 (a) and Theorem 16.3.3 (a). The eigenvalues of $\mathbf{G}$ are the roots of $p_{\mathbf{G}}$ : the number $1$ and the $\alpha\mu_j$ , each of modulus at most $\alpha$ . If $\alpha < 1$ , none of the $\alpha\mu_j$ equals $1$ , so every eigenvalue $\lambda \ne 1$ is some $\alpha\mu_j$ , and $\lvert\lambda\rvert \le \alpha$ . This proves the theorem.

The theorem gives more than a bound. It shows again that $1$ is a simple eigenvalue of $\mathbf{G}$ when $\alpha < 1$ , without Perron’s theorem, and it says that the rest of the spectrum of $\mathbf{G}$ is the rest of the spectrum of $\mathbf{P}$ , shrunk by the factor $\alpha$ . The bound is attained whenever $\mathbf{P}$ itself has $1$ as a repeated eigenvalue, as for the two separate webs of Example (Three ways a web can fail to rank) (b) (Exercise C2), and whenever $\mathbf{P}$ has $-1$ as an eigenvalue, as in the Quick check. So for a web with two or more pieces that no link leaves, as large webs typically have, the second eigenvalue of $\mathbf{G}$ has modulus exactly $\alpha$ , and no better bound is possible.

19.8.5. How fast the iteration converges

The eigenvalue bound predicts that iterates approach $\boldsymbol{\uppi}$ at a rate like $\alpha^k$ . For this particular matrix the prediction can be proved directly, with an explicit constant, by measuring errors in the $1$ -norm of Chapter 16.

Proposition 19.8.3 (Convergence at the Damping Rate)

Let $\mathbf{P}$ , $\alpha$ , $\mathbf{G}$ and $\boldsymbol{\uppi}$ be as in Theorem 19.8.1, let $\mathbf{x}_0$ be any probability vector, and let $\mathbf{x}_k = \mathbf{G}^k\mathbf{x}_0$ . Then for every $k \ge 0$ , $\left\| \mathbf{x}_k - \boldsymbol{\uppi} \right\|_1 \le \alpha^k\left\| \mathbf{x}_0 - \boldsymbol{\uppi} \right\|_1 \le 2\alpha^k .$ In particular, $\mathbf{x}_k \to \boldsymbol{\uppi}$ entrywise.

Idea. The error $\boldsymbol{\upepsilon}_k = \mathbf{x}_k - \boldsymbol{\uppi}$ is a difference of probability vectors, so its entries add up to $0$ , and the teleportation term kills it. What remains is $\alpha\mathbf{P}$ , and a stochastic matrix never increases the $1$ -norm.

Proof. Each $\mathbf{x}_k$ is a probability vector by Proposition 9.11.3 (a), since $\mathbf{G}$ is stochastic. Put $\boldsymbol{\upepsilon}_k = \mathbf{x}_k - \boldsymbol{\uppi}$ , so $\mathbf{1}^{\top}\boldsymbol{\upepsilon}_k = 1 - 1 = 0$ . Since $\mathbf{G}\boldsymbol{\uppi} = \boldsymbol{\uppi}$ , $\boldsymbol{\upepsilon}_{k+1} = \mathbf{G}\mathbf{x}_k - \mathbf{G}\boldsymbol{\uppi} = \mathbf{G}\boldsymbol{\upepsilon}_k = \alpha\mathbf{P}\boldsymbol{\upepsilon}_k + \frac{1 - \alpha}{n}\,\mathbf{1}(\mathbf{1}^{\top}\boldsymbol{\upepsilon}_k) = \alpha\mathbf{P}\boldsymbol{\upepsilon}_k .$ By Theorem 16.3.3 (a), $\left\| \mathbf{P} \right\|_1 = 1$ , the largest column sum of the nonnegative matrix $\mathbf{P}$ , so $\left\| \mathbf{P}\boldsymbol{\upepsilon}_k \right\|_1 \le \left\| \boldsymbol{\upepsilon}_k \right\|_1$ (Definition 16.3.2). Hence $\left\| \boldsymbol{\upepsilon}_{k+1} \right\|_1 \le \alpha\left\| \boldsymbol{\upepsilon}_k \right\|_1$ , and by induction on $k$ , $\left\| \boldsymbol{\upepsilon}_k \right\|_1 \le \alpha^k\left\| \boldsymbol{\upepsilon}_0 \right\|_1$ . Finally $\left\| \boldsymbol{\upepsilon}_0 \right\|_1 \le \left\| \mathbf{x}_0 \right\|_1 + \left\| \boldsymbol{\uppi} \right\|_1 = 2$ , as both are probability vectors. Each entry of $\boldsymbol{\upepsilon}_k$ has modulus at most $\left\| \boldsymbol{\upepsilon}_k \right\|_1 \le 2\alpha^k$ , and $\alpha^k \to 0$ because $0 < \alpha < 1$ , one of the calculus facts recorded in Chapter 9 §11. A sequence whose terms are at most $2\alpha^k$ in absolute value, with $2\alpha^k \to 0$ , tends to $0$ straight from the definition of a limit: once $2\alpha^k < \varepsilon$ , so is every such term. So $\mathbf{x}_k \to \boldsymbol{\uppi}$ entrywise.

The bound does not depend on the web at all: not on the number of pages, not on how they link. With $\alpha = 0.85$ , fifty steps guarantee $\left\| \mathbf{x}_{50} - \boldsymbol{\uppi} \right\|_1 \le 2(0.85)^{50} < 6 \cdot 10^{-4}$ , and ninety guarantee an error below $10^{-6}$ , for a web of any size. Each step is cheap, because $\mathbf{G}$ is never formed: by the proof of Theorem 19.8.1 (c), $\mathbf{G}\mathbf{x} = \alpha\mathbf{P}\mathbf{x} + \frac{1-\alpha}{n}\mathbf{1}$ for a probability vector $\mathbf{x}$ , and $\mathbf{P}\mathbf{x}$ needs one operation per link, plus one shared correction for the dangling pages.

In the language of §05, $\mathbf{G}$ is primitive (Definition 19.5.1), since $\mathbf{G}^1$ is already positive, and Theorem 19.5.2 gives $\mathbf{G}^k \to \boldsymbol{\uppi}\mathbf{1}^{\top}$ , with right Perron vector $\boldsymbol{\uppi}$ and left Perron vector $\mathbf{1}$ , normalized by $\mathbf{1}^{\top}\boldsymbol{\uppi} = 1$ . The proposition adds the rate, and the rate is what makes the method practical. The iteration $\mathbf{x}_{k+1} = \mathbf{G}\mathbf{x}_k$ is the power method; Chapter 24 studies it for general matrices, where the rate is governed by the ratio of the two largest eigenvalue moduli, here at most $\alpha$ .

19.8.6. A small web, exactly

Example (Four pages, one dangling)

A web has four pages. Page $1$ links to pages $2$ and $3$ ; page $2$ links to pages $3$ and $4$ ; page $3$ links to page $1$ ; page $4$ is dangling. With $\alpha = \tfrac45$ , find the Google matrix, the PageRank vector, and the ranking, and compare $\lvert\lambda_2\rvert$ with $\alpha$ .

Solution. The link matrix. Pages $1$ and $2$ have out-degree $2$ , page $3$ has out-degree $1$ , and page $4$ is dangling, so by Definition 19.8.1 $\mathbf{P} = \begin{pmatrix} 0 & 0 & 1 & \tfrac14 \\ \tfrac12 & 0 & 0 & \tfrac14 \\ \tfrac12 & \tfrac12 & 0 & \tfrac14 \\ 0 & \tfrac12 & 0 & \tfrac14 \end{pmatrix} , \qquad 20\,\mathbf{G} = 16\,\mathbf{P} + \mathbf{J} = \begin{pmatrix} 1 & 1 & 17 & 5 \\ 9 & 1 & 1 & 5 \\ 9 & 9 & 1 & 5 \\ 1 & 9 & 1 & 5 \end{pmatrix} ,$ since $20\alpha = 16$ and $20 \cdot \frac{1-\alpha}{4} = 1$ . Every column of $20\mathbf{G}$ adds up to $20$ , and every entry is positive.

The linear system. By Theorem 19.8.1 (c), $(\mathbf{I} - \tfrac45\mathbf{P})\boldsymbol{\uppi} = \tfrac1{20}\mathbf{1}$ . Multiplying by $5$ gives $(5\mathbf{I} - 4\mathbf{P})\boldsymbol{\uppi} = \tfrac14\mathbf{1}$ , that is, $\begin{aligned} 5\pi_1 - 4\pi_3 - \pi_4 &= \tfrac14 , &\qquad -2\pi_1 + 5\pi_2 - \pi_4 &= \tfrac14 , \\ -2\pi_1 - 2\pi_2 + 5\pi_3 - \pi_4 &= \tfrac14 , &\qquad -2\pi_2 + 4\pi_4 &= \tfrac14 . \end{aligned}$ Express everything through $\pi_4$ . The fourth equation gives $\pi_2 = 2\pi_4 - \tfrac18$ . The second then gives $2\pi_1 = 5\pi_2 - \pi_4 - \tfrac14 = 9\pi_4 - \tfrac78$ , so $\pi_1 = \tfrac92\pi_4 - \tfrac7{16}$ . The first gives $4\pi_3 = 5\pi_1 - \pi_4 - \tfrac14 = \tfrac{43}{2}\pi_4 - \tfrac{39}{16}$ , so $\pi_3 = \tfrac{43}{8}\pi_4 - \tfrac{39}{64}$ . Substituting into the third, $\Bigl(-9 - 4 + \tfrac{215}{8} - 1\Bigr)\pi_4 + \Bigl(\tfrac78 + \tfrac14 - \tfrac{195}{64}\Bigr) = \tfrac{103}{8}\pi_4 - \tfrac{123}{64} = \tfrac14 ,$ so $\tfrac{103}{8}\pi_4 = \tfrac{139}{64}$ and $\pi_4 = \tfrac{139}{824}$ . Back-substituting, $\boldsymbol{\uppi} = \frac{1}{824}\,(265,\ 175,\ 245,\ 139) .$ Check. The entries add up to $824/824 = 1$ , as they must. With $\mathbf{y} = (265, 175, 245, 139)$ , the first row of $20\mathbf{G}$ gives $265 + 175 + 17 \cdot 245 + 5 \cdot 139 = 5300 = 20 \cdot 265$ , and the other rows give $3500 = 20 \cdot 175$ , $4900 = 20 \cdot 245$ and $2780 = 20 \cdot 139$ . So $\mathbf{G}\boldsymbol{\uppi} = \boldsymbol{\uppi}$ .

The ranking. Page $1$ first ( $\approx 0.322$ ), then page $3$ ( $\approx 0.297$ ), page $2$ ( $\approx 0.212$ ) and page $4$ ( $\approx 0.169$ ). Page $3$ is linked from pages $1$ and $2$ , while the dangling page $4$ feeds every page equally; page $1$ is linked only from page $3$ . Yet page $1$ wins, because page $3$ passes its whole weight to it, while pages $1$ , $2$ and $4$ split theirs.

The second eigenvalue. Expanding the determinant gives $\begin{aligned} p_{\mathbf{P}}(x) &= (x - 1)\Bigl(x^3 + \tfrac34x^2 + \tfrac18x - \tfrac1{16}\Bigr) , \\ p_{\mathbf{G}}(x) &= (x - 1)\Bigl(x^3 + \tfrac35x^2 + \tfrac{2}{25}x - \tfrac{4}{125}\Bigr) , \end{aligned}$ and the second cubic is $\alpha^3$ times the first evaluated at $x/\alpha$ , as Theorem 19.8.2 predicts: $\tfrac34 \cdot \tfrac45 = \tfrac35$ , $\tfrac18 \cdot \tfrac{16}{25} = \tfrac{2}{25}$ , $\tfrac1{16} \cdot \tfrac{64}{125} = \tfrac{4}{125}$ . The cubic for $\mathbf{P}$ has one real root near $0.199$ and two complex ones of modulus about $0.560$ . So $\lvert\lambda_2(\mathbf{G})\rvert \approx 0.8 \times 0.560 \approx 0.448$ , comfortably below $\alpha = 0.8$ : for this web the iteration converges faster than Proposition 19.8.3 guarantees.

19.8.7. Exercises

A. Check your understanding

Exercise (A1)

(a) Define the Google matrix of a web and its PageRank vector.
(b) Why is every entry of $\mathbf{G}$ positive, and which three conclusions does Theorem 19.1.5 then give?
(c) True or false: with $\alpha = 1$ , every web has exactly one PageRank vector. Justify your answer.
(d) True or false: the page with the most incoming links always has the highest PageRank. Justify your answer.
(e) For $\alpha = 0.85$ , what does Theorem 19.8.2 say about the eigenvalues of $\mathbf{G}$ other than $1$ ? Can the bound be improved for every web?
(f) True or false: after $10$ steps of $\mathbf{x}_{k+1} = \mathbf{G}\mathbf{x}_k$ from any probability vector, $\left\| \mathbf{x}_{10} - \boldsymbol{\uppi} \right\|_1 \le 2\alpha^{10}$ . Justify your answer.

Solution.

(a) For a web with link matrix $\mathbf{P}$ (Definition 19.8.1) and $0 < \alpha < 1$ , $\mathbf{G} = \alpha\mathbf{P} + \frac{1-\alpha}{n}\mathbf{J}$ . A PageRank vector is a probability vector $\boldsymbol{\uppi}$ with $\mathbf{G}\boldsymbol{\uppi} = \boldsymbol{\uppi}$ .
(b) $\alpha\mathbf{P}$ has nonnegative entries and $\frac{1-\alpha}{n}\mathbf{J}$ has every entry equal to $\frac{1-\alpha}{n} > 0$ , since $\alpha < 1$ . Perron’s theorem then gives: $\rho(\mathbf{G})$ is an eigenvalue of algebraic multiplicity one; it has an eigenvector with all entries positive; every other eigenvalue has modulus strictly less than $\rho(\mathbf{G})$ . Here $\rho(\mathbf{G}) = 1$ .
(c) False. With $\alpha = 1$ , $\mathbf{G} = \mathbf{P}$ , and for two pairs of pages linking only to each other, Example (Three ways a web can fail to rank) (b) gives two different steady states.
(d) False. In Example (Four pages, one dangling), page $3$ has the most incoming links, but page $1$ ranks first.
(e) Every eigenvalue $\lambda \ne 1$ has $\lvert\lambda\rvert \le 0.85$ . The bound cannot be improved for every web: when the link matrix has $-1$ or a repeated $1$ among its eigenvalues, $\mathbf{G}$ has an eigenvalue of modulus exactly $0.85$ (the Quick check, and Exercise C2).
(f) True, by Proposition 19.8.3 with $k = 10$ .

B. Practice

Exercise (B1: A three-page web)

For the three-page web after Definition 19.8.1 (page $1$ links to pages $2$ and $3$ , page $2$ to page $3$ , page $3$ is dangling), with $\alpha = \tfrac12$ , find the PageRank vector by solving the system of Theorem 19.8.1 (c). Hence rank the pages.

Solution. With $\mathbf{P}$ as in the text, $(\mathbf{I} - \tfrac12\mathbf{P})\boldsymbol{\uppi} = \tfrac16\mathbf{1}$ . Multiplying by $12$ gives $(12\mathbf{I} - 6\mathbf{P})\boldsymbol{\uppi} = 2\,\mathbf{1}$ : $\begin{aligned} 12\pi_1 - 2\pi_3 &= 2 , \\ -3\pi_1 + 12\pi_2 - 2\pi_3 &= 2 , \\ -3\pi_1 - 6\pi_2 + 10\pi_3 &= 2 . \end{aligned}$ The first gives $\pi_3 = 6\pi_1 - 1$ . The second becomes $-3\pi_1 + 12\pi_2 - 12\pi_1 + 2 = 2$ , so $\pi_2 = \tfrac54\pi_1$ . The third becomes $-3\pi_1 - \tfrac{15}{2}\pi_1 + 60\pi_1 - 10 = 2$ , so $\tfrac{99}{2}\pi_1 = 12$ and $\pi_1 = \tfrac{8}{33}$ . Then $\pi_2 = \tfrac{10}{33}$ and $\pi_3 = \tfrac{48}{33} - 1 = \tfrac{15}{33}$ . So $\boldsymbol{\uppi} = \frac{1}{33}(8,\ 10,\ 15) ,$ whose entries add up to $1$ . Check against the original system: $12 \cdot 8 - 2 \cdot 15 = 66 = 2 \cdot 33$ , $-24 + 120 - 30 = 66$ , $-24 - 60 + 150 = 66$ . Hence page $3$ ranks first, then page $2$ , then page $1$ .

Exercise (B2: A cycle of three pages)

Three pages link in a cycle: $1$ to $2$ , $2$ to $3$ , $3$ to $1$ . Let $0 < \alpha < 1$ .

(a) Write down $\mathbf{P}$ and show that $p_{\mathbf{P}}(x) = x^3 - 1$ .
(b) Use Theorem 19.8.2 to find the eigenvalues of $\mathbf{G}$ , and check your answer against $\operatorname{tr}\mathbf{G}$ .
(c) Find $\boldsymbol{\uppi}$ , and explain why the bound of Theorem 19.8.2 is attained.

Solution.

(a) Column $j$ of $\mathbf{P}$ is $\mathbf{e}_{j+1}$ , with $\mathbf{e}_4$ read as $\mathbf{e}_1$ : $\begin{aligned} \mathbf{P} &= \begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} , \qquad \det(x\mathbf{I} - \mathbf{P}) = \det\begin{pmatrix} x & 0 & -1 \\ -1 & x & 0 \\ 0 & -1 & x \end{pmatrix} \\ &= x \cdot x^2 + (-1)\cdot\bigl((-1)(-1) - x \cdot 0\bigr) = x^3 - 1 , \end{aligned}$ expanding along the first row.
(b) $x^3 - 1 = (x - 1)(x - \omega)(x - \conj\omega)$ with $\omega = -\tfrac12 + \tfrac{\sqrt3}{2}i$ , so $\mu_2 = \omega$ , $\mu_3 = \conj\omega$ , and the eigenvalues of $\mathbf{G}$ are $1, \alpha\omega, \alpha\conj\omega$ . Their sum is $1 + \alpha(\omega + \conj\omega) = 1 - \alpha$ . Directly, $\operatorname{tr}\mathbf{G} = \alpha\operatorname{tr}\mathbf{P} + \frac{1-\alpha}{3}\operatorname{tr}\mathbf{J} = 0 + (1 - \alpha)$ , which agrees (Theorem 9.3.3).
(c) $\mathbf{P}\mathbf{1} = \mathbf{1}$ and $\mathbf{J}\mathbf{1} = 3\,\mathbf{1}$ , so $\mathbf{G}\mathbf{1} = \alpha\mathbf{1} + (1 - \alpha)\mathbf{1} = \mathbf{1}$ , and $\boldsymbol{\uppi} = \tfrac13\mathbf{1}$ by the uniqueness in Theorem 19.8.1. The eigenvalues $\alpha\omega$ and $\alpha\conj\omega$ have modulus $\alpha\lvert\omega\rvert = \alpha$ , so the bound $\lvert\lambda\rvert \le \alpha$ holds with equality.

Exercise (B3: Personalized jumps)

Let $\mathbf{P} \in M_n(\mathbb{R})$ be stochastic, $0 < \alpha < 1$ , and let $\mathbf{v}$ be a probability vector with every $v_i > 0$ . Put $\mathbf{G}_{\mathbf{v}} = \alpha\mathbf{P} + (1 - \alpha)\mathbf{v}\mathbf{1}^{\top}$ : the surfer now jumps to page $i$ with probability $v_i$ .

(a) Prove that $\mathbf{G}_{\mathbf{v}}$ is stochastic and positive, and deduce that it has exactly one probability vector $\boldsymbol{\uppi}$ with $\mathbf{G}_{\mathbf{v}}\boldsymbol{\uppi} = \boldsymbol{\uppi}$ , and that $\boldsymbol{\uppi} > \mathbf{0}$ .
(b) Prove that $\boldsymbol{\uppi}$ is the unique solution of $(\mathbf{I} - \alpha\mathbf{P})\boldsymbol{\uppi} = (1 - \alpha)\mathbf{v}$ .
(c) For two pages linking to each other, $\alpha = \tfrac12$ and $\mathbf{v} = (\tfrac34, \tfrac14)$ , find $\boldsymbol{\uppi}$ .

Solution.

(a) The entries of $\mathbf{G}_{\mathbf{v}}$ are $\alpha p_{ij} + (1 - \alpha)v_i \ge (1 - \alpha)v_i > 0$ . Column $j$ adds up to $\alpha + (1 - \alpha)\mathbf{1}^{\top}\mathbf{v} = \alpha + 1 - \alpha = 1$ . So $\mathbf{G}_{\mathbf{v}}$ is stochastic and positive. The proof of Theorem 19.8.1 (a) and (b) used only these two facts, so it applies word for word: $\rho(\mathbf{G}_{\mathbf{v}}) = 1$ is an eigenvalue of algebraic multiplicity one with a positive eigenvector, and its normalization $\boldsymbol{\uppi}$ is the only probability vector fixed by $\mathbf{G}_{\mathbf{v}}$ .
(b) For a probability vector $\mathbf{x}$ , $\mathbf{G}_{\mathbf{v}}\mathbf{x} = \alpha\mathbf{P}\mathbf{x} + (1 - \alpha)\mathbf{v}(\mathbf{1}^{\top}\mathbf{x}) = \alpha\mathbf{P}\mathbf{x} + (1 - \alpha)\mathbf{v}$ , so $\mathbf{G}_{\mathbf{v}}\boldsymbol{\uppi} = \boldsymbol{\uppi}$ says $(\mathbf{I} - \alpha\mathbf{P})\boldsymbol{\uppi} = (1 - \alpha)\mathbf{v}$ . The matrix $\mathbf{I} - \alpha\mathbf{P}$ is invertible, as in the proof of Theorem 19.8.1 (c), so the solution is unique.
(c) $\mathbf{P}$ is the swap, and the system is $\pi_1 - \tfrac12\pi_2 = \tfrac38$ , $-\tfrac12\pi_1 + \pi_2 = \tfrac18$ . The first gives $\pi_1 = \tfrac38 + \tfrac12\pi_2$ , and the second becomes $-\tfrac3{16} + \tfrac34\pi_2 = \tfrac18$ , so $\pi_2 = \tfrac{5}{12}$ and $\pi_1 = \tfrac38 + \tfrac5{24} = \tfrac{7}{12}$ . So $\boldsymbol{\uppi} = (\tfrac7{12}, \tfrac5{12})$ : the preferred page $1$ gains, but less than its jump weight $\tfrac34$ , because half the time the surfer follows the link to page $2$ .

C. Going deeper

Exercise (C1: PageRank as a sum over paths)

Let $\mathbf{P}$ , $\alpha$ , $\mathbf{G}$ and $\boldsymbol{\uppi}$ be as in Theorem 19.8.1.

(a) Prove that $\displaystyle \boldsymbol{\uppi} = \frac{1 - \alpha}{n}\sum_{k=0}^{\infty}\alpha^k\mathbf{P}^k\mathbf{1}$ .
(b) Deduce that $\pi_i \ge \frac{1-\alpha}{n}$ for every $i$ .
(c) Suppose no page is dangling and no page links to page $i$ . Prove that $\pi_i = \frac{1-\alpha}{n}$ exactly.

Hint for (a): Theorem 16.5.1 with the $1$ -norm.

Solution.

(a) By Theorem 16.3.3 (a), $\left\| \alpha\mathbf{P} \right\|_1 = \alpha\left\| \mathbf{P} \right\|_1 = \alpha < 1$ , the largest column sum of $\alpha\mathbf{P}$ . By Theorem 16.5.1 (a), $\mathbf{I} - \alpha\mathbf{P}$ is invertible and $(\mathbf{I} - \alpha\mathbf{P})^{-1} = \sum_{k \ge 0}\alpha^k\mathbf{P}^k$ . By Theorem 19.8.1 (c), $\boldsymbol{\uppi} = \frac{1-\alpha}{n}(\mathbf{I} - \alpha\mathbf{P})^{-1}\mathbf{1}$ , which is the stated series.
(b) Every term $\alpha^k\mathbf{P}^k\mathbf{1}$ has nonnegative entries, and the term $k = 0$ is $\mathbf{1}$ . So each entry of the sum is at least $1$ , since a limit of partial sums that are all at least $1$ is at least $1$ , and $\pi_i \ge \frac{1-\alpha}{n}$ .
(c) From $\mathbf{G}\boldsymbol{\uppi} = \boldsymbol{\uppi}$ and the proof of Theorem 19.8.1 (c), $\boldsymbol{\uppi} = \alpha\mathbf{P}\boldsymbol{\uppi} + \frac{1-\alpha}{n}\mathbf{1}$ . Row $i$ of $\mathbf{P}$ is zero: $p_{ij} \ne 0$ only if page $j$ links to page $i$ or page $j$ is dangling, and neither happens. So $(\mathbf{P}\boldsymbol{\uppi})_i = 0$ and $\pi_i = \frac{1-\alpha}{n}$ , the smallest possible value by (b).

Exercise (C2: When the bound is attained)

Let $\mathbf{P} \in M_n(\mathbb{R})$ be stochastic, $0 < \alpha < 1$ , and $\mathbf{G} = \alpha\mathbf{P} + \frac{1-\alpha}{n}\mathbf{J}$ .

(a) Suppose $\mathbf{P}$ has two different steady states $\mathbf{u} \ne \mathbf{w}$ . Prove that $\mathbf{G}(\mathbf{u} - \mathbf{w}) = \alpha(\mathbf{u} - \mathbf{w})$ , so that $\alpha$ is an eigenvalue of $\mathbf{G}$ .
(b) For the web of Example (Three ways a web can fail to rank) (b), find all eigenvalues of $\mathbf{G}$ , with multiplicity, and check your answer against (a).

Solution.

(a) Put $\mathbf{z} = \mathbf{u} - \mathbf{w} \ne \mathbf{0}$ . Both are probability vectors, so $\mathbf{1}^{\top}\mathbf{z} = 0$ and $\mathbf{J}\mathbf{z} = \mathbf{1}(\mathbf{1}^{\top}\mathbf{z}) = \mathbf{0}$ . Hence $\mathbf{G}\mathbf{z} = \alpha\mathbf{P}\mathbf{u} - \alpha\mathbf{P}\mathbf{w} + \mathbf{0} = \alpha(\mathbf{u} - \mathbf{w}) = \alpha\mathbf{z}$ , and $\alpha$ is an eigenvalue of $\mathbf{G}$ with eigenvector $\mathbf{z}$ .
(b) $\mathbf{P}$ is block diagonal with two blocks $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ , each with characteristic polynomial $x^2 - 1$ , so $p_{\mathbf{P}}(x) = (x^2 - 1)^2 = (x - 1)(x - 1)(x + 1)(x + 1)$ by Theorem 7.8.4. By Theorem 19.8.2, with $\mu_2 = 1$ and $\mu_3 = \mu_4 = -1$ , the eigenvalues of $\mathbf{G}$ are $1, \alpha, -\alpha, -\alpha$ . The eigenvalue $\alpha$ is the one found in (a), with $\mathbf{u} = (\tfrac12, \tfrac12, 0, 0)$ , $\mathbf{w} = (0, 0, \tfrac12, \tfrac12)$ and eigenvector $\mathbf{z} = \tfrac12(1, 1, -1, -1)$ ; indeed $\mathbf{P}\mathbf{z} = \mathbf{z}$ and $\mathbf{J}\mathbf{z} = \mathbf{0}$ , so $\mathbf{G}\mathbf{z} = \alpha\mathbf{z}$ .