Diagonalization and Powers of A

The key formula: S⁻¹AS = Λ

Last lecture reached the key equation $A\mathbf{x} = \lambda\mathbf{x}$ and showed how to find the $\lambda$‘s and $\mathbf{x}$‘s. Job one is done. Now: what do we do with eigenvalues and eigenvectors once we have them? The good way to see that is to diagonalize the matrix.

Suppose $A$ has $n$ linearly independent eigenvectors $\mathbf{x}_1, \dots, \mathbf{x}_n$. Put them in the columns of a matrix $S$ — Strang naturally calls it the eigenvector matrix — and look at what he calls “this magic combination $S^{-1}AS$.” Everything follows from multiplying $A$ times $S$, a column at a time:

$$AS = A \begin{bmatrix} \mathbf{x}_1 & \mathbf{x}_2 & \cdots & \mathbf{x}_n \end{bmatrix} = \begin{bmatrix} \lambda_1\mathbf{x}_1 & \lambda_2\mathbf{x}_2 & \cdots & \lambda_n\mathbf{x}_n \end{bmatrix}$$

Each column of $AS$ is $A$ times an eigenvector, and that’s an eigenvalue times the eigenvector. Now the step Strang likes even better: peel the $\lambda$‘s off. To multiply the first column by $\lambda_1$, the second by $\lambda_2$, and so on, put the $\lambda$‘s in a diagonal matrix on the right:

$$\begin{bmatrix} \lambda_1\mathbf{x}_1 & \cdots & \lambda_n\mathbf{x}_n \end{bmatrix} = \begin{bmatrix} \mathbf{x}_1 & \cdots & \mathbf{x}_n \end{bmatrix} \begin{bmatrix} \lambda_1 & & \\ & \ddots & \\ & & \lambda_n \end{bmatrix} = S\Lambda$$

“There you see matrix multiplication just working for us.” The diagonal matrix of eigenvalues gets a capital lambda, $\Lambda$ — capital letters for matrices, lambda to remind you it holds eigenvalues.

So $A = S\Lambda S^{-1}$ is a new factorization — the replacement for $LU$ from elimination or $QR$ from Gram–Schmidt. A matrix, times a diagonal matrix, times the inverse of the first: that combination of $S$ and $S^{-1}$ runs throughout this chapter.

Powers of A

First use of the formula: what are the eigenvalues and eigenvectors of $A^2$? A straightforward question with an absolutely clean answer, seen two ways.

From the equation. If $A\mathbf{x} = \lambda\mathbf{x}$, multiply both sides by $A$:

$$A^2\mathbf{x} = \lambda A\mathbf{x} = \lambda^2 \mathbf{x}$$

The eigenvalues of $A^2$ are $\lambda^2$ — squared. The eigenvectors are the same $\mathbf{x}$‘s. (Strang always asks about both.)

From the factorization. This is the beauty of eigenvalues:

$$A^2 = \left(S\Lambda S^{-1}\right)\left(S\Lambda S^{-1}\right) = S\Lambda^2 S^{-1}$$

The $S^{-1}S$ in the middle is the identity. Same message in matrix form: same $S$, eigenvalues squared — $\Lambda^2$ is still diagonal, with $\lambda_1^2, \dots, \lambda_n^2$ down its diagonal. And nothing stops at the square. String $K$ copies together and the inner $S^{-1}S$ pairs keep canceling:

$$A^K = S\Lambda^K S^{-1}$$

Here’s an immediate payoff. When do the powers of a matrix go to zero — when is $A$ stable, so to speak? That information is not present in the pivots. It’s present in the eigenvalues. In $A^K = S\Lambda^K S^{-1}$, the $S$ and $S^{-1}$ are not moving; it’s $\Lambda^K$ that has to get small.

Which matrices are diagonalizable?

Time to face the assumption. The nice case first: $A$ is sure to have $n$ independent eigenvectors — and be diagonalizable — if all the $\lambda$‘s are different. No repeated eigenvalues, no problem; for the proof Strang refers you to the text. And this is the typical case: ask Matlab for eig(rand(10,10)) and a random $10 \times 10$ matrix will hand you ten distinct eigenvalues, each with its own eigenvector, automatically independent.

If an eigenvalue is repeated, you have to look more closely — count and check. It’s not a completely negative case: take the $10 \times 10$ identity matrix. Its eigenvalue $1$ is repeated ten times, but there’s no shortage of eigenvectors — every vector is an eigenvector, so pick ten independent ones. Of course $S^{-1}IS = I$: the matrix was already diagonal, and a diagonal matrix has its eigenvalues sitting right there in front of you, $\Lambda = A$.

Now the case that’s going to be trouble.

That’s the case the lecture is not really handling — the stability theorem above, for instance, was reasoned from a formula that needs $n$ independent eigenvectors. Some matrices escape diagonalization, but the great majority don’t, and distinct eigenvalues always come with a full set of independent eigenvectors.

Difference equations: uₖ₊₁ = Auₖ

Now the important application. Start with a vector $\mathbf{u}_0$ and at every step multiply by $A$:

$$\mathbf{u}_{k+1} = A\mathbf{u}_k \qquad\Longrightarrow\qquad \mathbf{u}_1 = A\mathbf{u}_0,\quad \mathbf{u}_2 = A^2\mathbf{u}_0,\quad \dots,\quad \mathbf{u}_k = A^k\mathbf{u}_0$$

Strang calls this a first-order difference equation — a system, because the unknowns are vectors and $A$ is a matrix. The next section will solve differential equations, with derivatives; “this section is the nice one.” And $\mathbf{u}_k = A^k\mathbf{u}_0$ is the most compact formula you could ever ask for. But how would you actually find $\mathbf{u}_{100}$?

To really solve it, write $\mathbf{u}_0$ as a combination of eigenvectors:

$$\mathbf{u}_0 = c_1\mathbf{x}_1 + c_2\mathbf{x}_2 + \cdots + c_n\mathbf{x}_n$$

Now multiply by $A$ and watch — “you’ve got to see the magic of eigenvectors working here.” Each piece is a pure eigenvector, so $A$ only brings in a scalar factor:

$$A\mathbf{u}_0 = c_1\lambda_1\mathbf{x}_1 + c_2\lambda_2\mathbf{x}_2 + \cdots + c_n\lambda_n\mathbf{x}_n$$

Multiply by $A$ a hundred times and each term picks up its eigenvalue a hundred times:

$$\mathbf{u}_{100} = A^{100}\mathbf{u}_0 = c_1\lambda_1^{100}\mathbf{x}_1 + c_2\lambda_2^{100}\mathbf{x}_2 + \cdots + c_n\lambda_n^{100}\mathbf{x}_n$$

The Fibonacci numbers

Now the example. The Fibonacci numbers start $F_0 = 0$, $F_1 = 1$, and each one is the sum of the previous two: $1, 2, 3, 5, 8, 13, \dots$ Question: what is $F_{100}$, and how fast are these numbers growing? They’re certainly growing — not a stable case — but they’re not doubling either. The answer lies in an eigenvalue.

The rule $F_{k+2} = F_{k+1} + F_k$ is a single second-order equation, like a differential equation with second derivatives. A small trick turns it into a first-order system: let the unknown be a vector,

$$\mathbf{u}_k = \begin{bmatrix} F_{k+1} \\ F_k \end{bmatrix}$$

and add the trivially true equation $F_{k+1} = F_{k+1}$ as the second row. Then

$$\mathbf{u}_{k+1} = \begin{bmatrix} F_{k+2} \\ F_{k+1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{k+1} \\ F_k \end{bmatrix} = A\mathbf{u}_k$$

“Before I even think,” find the eigenvalues and eigenvectors. The matrix is symmetric, by the way — so the eigenvalues will come out real (a fact coming later in the course). Sanity checks first: $\lambda_1 + \lambda_2$ equals the trace, $1$, and $\lambda_1\lambda_2$ equals the determinant, $-1$. Now compute:

$$\det(A - \lambda I) = \begin{vmatrix} 1-\lambda & 1 \\ 1 & -\lambda \end{vmatrix} = \lambda^2 - \lambda - 1$$

Compare that with the recursion $F_{k+2} - F_{k+1} - F_k = 0$ — the Fibonacci rule is showing up directly in the eigenvalue equation. The quadratic formula gives

$$\lambda_1 = \frac{1 + \sqrt{5}}{2} \approx 1.618, \qquad \lambda_2 = \frac{1 - \sqrt{5}}{2} \approx -0.618$$

and sure enough they add to $1$ and multiply to $-1$. One eigenvalue bigger than one, one smaller than one in absolute value — “actually, that’s a great situation to be in.” The eigenvalues are distinct, so the matrix is certainly diagonalizable.

And the growth question is already answered. Write $\mathbf{u}_0 = c_1\mathbf{x}_1 + c_2\mathbf{x}_2$ and take a hundred steps: the $\lambda_2$ term, roughly $(-0.618)^{100}$, is extremely small — practically nothing. The $\lambda_1$ term takes over and controls everything:

$$F_{100} \approx c_1 \left( \frac{1+\sqrt{5}}{2} \right)^{100}$$

The Fibonacci numbers grow by a factor of about $1.618$ per step — precise information straight out of an eigenvalue.

To complete the process, the eigenvectors. For this $2 \times 2$ Strang uses a little trick: since

$$A - \lambda I = \begin{bmatrix} 1-\lambda & 1 \\ 1 & -\lambda \end{bmatrix}$$

is singular at each eigenvalue, the vector $\mathbf{x} = (\lambda, 1)$ is in its null space — the second row gives $\lambda - \lambda = 0$, and the first row gives $(1-\lambda)\lambda + 1 = -(\lambda^2 - \lambda - 1) = 0$, zero exactly because these $\lambda$‘s are special. So $\mathbf{x}_1 = (\lambda_1, 1)$ and $\mathbf{x}_2 = (\lambda_2, 1)$. The starting vector is $\mathbf{u}_0 = (F_1, F_0) = (1, 0)$, and solving $c_1\mathbf{x}_1 + c_2\mathbf{x}_2 = \mathbf{u}_0$ pins down $c_1$ and $c_2$ — the last step, which the lecture leaves as the closing idea rather than grinding out (Problem 22.4 finishes it).

The idea is what’s central. When things evolve in time by a first-order system from a starting vector $\mathbf{u}_0$: find the eigenvalues and eigenvectors of $A$ — they already tell you whether the solution blows up or dies out — then expand $\mathbf{u}_0$ into eigenvectors and follow each one separately. That is exactly what $A^k = S\Lambda^k S^{-1}$ is doing.

Problems

Work these before revealing the solutions — they use only this lecture’s machinery.

Problem 22.1 Diagonalize and take powers

Diagonalize

$$A = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}$$

— find $S$ and $\Lambda$ with $A = S\Lambda S^{-1}$ — and use the factorization to give a formula for $A^k$.

Show solution

$\det(A - \lambda I) = (3-\lambda)^2 - 1 = \lambda^2 - 6\lambda + 8 = (\lambda - 4)(\lambda - 2)$, so $\lambda_1 = 4$, $\lambda_2 = 2$ (check: trace $6$, determinant $8$).

Eigenvectors: $A - 4I = \begin{bmatrix} -1 & 1 \\ 1 & -1 \end{bmatrix}$ gives $\mathbf{x}_1 = (1,1)$; $A - 2I = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}$ gives $\mathbf{x}_2 = (1,-1)$.

$$S = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix},\quad \Lambda = \begin{bmatrix} 4 & 0 \\ 0 & 2 \end{bmatrix},\quad S^{-1} = \frac{1}{2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$$

Then

$$A^k = S\Lambda^k S^{-1} = \frac{1}{2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} 4^k & 0 \\ 0 & 2^k \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} = \frac{1}{2}\begin{bmatrix} 4^k + 2^k & 4^k - 2^k \\ 4^k - 2^k & 4^k + 2^k \end{bmatrix}$$

Check $k = 1$: $\frac{1}{2}\begin{bmatrix} 6 & 2 \\ 2 & 6 \end{bmatrix} = A$. ✓

Problem 22.2 Do the powers go to zero?

Without computing any powers, decide whether $A^k \to 0$ as $k \to \infty$ for

$$A = \begin{bmatrix} 0.6 & 0.9 \\ 0.1 & 0.6 \end{bmatrix}$$

Show solution

The answer lives in the eigenvalues. Trace $= 1.2$ and determinant $= 0.36 - 0.09 = 0.27$, so

$$\det(A - \lambda I) = \lambda^2 - 1.2\lambda + 0.27 = (\lambda - 0.9)(\lambda - 0.3)$$

giving $\lambda_1 = 0.9$, $\lambda_2 = 0.3$. Both satisfy $|\lambda| \lt 1$, and the eigenvalues are distinct, so $A$ is diagonalizable and

$$A^k = S\Lambda^k S^{-1} = S \begin{bmatrix} 0.9^k & 0 \\ 0 & 0.3^k \end{bmatrix} S^{-1} \to 0$$

since $S$ and $S^{-1}$ don’t move while $\Lambda^k \to 0$. Yes: the powers go to zero (slowly — the $0.9^k$ term controls the approach).

Problem 22.3 Algebraic vs. geometric multiplicity

Both of these matrices have $\lambda = 3$ repeated twice:

$$A = \begin{bmatrix} 3 & 0 \\ 0 & 3 \end{bmatrix}, \qquad B = \begin{bmatrix} 3 & 5 \\ 0 & 3 \end{bmatrix}$$

For each, find the algebraic and geometric multiplicities of $\lambda = 3$ and decide whether the matrix is diagonalizable.

Show solution

Both characteristic polynomials are $(3 - \lambda)^2$, so the algebraic multiplicity is 2 for both.

For $A = 3I$: $A - 3I$ is the zero matrix, whose null space is all of $\mathbb{R}^2$ — every vector is an eigenvector. Geometric multiplicity 2; take $S = I$ and $A$ is (already) diagonal. Diagonalizable.

For $B$: $B - 3I = \begin{bmatrix} 0 & 5 \\ 0 & 0 \end{bmatrix}$ has a one-dimensional null space, spanned by $(1, 0)$ alone — $(0,1)$ is not in it. Geometric multiplicity 1: only one independent eigenvector, two needed. Not diagonalizable — no invertible eigenvector matrix $S$ exists.

Moral: a repeated eigenvalue may or may not bring enough eigenvectors — you have to count.

Problem 22.4 Finishing Fibonacci

The lecture stopped just short of the constants. Using the eigenvectors $\mathbf{x}_1 = (\lambda_1, 1)$ and $\mathbf{x}_2 = (\lambda_2, 1)$ of the Fibonacci matrix, with $\lambda_1 = \frac{1+\sqrt{5}}{2}$ and $\lambda_2 = \frac{1-\sqrt{5}}{2}$, expand $\mathbf{u}_0 = (1, 0)$ as $c_1\mathbf{x}_1 + c_2\mathbf{x}_2$ and derive an exact formula for $F_k$.

Show solution

The expansion $c_1\mathbf{x}_1 + c_2\mathbf{x}_2 = (1,0)$ gives two equations:

$$c_1\lambda_1 + c_2\lambda_2 = 1, \qquad c_1 + c_2 = 0$$

From the second, $c_2 = -c_1$; substitute into the first: $c_1(\lambda_1 - \lambda_2) = 1$. Since $\lambda_1 - \lambda_2 = \sqrt{5}$,

$$c_1 = \frac{1}{\sqrt{5}}, \qquad c_2 = -\frac{1}{\sqrt{5}}$$

Each eigenvector goes its own way: $\mathbf{u}_k = c_1\lambda_1^k \mathbf{x}_1 + c_2\lambda_2^k \mathbf{x}_2$. The second component of $\mathbf{u}_k$ is $F_k$, and the second component of each eigenvector is $1$, so

$$F_k = c_1\lambda_1^k + c_2\lambda_2^k = \frac{1}{\sqrt{5}}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^{k} - \left(\frac{1-\sqrt{5}}{2}\right)^{k} \right]$$

Check: $F_0 = 0$ ✓, $F_1 = \frac{1}{\sqrt{5}}\cdot\sqrt{5} = 1$ ✓, $F_2 = \frac{1}{\sqrt{5}}(\lambda_1^2 - \lambda_2^2) = \frac{1}{\sqrt{5}}(\lambda_1+\lambda_2)(\lambda_1-\lambda_2) = 1$ ✓. Since $|\lambda_2| \lt 1$, the second term vanishes as $k$ grows, and $F_{100} \approx \frac{1}{\sqrt{5}}\lambda_1^{100}$ — exactly the growth rate the eigenvalue predicted.