Math 1600 Lecture 30, Section 2, 17 Nov 2014

$ \newcommand{\bdmat}[1]{\left|\begin{array}{#1}} \newcommand{\edmat}{\end{array}\right|} \newcommand{\bmat}[1]{\left[\begin{array}{#1}} \newcommand{\emat}{\end{array}\right]} \newcommand{\coll}[2]{\bmat{r} #1 \\ #2 \emat} \newcommand{\ccoll}[2]{\bmat{c} #1 \\ #2 \emat} \newcommand{\colll}[3]{\bmat{r} #1 \\ #2 \\ #3 \emat} \newcommand{\ccolll}[3]{\bmat{c} #1 \\ #2 \\ #3 \emat} \newcommand{\collll}[4]{\bmat{r} #1 \\ #2 \\ #3 \\ #4 \emat} \newcommand{\ccollll}[4]{\bmat{c} #1 \\ #2 \\ #3 \\ #4 \emat} \newcommand{\colllll}[5]{\bmat{r} #1 \\ #2 \\ #3 \\ #4 \\ #5 \emat} \newcommand{\ccolllll}[5]{\bmat{c} #1 \\ #2 \\ #3 \\ #4 \\ #5 \emat} \newcommand{\red}[1]{{\color{red}#1}} \newcommand{\lra}[1]{\mbox{$\xrightarrow{#1}$}} \newcommand{\rank}{\textrm{rank}} \newcommand{\row}{\textrm{row}} \newcommand{\col}{\textrm{col}} \newcommand{\null}{\textrm{null}} \newcommand{\nullity}{\textrm{nullity}} \renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \renewcommand{\Arg}{\operatorname{Arg}} \renewcommand{\arg}{\operatorname{arg}} \newcommand{\adj}{\textrm{adj}} \newcommand{\mystack}[2]{\genfrac{}{}{0}{0}{#1}{#2}} \newcommand{\mystackthree}[3]{\mystack{\mystack{#1}{#2}}{#3}} \newcommand{\qimplies}{\quad\implies\quad} \newcommand{\qtext}[1]{\quad\text{#1}\quad} \newcommand{\qqtext}[1]{\qquad\text{#1}\qquad} \newcommand{\smalltext}[1]{{\small\text{#1}}} \newcommand{\svec}[1]{\,\vec{#1}} \newcommand{\querytext}[1]{\toggle{\text{?}\vphantom{\text{#1}}}{\text{#1}}\endtoggle} \newcommand{\query}[1]{\toggle{\text{?}\vphantom{#1}}{#1}\endtoggle} \newcommand{\smallquery}[1]{\toggle{\text{?}}{#1}\endtoggle} \newcommand{\bv}{\mathbf{v}} %\require{AMScd} $

Announcements:

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

Section 4.4

We're going to introduce a new concept that will turn out to be closely related to eigenvalues and eigenvectors.

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.

Diagonalization

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

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.

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?

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.