Linear Algebra for Engineers lecture 23: Markov Chains and PageRank

Overview

Alex Townsend connects linear algebra to Google PageRank by defining Markov chains as probability vectors repeatedly transformed by a column-stochastic matrix, then computing their steady states as normalized vectors in the null space of I minus A. A two-location jumping-spider example illustrates the calculation, while a four-page web graph shows how a steady-state distribution can rank pages by long-run visit probability; Townsend also reviews determinants and their use in calculating signed geometric areas and volumes.

Key takeaways

With column vectors, a stochastic transition matrix has probability vectors as columns, and multiplying A by the current distribution produces the next distribution.
A Markov chain's steady state solves A x = x, equivalently (I − A)x = 0, and must be normalized so its entries sum to 1.
In the two-location spider example, the transition probabilities yield a steady state of (1/3, 2/3), giving the long-run location probabilities.
PageRank models a random surfer who follows outgoing hyperlinks; the stationary probability of visiting a page supplies its rank.
A page's importance depends on the influence of pages linking to it, not merely on its raw number of incoming links.
Determinants provide signed areas and volumes: a triangle's area is half the absolute determinant of its side vectors, while the determinant's sign preserves orientation.

Chapters

0:00 Larry Page, John Kleinberg, and Linear Algebra in Search

Larry Page co-founded Google, whose PageRank algorithm uses linear algebra to rank web pages.
John Kleinberg developed a mathematically related page-ranking algorithm used by Ask Jeeves, though Townsend notes it was harder to scale to the full internet.
Townsend frames PageRank as an application developed across the next lectures.

3:20 Permutation Matrices Explain Why Transposition Preserves Determinants

A permutation matrix is formed by reordering the rows of the identity matrix, as in the row swaps used in PA = LU.
Each row swap changes a determinant's sign; the example permutation matrix takes two swaps, so its determinant is 1.
For permutation matrices, row swaps correspond to column swaps, helping explain why det(A) = det(Aᵀ).

9:00 Use Determinants to Calculate Triangle Areas and Signed Volumes

For a 2×2 matrix, ad − bc gives the signed area of the parallelogram spanned by its column vectors.
To find a triangle's area, use vectors along its sides rather than its absolute coordinates, then take half the parallelogram area.
The example produces signed area −3, so the triangle's ordinary area is 3; the sign records orientation.
Triangulating polygons and decomposing 3D shapes into tetrahedra extends the determinant method to computational geometry.

17:45 Probability Vectors and Column-Stochastic Matrices

A probability vector has nonnegative entries that sum to 1, such as (1/3, 1/3, 1/3) or (1/2, 1/2, 0).
A stochastic matrix is square and has probability vectors as its columns, so every column sums to 1.
Under Townsend's column-vector convention, each matrix column describes the outcome distribution after starting in one particular state.

22:00 Define Markov Chains with the Jumping-Spider Example

A Markov chain is a sequence of probability vectors linked by a stochastic transition matrix A, with xₖ₊₁ = A xₖ.
In the two-location spider example, the transition probabilities are 0.6 and 0.4 from location one, and 0.2 and 0.8 from location two.
Starting from either location's basis vector reveals the corresponding column of A; repeated multiplication generates the spider's probability distribution over time.

29:00 A Markov Chain's Steady State Is an Eigenvector

A steady state is a probability vector x that remains unchanged after a transition: A x = x.
If the chain reaches x, every later distribution remains x because applying A again leaves it unchanged.
For the jumping spider, the steady state describes the long-run probabilities of finding it at each of the two locations.

32:25 Find the Spider's Steady State from the Null Space of I − A

Rearranging A x = x gives (I − A)x = 0, so steady states lie in the null space of I − A.
For the spider matrix with columns (0.6, 0.4) and (0.2, 0.8), row reduction gives a null-space direction proportional to (1/2, 1).
Normalizing the entries to sum to 1 gives the probability vector (1/3, 2/3).
The spider therefore spends one-third of the long run at location one and two-thirds at location two.

42:10 Model a Four-Page Website as a Random-Surfer Markov Chain

Townsend represents four web pages as four states connected by directed hyperlinks, including links that do not have a reverse link.
A random surfer at each page chooses uniformly among its outgoing links; three links from page one each receive probability 1/3.
Each transition-matrix column records where the surfer goes after starting from its corresponding page.

45:20 Build the PageRank Transition Matrix from Web Links

The four-page example uses a 4×4 stochastic matrix whose columns encode the link choices from pages one through four.
From page two, the surfer moves to pages three and four with probability 1/2 each; from page three, the only link goes to page one.
From page four, the surfer moves to page one or page three with probability 1/2 each, completing the transition model.

48:20 Rank Pages by Steady-State Visits and Address Ranking Ambiguity

The example's steady-state probabilities have numerators that sum to 31; normalizing them yields the page ranking 1, then 3, then 4, then 2.
Long-run visit probability captures not just the number of incoming links but also how influential the linking pages are.
Some link structures may not produce a unique steady-state ranking; Townsend previews Google's teleportation idea as a way to address this issue.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Alex Townsend.