\( \newcommand{\vect}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\mat}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

M03.9 · Markov matrices, graphs and PageRank

A free, illustrated module of 4 lessons and one interactive in M03 Linear Algebra II: Decompositions: Markov matrices; Steady states and Perron-Frobenius; Graphs as matrices; PageRank.

M03.9 L2 · Intermediate 4 lessons · about 100 min Live · in review

Part of M03 Linear Algebra II: Decompositions in the Mathematics track.

A matrix whose rows are probabilities moves a distribution forward one step at a time, and its eigenvalue 1 holds the long run. These four lessons build the transition matrix of a Markov chain and prove why 1 is always an eigenvalue and nothing is larger, state the Perron-Frobenius theorem that makes the long run unique and show what breaks without it, turn graphs into adjacency and Laplacian matrices that count walks and find clusters, and put it all together in PageRank, the random surfer whose steady state ranks the pages of a web.

What you need first. Eigenvalues and diagonalisation (M03.1, M03.2), the power method (M03.2.4), the spectral theorem and semidefinite matrices (M03.3, M03.4), the max-norm of a matrix (M03.8.1), conditional probability (M06.3) and NumPy arrays (P02).

Lessons

1. Markov matrices M03.9.1 25 min

   A matrix whose rows are probabilities moves a distribution forward one step at a time. Build the transition matrix of a chain, prove that 1 is always an eigenvalue and that no eigenvalue is larger, and find the long run of a two-state chain by diagonalising.

2. Steady states and Perron-Frobenius M03.9.2 25 min

   When does a Markov chain have exactly one steady state, and reach it from every start? State the Perron-Frobenius theorem, see the second-largest eigenvalue set the speed, and work the two ways it fails: separate pieces and a chain that flips for ever.

3. Graphs as matrices M03.9.3 25 min

   Write a graph as its adjacency matrix and its powers count walks; write it as its Laplacian and the quadratic form adds up squared differences across edges. The zero eigenvalues count the pieces, and the second eigenvector cuts a graph into two clusters.

4. PageRank M03.9.4 25 min

   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.

The interactive

M03.9-X1 · Random surfer. Watch the probability of a random surfer flow round a four-page web one click at a time. Set the damping factor, switch links off and on, and read the distance from the steady state and the second-largest eigenvalue modulus that sets the speed. It lives in PageRank.