Similar Matrices and Jordan Form

Finishing positive definiteness

Before similar matrices, Strang grabs the first ten minutes for a subject he “thinks is really important” — positive definite matrices. We know what positive definite means: the quadratic form $\mathbf{x}^T A \mathbf{x}$ is always positive (for $\mathbf{x} \neq \mathbf{0}$), with $A$ symmetric always built into the definition. We know how to test it — eigenvalues, pivots, determinants. Three quick questions push the idea further.

Is the inverse of a symmetric positive definite matrix positive definite? Don’t reach for pivots — you know nothing about the pivots of $A^{-1}$. But you know everything about its eigenvalues: they are $1/\lambda$ for each eigenvalue $\lambda$ of $A$. If every $\lambda$ is positive, so is every $1/\lambda$. Yes — the inverse is positive definite.

If $A$ and $B$ are both positive definite, what about $A + B$? You hope so — positive definite for a matrix is “kind of like positive for a real number.” But you don’t know the eigenvalues of $A + B$, and you don’t know its pivots. So go down the list of tests and grab the one you can handle: the quadratic form. We have $\mathbf{x}^T A \mathbf{x} > 0$ and $\mathbf{x}^T B \mathbf{x} > 0$ for all $\mathbf{x} \neq \mathbf{0}$. Add them:

$$\mathbf{x}^T (A + B)\, \mathbf{x} = \mathbf{x}^T A \mathbf{x} + \mathbf{x}^T B \mathbf{x} > 0.$$

If $A$ and $B$ are positive definite, so is $A + B$. Be ready for all the approaches — eigenvalues and the quadratic form.

A transpose A is positive definite

Now the combination that came up in least squares. Let $A$ be rectangular, $m$ by $n$. No way is $A$ itself positive definite — it isn’t symmetric, it isn’t even square. But the key matrix in least squares and projections was $A^T A$: square, symmetric. Now we can ask the deeper question — is it positive definite? In analogy with numbers, $A^T A$ is “sort of like the square of a number,” and squares are positive.

Eigenvalues of the product? Unknown. Pivots? No thanks. The right quantity is the quadratic form $\mathbf{x}^T A^T A \mathbf{x}$ — and the argument is “the one key idea in so many steps in linear algebra: put those parentheses in a good way.”

For an 11 by 5 matrix: no null space means the 5 columns are independent — rank 5, rank $n$. Then $A^T A$ is invertible, the least squares equations all work, and more: the matrix is positive definite. One numerical comment: with a positive definite matrix you never have to do row exchanges, never run into unsuitably small pivots or zeros. “They’re the great matrices to compute with, and they’re the great matrices to study.” Positive definiteness brought everything together — we’re coming close to the end of the heart of linear algebra.

Similar matrices: the definition

Now today’s lecture proper. Two square $n$ by $n$ matrices — no longer expecting symmetric — and a new word.

Why that combination? Part of the answer you already know. If $A$ has a full set of eigenvectors, put them in the eigenvector matrix $S$, and the main calculation of the whole chapter was

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

In the new language: $A$ is similar to $\Lambda$ — there is an $M$, and that particular $M$ is the all-important eigenvector matrix. But take any other invertible $M$ and $M^{-1} A M$ won’t come out diagonal — it comes out some matrix $B$ similar to $A$.

The main fact: same eigenvalues

The proof starts from the only possible place, $A\mathbf{x} = \lambda\mathbf{x}$, and gets $M$ into the picture by slipping in $M M^{-1}$ (the identity — the left side is unchanged):

$$A M M^{-1} \mathbf{x} = \lambda \mathbf{x}.$$

Multiply on the left by $M^{-1}$ — the same to both sides, and $\lambda$ is just a number that factors out front:

$$\underbrace{M^{-1} A M}_{B}\, (M^{-1}\mathbf{x}) = \lambda\, (M^{-1}\mathbf{x}).$$

$B$ times some vector equals $\lambda$ times that vector — so $\lambda$ is an eigenvalue of $B$ too. End of proof. The eigenvector didn’t stay the same, and of course it shouldn’t: if all the eigenvalues and all the eigenvectors matched, the matrices would probably be equal. Similar matrices have the same eigenvalues with eigenvectors just moved around by $M^{-1}$. Diagonalization is the special case where the move makes the eigenvectors as nice as possible — the eigenvectors of $\Lambda$ are just $(1,0)$ and $(0,1)$.

So the family of matrices similar to $A$ above is all matrices with eigenvalues $3$ and $1$: the triangular $\begin{bmatrix} 3 & 7 \\ 0 & 1 \end{bmatrix}$, the flipped $\begin{bmatrix} 1 & 0 \\ 7 & 3 \end{bmatrix}$, and infinitely many more — for each, some $M$ connects it to the rest.

The bad case: repeated eigenvalues

That family was nice because its two eigenvalues were different. Now the less happy possibility: $\lambda_1 = \lambda_2$. Then the matrix might not have a full set of eigenvectors — might not be diagonalizable — and the family picture gets trickier.

Say $\lambda_1 = \lambda_2 = 4$. The matrices with eigenvalues $4$ and $4$ split into two families, not one.

One family contains only $4I = \begin{bmatrix} 4 & 0 \\ 0 & 4 \end{bmatrix}$ — a “total loner.” Why is it off by itself? Conjugate it by any invertible $M$:

$$M^{-1} (4I) M = 4\, M^{-1} I M = 4 I.$$

The identity slips through, $M^{-1}$ cancels $M$, and you get $4I$ back every time. The only matrix similar to $4I$ is $4I$ itself — a family with one member.

All the other matrices with eigenvalues $4, 4$ form one big family, and its best-looking member is

$$J = \begin{bmatrix} 4 & 1 \\ 0 & 4 \end{bmatrix}.$$

This matrix is not diagonalizable — if it were, it would be similar to $4I$, and nothing but $4I$ is. The catch: it has only one eigenvector. It can’t be made diagonal, so this near-diagonal form — diagonal except for one $1$ above the diagonal — is the nearest the family gets. That’s its Jordan form, after Jordan, who studied these families and picked out the nicest, most-diagonal member of each.

Other members of the big family? They need trace $8$ and determinant $16$: for instance $\begin{bmatrix} 5 & 1 \\ -1 & 3 \end{bmatrix}$, or $\begin{bmatrix} 4 & 0 \\ 17 & 4 \end{bmatrix}$ — in general any $a$ and $8 - a$ on the diagonal, filled in to make the determinant $16$. All similar, all with eigenvalues $4$ and $4$, all with only one eigenvector. Similar matrices share the same $\lambda$‘s and the same number of independent eigenvectors — because an eigenvector for $A$ gives the eigenvector $M^{-1}\mathbf{x}$ for $B$.

Jordan blocks and Jordan’s theorem

But counting eigenvectors is not enough, and a 4 by 4 example shows why. “If you want nightmares, think about matrices like these”:

$$A = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

Its eigenvalues are four zeros. Its eigenvectors live in the null space (since $A\mathbf{x} = 0\mathbf{x}$), and the rank is obviously $2$ — two independent rows — so the null space has dimension $4 - 2 = 2$: two eigenvectors, two missing. Change one of the remaining zeros to a $7$ and the rank is still $2$ — that matrix is similar to this one, just not as beautiful. Jordan picked the clean version: a $1$ above the diagonal for every missing eigenvector.

Now move the second $1$:

$$B = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

Eigenvalues: four zeros again. Rank: $2$ again. Two eigenvectors, two missing — the counts all match. “But the darn thing is not similar to that one.” The first matrix is a 3 by 3 block with a 1 by 1 block; the second is a 2 by 2 block with a 2 by 2 block. Those blocks are Jordan blocks, and matrices with different block sizes are not similar — Jordan worked that out.

Jordan completed diagonalization by coming as near to it as every matrix allows — including the non-diagonalizable ones. When Strang took 18.06, the Jordan form was the climax of the course. He thinks it isn’t the climax of linear algebra anymore: computing it for a general matrix is not easy, because it depends on eigenvalues being exactly equal and on exact ranks — the slightest change in the numbers changes both, so numerically it’s not a good thing. For algebra, though, it’s the right way to understand these families. “I’m not that crazy about the Jordan form. But I’m very positive about positive definite matrices” — and about what’s coming Monday: the singular value decomposition.

Problems

Work these before revealing the solutions — trace and determinant will do most of the eigenvalue checking for you.

Problem 28.1 Verify similarity by hand

Let

$$A = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}, \qquad M = \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix}.$$

Compute $B = M^{-1} A M$, then confirm by trace and determinant that $A$ and $B$ have the same eigenvalues. What are those eigenvalues?

Show solution

Since $M$ is triangular with ones on the diagonal, $M^{-1} = \begin{bmatrix} 1 & -2 \\ 0 & 1 \end{bmatrix}$.

First $AM = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}\begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 3 & 7 \\ 1 & 5 \end{bmatrix}$.

Then

$$B = M^{-1}(AM) = \begin{bmatrix} 1 & -2 \\ 0 & 1 \end{bmatrix}\begin{bmatrix} 3 & 7 \\ 1 & 5 \end{bmatrix} = \begin{bmatrix} 1 & -3 \\ 1 & 5 \end{bmatrix}.$$

Check: $\operatorname{trace}(B) = 1 + 5 = 6 = \operatorname{trace}(A)$ and $\det(B) = 5 + 3 = 8 = \det(A) = 9 - 1$. Eigenvalues solve $\lambda^2 - 6\lambda + 8 = 0$, so $\lambda = 4$ and $\lambda = 2$ — the same for both matrices.

Problem 28.2 A transpose A test

Let

$$A = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 0 & 1 \end{bmatrix}.$$

(a) Compute $A^T A$. (b) Without computing eigenvalues, explain why $A^T A$ must be positive definite. (c) Confirm with the determinant test.

Show solution

(a)

$$A^T A = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 2 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 2 & 3 \\ 3 & 6 \end{bmatrix}.$$

(b) For any $\mathbf{x}$, $\mathbf{x}^T A^T A \mathbf{x} = \|A\mathbf{x}\|^2 \geq 0$, with equality only when $A\mathbf{x} = \mathbf{0}$. The columns of $A$, $(1,1,0)$ and $(1,2,1)$, are independent (neither is a multiple of the other), so $A$ has rank $2 = n$ and no null space: $A\mathbf{x} = \mathbf{0}$ forces $\mathbf{x} = \mathbf{0}$. Hence $\|A\mathbf{x}\|^2 > 0$ for $\mathbf{x} \neq \mathbf{0}$ — positive definite.

(c) Leading determinants: $2 > 0$ and $\det = 12 - 9 = 3 > 0$. Positive definite, confirmed.

Problem 28.3 Sorting a family

The eigenvalues of each matrix below are $2$ and $2$. Which of them are similar to $J = \begin{bmatrix} 2 & 1 \\ 0 & 2 \end{bmatrix}$, and which are not?

$$P = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix}, \qquad Q = \begin{bmatrix} 2 & 0 \\ 5 & 2 \end{bmatrix}, \qquad R = \begin{bmatrix} 3 & 1 \\ -1 & 1 \end{bmatrix}.$$

Show solution

The matrices with eigenvalues $2, 2$ split into two families: the loner $2I$, and everything else, whose Jordan form is $J$.

$P = 2I$ is not similar to $J$: for any invertible $M$, $M^{-1}(2I)M = 2I$ — the only matrix similar to $2I$ is $2I$ itself. (Equivalently, $P$ has two independent eigenvectors and $J$ has one.)

$Q$ is similar to $J$: trace $4$, determinant $4$, eigenvalues $2, 2$, and $Q - 2I = \begin{bmatrix} 0 & 0 \\ 5 & 0 \end{bmatrix}$ has rank $1$, so the null space is one-dimensional: only one eigenvector. $Q$ is not diagonalizable, so it lives in the big family with Jordan form $J$.

$R$ is similar to $J$: trace $4$, determinant $3 + 1 = 4$, so eigenvalues $2, 2$. And $R - 2I = \begin{bmatrix} 1 & 1 \\ -1 & -1 \end{bmatrix}$ has rank $1$ — again a single eigenvector, so $R$ is in the same family as $J$ and $Q$.

Problem 28.4 Counting is not enough

Consider the 4 by 4 matrices

$$A = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}, \qquad B = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

For each: find the eigenvalues, the rank, and the number of independent eigenvectors. Describe each matrix’s Jordan block structure. Are $A$ and $B$ similar?

Show solution

Both matrices are triangular with zeros on the diagonal, so both have eigenvalues $0, 0, 0, 0$. Eigenvectors for $\lambda = 0$ fill the null space.

$A$: three independent rows, so rank $3$; the null space has dimension $4 - 3 = 1$ — one eigenvector. One eigenvector means one Jordan block: $A$ is a single 4 by 4 Jordan block.

$B$: two independent rows, so rank $2$; the null space has dimension $4 - 2 = 2$ — two eigenvectors, hence two Jordan blocks: a 3 by 3 block and a 1 by 1 block.

Not similar. They already differ in eigenvector count ($1$ versus $2$), so no $M$ can connect them — similar matrices must have the same number of independent eigenvectors. (And even matching counts wouldn’t be enough: a 3+1 block structure is not similar to a 2+2 structure, though both have two eigenvectors.)