## Announcements:

Today we finish 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.

Next class: course evaluations.

Tutorials: Quiz 9 (the last one) will cover Section 4.4.

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

Office hour: Monday, 1:30-2:30, MC103B.

The final exam will take place on Tuesday, April 22, 2-5pm. All students write in AH201 (Alumni Hall). See the course home page for final exam conflict policy. You should immediately notify the registrar or your Dean (and your instructor) of any conflicts!

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$.

### Review of Section 4.4

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}$.

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$.

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.

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.

### Diagonalization

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

If $A$ is similar to a diagonal matrix $D$, then $D$ must have the eigenvalues of $A$ on the diagonal. But how to find $P$?

Theorem 4.23: Let $A$ be an $n \times n$ matrix. If $P$ is an $n \times n$ matrix whose columns are linearly independent eigenvectors of $A$, then $P^{-1} A P$ is a diagonal matrix $D$ with the corresponding eigenvalues of $A$ on the diagonal.

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.

### New material: Section 4.4 continued

Proof of Theorem 4.23: 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 if 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?

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?

Summary of diagonalization: Given an $n \times n$ matrix $A$, we would like to determine whether $A$ is diagonalizable, and if it is, find the invertible matrix $P$ and the diagonal matrix $D$ such that $P^{-1} A P = D$. The result may depend upon whether you are working over $\R$ or $\C$.

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.

I still owe you a proof of:

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$$

Proof (more direct than in text): Suppose that $\lambda_1$ is an eigenvalue of $A$ with geometric multiplicity $g$, and let $\vv_1, \ldots, \vv_g$ be a basis for $E_{\lambda_1}$, so $$A \vv_i = \lambda_1 \vv_i \qtext{for each i.}$$ Let $Q$ be an invertible matrix whose first $g$ columns are $\vv_1, \ldots, \vv_g$: $$Q = [ \, \vv_1 \, \cdots \, \vv_g \qtext{other vectors} ]$$ Since $Q^{-1} Q = I$, we know that $Q^{-1} \vv_i = \ve_i$ for $1 \leqslant i \leqslant g$. Also, the first $g$ columns of $A Q$ are $\lambda_1 \vv_1, \ldots, \lambda_1 \vv_g$. So the first $g$ columns of $Q^{-1} A Q$ are $\lambda_1 \ve_1, \ldots, \lambda_1 \ve_g$. Therefore the matrix $Q^{-1} A Q$ has $\lambda_1$ as an eigenvalue with algebraic multiplicity at least $g$. But $Q^{-1} A Q$ has the same characteristic polynomial as $A$, so $\lambda_1$ must also have algebraic multiplicity at least $g$ for $A$.$\quad\Box$.