Today we continue with 4.4. **Read** Markov chains part of Section 4.6
for next class.
Not covering Section 4.5, or rest of 4.6 (which contains many
interesting applications!)
Work through recommended homework questions.

**Tutorials:** Quiz 8 will cover Section 4.3,
the part of Appendix C we covered,
and what we finish today in Section 4.4.
There is also a quiz next week.

**Help Centers:** Monday-Friday 2:30-6:30 in MC 106.

**Office hour:** Monday, 3:00-3:30, MC103B.

**True/false:**
Every polynomial of degree $n$ has exactly $n$ distinct roots over $\C$.

**True/false:**
The complex eigenvalues of a matrix always come in conjugate pairs.

**True/false:**
If $\lambda$ is an eigenvalue of $A$ and $k \geqslant 0$,
then $\lambda^k$ is an eigenvalue of $A^k$.

**Definition:** Let $A$ and $B$ be $n \times n$ matrices. We say that
$A$ is **similar** to $B$ if there is an invertible matrix $P$ such that $P^{-1} A P = B$.
When this is the case, we write $A \sim B$.

It is equivalent to say that $AP = PB$ or $A = PBP^{-1}$.

**Example 4.22:** Let $A = \bmat{rr} 1 & 2 \\ 0 & -1 \emat$ and $B = \bmat{rr} 1 & 0 \\ -2 & -1 \emat$.
Then $A \sim B$, since
$$
\bmat{rr} 1 & 2 \\ 0 & -1 \emat \bmat{rr} 1 & -1 \\ 1 & 1 \emat
= \bmat{rr} 1 & -1 \\ 1 & 1 \emat \bmat{rr} 1 & 0 \\ -2 & -1 \emat.
$$
We also need to check that the matrix $P = \bmat{rr} 1 & -1 \\ 1 & 1 \emat$ is
invertible, which is the case since its determinant is $2$.

It is tricky in general to find such a $P$ when it exists. We'll learn a method that works in a certain situation in this section.

**Theorem 4.21:** Let $A$, $B$ and $C$ be $n \times n$ matrices. Then:

a. $A \sim A$.

b. If $A \sim B$ then $B \sim A$.

c. If $A \sim B$ and $B \sim C$, then $A \sim C$.

**Proof:** (a) $I^{-1} A I = A$

(b) Suppose $A \sim B$. Then $P^{-1}AP = B$ for some invertible matrix $P$. Then $PBP^{-1} = A$. Let $Q = P^{-1}$. Then $Q^{-1}BQ = A$, so $B \sim A$.

(c) Exercise.$\quad\Box$

Similar matrices have a lot of properties in common.

**Theorem 4.22:**
Let $A$ and $B$ be similar matrices. Then:

a. $\det A = \det B$

b. $A$ is invertible iff $B$ is invertible.

c. $A$ and $B$ have the same rank.

d. $A$ and $B$ have the same characteristic polynomial.

e. $A$ and $B$ have the same eigenvalues.

**Proof:**
Assume that $P^{-1}AP = B$ for some invertible matrix $P$.

We discussed (a) in lecture 27: $$ \begin{aligned} \det(B)\ &= \det(P^{-1}AP) = \det(P^{-1})\det(A)\det(P)\\ &= \frac{1}{\det (P)} \det(A) \det(P) = \det A . \end{aligned} $$ (b) follows immediately.

(c) takes a bit of work and will not be covered.

(d) follows from (a): since $B - \lambda I = P^{-1} A P - \lambda I = P^{-1} (A - \lambda I) P$ it follows that $B - \lambda I$ and $A - \lambda I$ have the same determinant.

(e) follows from (d).$\quad\Box$

**Question:** Are $\bmat{rr} 1 & 2 \\ 3 & 4 \emat$ and $\bmat{rr} 1 & 1 \\ 2 & -1 \emat$
similar?

**Question:** Are $\bmat{rr} 1 & 2 \\ 0 & 4 \emat$ and $\bmat{rr} 2 & 0 \\ 1 & 2 \emat$
similar?

**True/false:**
The identity matrix is similar to every matrix.

**True/False:**
If $A$ and $B$ have the same eigenvalues, then $A$ and $B$ are similar.

See also Example 4.23(b) in text.

**Definition:** $A$ is **diagonalizable** if it is similar to some diagonal matrix.

**Example 4.24:** $A = \bmat{rr} 1 & 3 \\ 2 & 2 \emat$ is diagonalizable.
Take $P = \bmat{rr} 1 & 3 \\ 1 & -2 \emat$. Then
$$
\kern-8ex
P^{-1} A P
= \frac{1}{\det P} \bmat{rr} -2 & -3 \\ -1 & 1 \emat \bmat{rr} 1 & 3 \\ 2 & 2 \emat \bmat{rr} 1 & 3 \\ 1 & -2 \emat
= \bmat{rr} 4 & 0 \\ 0 & -1 \emat
$$
If $A$ is similar to a diagonal matrix $D$, then $D$ must have the eigenvalues
of $A$ on the diagonal. (Why?) But how to find $P$?

On board: notice that the columns of $P$ are eigenvectors for $A$!

On the other hand, if $P$ is any invertible matrix such that $P^{-1} A P$ is diagonal, then the columns of $P$ are linearly independent eigenvectors of $A$.

It follows that $A$ is diagonalizable if and only if it has $n$ linearly independent eigenvectors.

This theorem is one of the main reasons we want to be able to find eigenvectors of a matrix. Moreover, the more eigenvectors the better, so this motivates allowing complex eigenvectors.

**Proof:** Suppose $\vp_1, \vp_2, \ldots, \vp_n$ are $n$ linearly independent
eigenvectors of $A$, and let $P = [\,\vp_1\,\vp_2\,\cdots\,\vp_n\,]$.
Write $\lambda_i$ for the $i$th eigenvalue,
so $A \vp_i = \lambda_i \vp_i$ for each $i$,
and let $D$ be the diagonal matrix with the $\lambda_i$'s on the diagonal.
Then
$$
\kern-4ex
AP = A[\,\vp_1\,\vp_2\,\cdots\,\vp_n\,]
= [\,\lambda_1\vp_1\ \ \lambda_2\vp_2\ \,\cdots\ \lambda_n\vp_n\,]
$$
Also,
$$
\kern-4ex
\begin{aligned}
PD\ &= [\,\vp_1\,\vp_2\,\cdots\,\vp_n\,]
\bmat{cccc} \lambda_1 & 0 & \cdots & 0 \\
0 & \lambda_2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \lambda_n \emat \\
&= [\,\lambda_1\vp_1\ \ \lambda_2\vp_2\ \,\cdots\ \lambda_n\vp_n\,]
\end{aligned}
$$
so $P^{-1} A P = D$, as required. (Why is $P$ invertible?)

On the other hand, if $P^{-1} A P = D$ and $D$ is diagonal, then $AP = PD$, and it follows from an argument like the one above that the columns of $P$ are eigenvectors of $A$, and the eigenvalues are the diagonal entries of $D$.$\quad\Box$

So we'd like to be able to find enough linearly independent eigenvectors of a matrix. Recall that in Section 4.3, we saw:

**Theorem 4.20:** If $\vv_1, \vv_2, \ldots, \vv_m$ are eigenvectors of $A$
corresponding to distinct eigenvalues
$\lambda_1, \lambda_2, \ldots, \lambda_m$, then
$\vv_1, \vv_2, \ldots, \vv_m$ are linearly independent.

**Example:** Is the matrix
$A = \bmat{rrr} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \emat$
diagonalizable?

Yes. The eigenvalues
are $1$, $4$ and $6$, and for each one there is at least one
eigenvector. These are linearly independent (by Theorem 4.20),
and there are three of them, so $A$ is diagonalizable (by Theorem 4.23).

To **find** the matrix $P$ explicitly, we need to solve the
three systems to find the eigenvectors.

**Theorem 4.25:** If $A$ is an $n \times n$ matrix with $n$ distinct eigenvalues,
then $A$ is diagonalizable.

**Example 4.25:** Is $A = \bmat{rrr} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 2 & -5 & 4 \emat$
diagonalizable? If so, find a matrix $P$ that diagonalizes it.

**Solution:**
In Example 4.18 we found that the eigenvalues are
$\lambda = 1$ (with algebraic multiplicity 2) and
$\lambda = 2$ (with algebraic multiplicity 1).
A basis for $E_1$ is $\colll 1 1 1$ and a basis for $E_2$ is $\colll 1 2 4$.
Since every eigenvector is a scalar multiple of one of these, it is not
possible to find three linearly independent eigenvectors.
So $A$ is not diagonalizable.

**Example 4.26:** Is $A = \bmat{rrr} -1 & 0 & 1 \\ 3 & 0 & -3 \\ 1 & 0 & -1 \emat$
diagonalizable? If so, find a matrix $P$ that diagonalizes it.

**Solution:**
In Example 4.19 (done mostly on board, but also
in text) we found that the eigenvalues are
$\lambda = 0$ (with algebraic multiplicity 2) and
$\lambda = -2$ (with algebraic multiplicity 1).
A basis for $E_0$ is $\vp_1 = \colll 0 1 0$ and $\vp_2 = \colll 1 0 1$.
A basis for $E_{-2}$ is $\vp_3 = \colll {-1} 3 1$.
These are linearly independent (see below). Thus
$$
P = [\, \vp_1 \, \vp_2 \, \vp_3 \,]
= \bmat{rrr} 0 & 1 & -1 \\ 1 & 0 & 3 \\ 0 & 1 & 1 \emat
$$
is invertible, and by the theorem, we must have
$$
P^{-1} A P = \bmat{rrr} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & -2 \emat = D
$$
(Note that to check an answer like this, it is usually easiest
to check that $AP = PD$. Do so!)

Note: Different orders of eigenvectors/values work too.

**Theorem 4.24:** If $\lambda_1, \ldots, \lambda_k$ are distinct eigenvalues of $A$
and, for each $i$, $\cB_i$ is a basis for the eigenspace $E_{\lambda_i}$,
then the union of the $\cB_i$'s is a linearly independent set.

The proof of this is similar to the proof of Theorem 4.20, where we had only one non-zero vector in each eigenspace.

Combining Theorems 4.23 and 4.24 gives the following important consequence:

**Theorem:** An $n \times n$ matrix is diagonalizable if and only if
the sum of the geometric multiplicities of the eigenvalues is $n$.

Look at Examples 4.25 and 4.26 again.

So it is important to understand the geometric multiplicities better. Here is a helpful result:

**Lemma 4.26:** If $\lambda_1$ is an eigenvalue of an $n \times n$ matrix $A$, then
$$
\text{geometric multiplicity of } \lambda_1 \leqslant
\text{algebraic multiplicity of } \lambda_1
$$

We'll prove this in a minute. First, let's look at what it implies:

Let $A$ be an $n \times n$ matrix with distinct eigenvalues $\lambda_1, \lambda_2, \ldots, \lambda_k$. Let their geometric multiplicities be $g_1, g_2, \ldots, g_k$ and their algebraic multiplicities be $a_1, a_2, \ldots, a_k$. We know $$ g_i \leqslant a_i \qtext{for each $i$} $$ and so $$ g_1 + \cdots + g_k \leqslant a_1 + \cdots + a_k \leqslant n $$ So the only way to have $g_1 + \cdots + g_k = n$ is to have $g_i = a_i$ for each $i$ and $a_1 + \cdots + a_k = n$.

This gives the **main theorem** of the section:

**Theorem 4.27 (The Diagonalization Theorem):**
Let $A$ be an $n \times n$ matrix with distinct eigenvalues
$\lambda_1, \lambda_2, \ldots, \lambda_k$.
Let their geometric multiplicities be $g_1, g_2, \ldots, g_k$
and their algebraic multiplicities be $a_1, a_2, \ldots, a_k$.
Then the following are equivalent:

a. $A$ is diagonalizable.

b. $g_1 + \cdots + g_k = n$.

c. $g_i = a_i$ for each $i$ and $a_1 + \cdots + a_k = n$.

**Note:** This is stated incorrectly in the text.
The red part must be added unless you are working over $\C$,
in which case it is automatic that $a_1 + \cdots + a_k = n$.
With the way I have stated it, it is correct over $\R$ or over $\C$.

**Example:** Is $A = \bmat{rr} 0 & -1 \\ 1 & 0 \emat$
diagonalizable?

It
depends.
If we are working over $\R$,
there are no eigenvalues and no eigenvectors, so no, it is not diagonalizable,
and (a), (b) and (c) all fail.

If we are working over $\C$, then $i$ and $-i$ are eigenvalues, and are distinct, so $A$ is diagonalizable, and (b) and (c) hold too. Note that in this case, $P$ will be complex: To find $P$, we first find that corresponding eigenvectors are $\vp_1 = \coll i 1$ and $\vp_2 = \coll 1 i$. So if we take $$ P = [\,\vp_1\,\vp_2\,] = \bmat{rr} i & 1 \\ 1 & i \emat $$ we find that $$ P^{-1} A P = \bmat{rr} i & 0 \\ 0 & -i \emat = D $$

**Steps**:

1. Compute the characteristic polynomial $\det(A - \lambda I)$ of $A$.

2. Find the roots of the characteristic polynomial and their algebraic
multiplicities by factoring.

3. If the algebraic multiplicities don't add up to $n$, then $A$ is
not diagonalizable, and you can stop. (If you are working over $\C$,
this can't happen.)

4. For each eigenvalue $\lambda$, compute the dimension of the
eigenspace $E_\lambda$. This is the geometric multiplicity of
$\lambda$, and if it is less than the algebraic multiplicity,
then $A$ is not diagonalizable, and you can stop.

5. Compute a basis for the eigenspace $E_\lambda$.

6. If for each eigenvalue the geometric multiplicity equals the
algebraic multiplicity, then you take the $n$ eigenvectors you
found and put them in the columns of a matrix $P$. Put the
eigenvalues in the same order on the diagonal of a matrix $D$.

7. **Check** that $AP=PD$.

Note that step 4 only requires you to find the row echelon form of $A - \lambda I$, as the number of free variables here is the geometric multiplicity. In step 5, you solve the system.