Chapter 7
Matrices
A graph written as a matrix is a linear recurrence in disguise. Multiply it by itself log k times and you have counted every walk of length k — or computed the number of spanning trees with a determinant.
4 pages2,764 words7 problems0 interactive
1Adjacency, Incidence and LaplacianThree matrices for one graph, what each row/column product means, and the properties you can read off in O(1).2Counting Walks with Matrix PowersA^k counts walks, and the trick of exponentiating a graph's matrix solves "in exactly k steps" problems in O(n³ log k).3The Matrix–Tree TheoremCounting spanning trees with a determinant — plus Gaussian elimination mod p, which is the algorithm you actually type.4Linear Recurrences from Graphs and MatricesTurn a DP with constant-size state into a matrix, exponentiate, and answer n = 10^18 questions.