\( \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.2 · Diagonalization and matrix powers

A free, illustrated module of 4 lessons and one interactive in M03 Linear Algebra II: Decompositions: A = P D P inverse; Powers through the eigenbasis; Fibonacci and linear recurrences; The power method.

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

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

A matrix with enough eigenvectors comes apart as A = P D P inverse: change to the grid of its eigenvectors, stretch along each one, change back. These four lessons derive that factorisation column by column, use it to raise matrices to any power and to read their long run off the eigenvalues, turn the Fibonacci numbers into a matrix power with a closed formula, and build the power method, the multiply-and-rescale algorithm behind PageRank.

What you need first. Eigenvalues, eigenvectors, the characteristic polynomial and complex eigenvalues (M03.1), change of basis and the matrix of a map in a new basis (M02.9), matrix products and the inverse of a 2 by 2 matrix (M02.5, M02.7), and NumPy arrays (P02).

Lessons

1. A = P D P inverse M03.2.1 25 min

   Put the eigenvectors of a matrix in the columns of P and its eigenvalues on the diagonal of D. Derive A P = P D column by column, so that A = P D P inverse, work it by hand for the running matrix, and see which matrices cannot be taken apart this way.

2. Powers through the eigenbasis M03.2.2 25 min

   Raise a matrix to any power by raising its eigenvalues instead: derive A^k = P D^k P inverse, follow a vector’s eigen-coordinates as they grow or shrink, read the long-run behaviour off the eigenvalues, and compare the cost with repeated multiplication.

3. Fibonacci and linear recurrences M03.2.3 25 min

   Turn the Fibonacci rule into one matrix step on a pair of numbers, diagonalise the Fibonacci matrix, derive Binet’s formula from the eigen-expansion, and find the exact place where the formula fails in floating point.

4. The power method M03.2.4 25 min

   Find the dominant eigenvector of a matrix by multiplying and rescaling, again and again. Derive why it converges at the rate of the ratio of the two largest eigenvalues, estimate the eigenvalue with the Rayleigh quotient, and meet the three ways it fails.

The interactive

M03.2-X1 · Power stepper. Choose a matrix, drag a starting vector and apply the matrix again and again. Bars show the vector’s two eigen-coordinates growing or shrinking by their eigenvalues, and a switch turns the steps into the power method, with the angle to the dominant eigenvector in the read-out. It lives in Powers through the eigenbasis.