Diagonalisation and matrix powers

Apply one matrix again and again. Watch a ring of points flatten onto a single line while it grows.

Along the eigenvectors, a step is a number

A matrix step mixes the coordinates of a point, and doing it ten times by hand is tedious. Along an eigenvector it is easy: the matrix only stretches. So split the point into eigenvector parts first.

Take $\mathbf{A}=\begin{bmatrix}1.5&1\\0.5&1\end{bmatrix}$, with $\mathbf{A}(2,1)=2\,(2,1)$ and $\mathbf{A}(1,-1)=0.5\,(1,-1)$, as on Finding eigenvalues. The point $(1,0)$ splits as

Each step doubles the first part and halves the second. After $k$ steps:

Here $\mathbf{A}^k$ means $\mathbf{A}$ applied $k$ times, the matrix product $\mathbf{A}\mathbf{A}\cdots\mathbf{A}$. After 10 steps the first part has grown by $2^{10}=1024$ and the second has shrunk by $0.5^{10}\approx0.001$. Almost nothing is left off the line of $(2,1)$. That is what the picture shows: the direction settles within a handful of steps, while the length keeps doubling.

In general, if $\mathbf{x}=c_1\mathbf{v}_1+\dots+c_n\mathbf{v}_n$ along eigenvectors, then

Provided its coefficient is not 0, the eigenvalue largest in size wins in the long run.

Diagonalising

Put the eigenvectors side by side as the columns of a matrix $\mathbf{X}$, and the eigenvalues on the diagonal of a matrix $\boldsymbol{\Lambda}$ (capital lambda), with zeros elsewhere:

$\mathbf{A}$ times each column of $\mathbf{X}$ is that column times its eigenvalue. Written for both columns at once:

If the eigenvectors are independent, $\mathbf{X}$ has an inverse, as in The inverse matrix. Multiply on the right by $\mathbf{X}^{-1}$:

This is diagonalising $\mathbf{A}$. Read it right to left as three steps: $\mathbf{X}^{-1}$ finds the eigenvector parts of a point, $\boldsymbol{\Lambda}$ stretches each part, and $\mathbf{X}$ puts the parts back together. Check it with numbers. Here $\mathbf{X}^{-1}=\tfrac13\begin{bmatrix}1&1\\1&-2\end{bmatrix}$ and $\mathbf{X}\boldsymbol{\Lambda}=\begin{bmatrix}4&0.5\\2&-0.5\end{bmatrix}$, so

Powers

Now square it. The inner $\mathbf{X}^{-1}\mathbf{X}$ cancels:

Every further step cancels the same way, so $\mathbf{A}^k=\mathbf{X}\boldsymbol{\Lambda}^k\mathbf{X}^{-1}$. The power of a diagonal matrix is easy: raise each diagonal entry to the power $k$.

There is a tidy way to write the answer. Let $\mathbf{P}_1=\tfrac13\begin{bmatrix}2&2\\1&1\end{bmatrix}$, the matrix that keeps the $(2,1)$ part of a point and drops the $(1,-1)$ part, and $\mathbf{P}_2=\mathbf{I}-\mathbf{P}_1$, which does the opposite. (These are projections, not the permutation matrices of Transposes and permutations. They are slanted projections: they drop along the other eigenvector, not at a right angle, so unlike those of Projections they are not symmetric.) Then

For $k=2$ this gives $4\mathbf{P}_1+0.25\mathbf{P}_2=\begin{bmatrix}2.75&2.5\\1.25&1.5\end{bmatrix}$, as above. For $k=10$:

Both columns are almost exactly $341.33\,(2,1)$: after ten steps, every point has been sent onto the line of $(2,1)$.

Fibonacci

The Fibonacci numbers $0,1,1,2,3,5,8,\dots$ add the last two to get the next: $F_{k+1}=F_k+F_{k-1}$. Keep the last two as a vector, and one step is a matrix:

Its trace is 1 and its determinant $-1$, so its eigenvalues solve $\lambda^2-\lambda-1=0$:

On this page $\varphi$ is this number, the golden ratio, not a phase. Its eigenvector is $(\varphi,1)$: the matrix sends it to $(\varphi+1,\,\varphi)=(\varphi^2,\varphi)=\varphi\,(\varphi,1)$, because $\varphi^2=\varphi+1$. Splitting the start $(F_1,F_0)=(1,0)$ along the two eigenvectors gives the closed form

Since $\lvert\psi\rvert<1$, its power fades, and $F_k$ grows like $\varphi^k$.

Watch the arrows close in on the line. They swing from one side to the other because $\psi$ is negative, and the swing shrinks because its size is less than 1.

When it fails

Diagonalising needs $n$ independent eigenvectors, so that $\mathbf{X}$ has an inverse. Most matrices have them, but not all. The shear $\begin{bmatrix}1&1\\0&1\end{bmatrix}$ has the eigenvalue 1 twice and only one line of eigenvectors, through $(1,0)$. Any $\mathbf{X}$ built from its eigenvectors has two columns on one line, so it has no inverse, and the shear can’t be diagonalised. Similar matrices and the Jordan form shows what to use instead.

Worked example

1. Diagonalise. For $\mathbf{A}=\begin{bmatrix}1.5&1\\0.5&1\end{bmatrix}$: $\mathbf{X}=\begin{bmatrix}2&1\\1&-1\end{bmatrix}$, $\boldsymbol{\Lambda}=\begin{bmatrix}2&0\\0&0.5\end{bmatrix}$, $\mathbf{X}^{-1}=\tfrac13\begin{bmatrix}1&1\\1&-2\end{bmatrix}$, and $\mathbf{X}\boldsymbol{\Lambda}\mathbf{X}^{-1}=\mathbf{A}$.

2. Square it two ways. Directly, $\mathbf{A}^2$ has entries $2.25+0.5=2.75$, $1.5+1=2.5$, $0.75+0.5=1.25$ and $0.5+1=1.5$. By eigenvalues, $4\mathbf{P}_1+0.25\mathbf{P}_2$ gives the same matrix.

3. Ten Fibonacci steps. $\begin{bmatrix}1&1\\1&0\end{bmatrix}^{10}=\begin{bmatrix}89&55\\55&34\end{bmatrix}$, so $F_{10}=55$. The closed form agrees: $(122.9919-0.0081)/2.236068=55$. Twenty steps give $F_{20}=6765$, and $F_{21}/F_{20}=10946/6765=1.618034$, the golden ratio to six decimals.

4. Can it be diagonalised? The shear: no, one line of eigenvectors.

Try these before you read the answers.

• By what factor does the $(2,1)$ part grow in $\mathbf{A}^{10}$? $2^{10}=1024$.
• Does the $0.5^{10}$ part matter? It is about 0.001: almost nothing.
• A matrix has eigenvalues 0.9 and 0.5. Do its powers die out? Yes: both parts shrink every step.
• After many steps from $(1,0)$, which way does $\mathbf{A}^k(1,0)$ point? Along $(2,1)$, at 26.57°, which is 0.4636 radians.

Where you’ll meet this

Stability. Any system updated by $\mathbf{x}_{k+1}=\mathbf{A}\mathbf{x}_k$ settles to zero exactly when every eigenvalue has size less than 1. The largest size is called the spectral radius; a filter is stable when its companion matrix has spectral radius below 1.

Growth rates. A recursion like Fibonacci’s grows by its largest eigenvalue each step: $\varphi\approx1.618$ for Fibonacci.

Long-run behaviour. Populations moving between places, and the chances of a random process being in each state, follow $\mathbf{u}_{k+1}=\mathbf{M}\mathbf{u}_k$. Markov matrices uses this page to find where they end up.

Reference card