Math 1600 Lecture 36

$ \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 finish Section 5.4 and finish the course material. Re-read Chapters 1 through 5 for the final. Work through recommended homework questions. New practice questions are posted at the bottom of the exercises page.

Review Sessions: Wednesday, in class. Also: Friday, 3:30-4:30 and Saturday, 1:30-2:30, both in MC105B. Bring questions!

Final exam: Covers whole course, with an emphasis on the material after the midterm. It does not cover $\Z_m$, code vectors, Markov chains or network analysis. Everything else we covered in class is considered exam material. Questions are similar to textbook questions, midterm questions and quiz questions.

Review of Section 5.4 from last class

Section 5.4: Orthogonal Diagonalization of Symmetric Matrices

(Remember our convention that, unless we say otherwise, the entries of $A$ are assumed to be real.)

Symmetric matrices are important in applications. For example, in quantum theory, they correspond to observable quantities, and their eigenvalues are the possible values that can be observed.

Examples: $\bmat{rr} 1 & 2 \\ 2 & 3 \emat$, $\bmat{rr} 3 & 2 \\ 2 & 3 \emat$, $\bmat{rr} 1 & 0 \\ 0 & 3 \emat$, $\bmat{rrr} 1 & 2 & 3 \\ 2 & 4 & 5 \\ 3 & 5 & 6 \emat$.

Non-examples: $\bmat{rr} 3 & -2 \\ 2 & 3 \emat$, $\bmat{rrr} 1 & 2 & 3 \\ 5 & 4 & 5 \\ 3 & 2 & 6 \emat$.

Example 5.16: If possible, diagonalize $A = \bmat{rr} 1 & 2 \\ 2 & -2 \emat$.

We found that $A$ has real eigenvalues, is diagonalizable, and that the eigenvectors are orthogonal.

Definition: A square matrix $A$ is orthogonally diagonalizable if there exists an orthogonal matrix $Q$ such that $Q^T A Q$ is a diagonal matrix $D$.

New material

Notice that if $A$ is orthogonally diagonalizable, then $Q^T A Q = D$, so $A = Q D Q^T$. Therefore $$ \kern-6ex A^T = (Q D Q^T)^T = (Q^T)^T D^T Q^T = Q D Q^T = A. $$ We have proven:

The rest of this section is working towards proving that every symmetric matrix $A$ is orthogonally diagonalizable. I'll organize this a bit more efficiently than the textbook.

Theorem 5.19: If $A$ is a symmetric matrix, then eigenvectors corresponding to distinct eigenvalues of $A$ are orthogonal.

In non-symmetric examples we've seen earlier, the eigenvectors were not orthogonal.

Proof: Suppose $\vv_1$ and $\vv_2$ are eigenvectors corresponding to distinct eigenvalues $\lambda_1$ and $\lambda_2$. Then we have $$ \kern-7ex \begin{aligned} \lambda_1 (\vv_1 \cdot \vv_2) \ &= (\lambda_1 \vv_1) \cdot \vv_2 = (A \vv_1) \cdot \vv_2 = (A \vv_1)^T \vv_2 \\ &= \vv_1^T A^T \vv_2 = \vv_1^T (A \vv_2) = \vv_1^T \lambda_2 \vv_2 = \lambda_2 (\vv_1 \cdot \vv_2) \end{aligned} $$ So $(\lambda_1 - \lambda_2) (\vv_1 \cdot \vv_2) = 0$, which implies that $\vv_1 \cdot \vv_2 = 0$.$\quad\Box$

Theorem 5.18: If $A$ is a real symmetric matrix, then the eigenvalues of $A$ are real.

To prove this, we have to recall some facts about complex numbers. If $z = a + bi$, then its complex conjugate is $\bar{z} = a - bi$, which is the reflection in the real axis. So $z$ is real if and only if $z = \bar{z}$.

Proof: Suppose that $\lambda$ is an eigenvalue of $A$ with eigenvector $\bv$. Then the complex conjugate $\bar{\bv}$ is an eigenvector with eigenvalue $\bar{\lambda}$, since $$ A \bar{\bv} = \bar{A} \bar{\bv} = \overline{A \bv} = \overline{\lambda \bv} = \bar{\lambda} \bar{\bv} . $$ If $\lambda \neq \bar{\lambda}$, then Theorem 5.19 shows that $\bv \cdot \bar{\bv} = 0$.

But if $\bv = \ccolll {z_1} {\vdots} {z_n}$ then $\bar{\bv} = \ccolll {\bar{z}_1} {\vdots} {\bar{z}_n}$ and so $$ \kern-6ex \bv \cdot \bar{\bv} = z_1 \bar{z}_1 + \cdots + z_n \bar{z}_n = |z_1|^2 + \cdots + |z_n|^2 \neq 0 $$ since $\bv \neq \vec 0$. Therefore, $\lambda = \bar{\lambda}$, so $\lambda$ is real. $\quad\Box$

Example 5.17 and 5.18: The eigenvalues of $A = \bmat{rrr} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \emat$ are $1$ and $4$, with eigenspaces $$ E_1 = \span(\colll {-1} 0 1, \colll {-1} 1 0) \qtext{and} E_4 = \span(\colll 1 1 1) $$ We see that every vector in $E_1$ is orthogonal to every vector in $E_4$. (In fact, $E_1 = E_4^\perp$.)

But notice that the vectors in $E_1$ aren't necessarily orthogonal to each other. However, we can apply Gram-Schmidt to get an orthogonal basis for $E_1$: $$ \begin{aligned} \vv_1\ &= \vx_1 = \colll {-1} 0 1 \\ \vv_2\ &= \vx_2 - \frac{\vv_1 \cdot \vx_2}{\vv_1 \cdot \vv_1} \vv_1 \\ &= \colll {-1} 1 0 - \frac{1}{2} \colll {-1} 0 1 = \ccolll {-1/2} 1 {-1/2} \end{aligned} $$ We normalize the three basis eigenvectors and put them in the columns of a matrix $Q = \bmat{ccr} 1/\sqrt{3} & - 1/\sqrt{2} & -1/\sqrt{6} \\ 1/\sqrt{3} & 0 & \,\ph 2/\sqrt{6} \\ 1/\sqrt{3} & \ph 1/\sqrt{2} & -1/\sqrt{6} \\ \emat . $ Then $Q^T A Q = \bmat{rrr} 4 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \emat$, so $A$ is orthogonally diagonalizable.

The spectral theorem

Theorem 5.20 (The spectral theorem): Let $A$ be an $n \times n$ real matrix. Then $A$ is symmetric if and only if $A$ is orthogonally diagonalizable.

Proof: We have seen that every orthogonally diagonalizable matrix is symmetric.

We also know that if $A$ is symmetric, then its eigenvectors for distinct eigenvalues are orthogonal. So, by using Gram-Schmidt on the eigenvectors with the same eigenvalue, we get an orthogonal set of eigenvectors.

The only thing that isn't clear is that we get $n$ eigenvectors. The argument here is a bit complicated. See the text. $\quad\Box$.

Method for orthogonally diagonalizing a real symmetric $n \times n$ matrix A:
1. Find all eigenvalues. They will all be real, and the algebraic multiplicities will add up to $n$.
2. Find a basis for each eigenspace.
3. If an eigenspace has dimension greater than one, use Gram-Schmidt to create an orthogonal basis of that eigenspace.
4. Normalize all basis vectors. Put them in the columns of $Q$, and make the eigenvalues (in the same order) the diagonal entries of a diagonal matrix $D$.
5. Then $Q^T A Q = D$.

Note that $A$ can be expressed in terms of its eigenvectors $\vq_1, \ldots, \vq_n$ and eigenvalues $\lambda_1, \ldots, \lambda_n$ (repeated according to their multiplicity) as $$ \kern-7ex \begin{aligned} A\ &= Q D Q^T = [\, \vq_1 \cdots \vq_n \, ] \bmat{ccc} \lambda_1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \lambda_n \emat \ccolll {\vq_1^T} {\vdots} {\vq_n^T} \\ &= [\, \lambda_1 \vq_1 \cdots \lambda_n \vq_n \, ] \ccolll {\vq_1^T} {\vdots} {\vq_n^T} \\ &= \lambda_1 \vq_1 \vq_1^T + \lambda_2 \vq_2 \vq_2^T + \cdots + \lambda_n \vq_n \vq_n^T \end{aligned} $$ This is called the spectral decomposition of $A$.

Note that the $n \times n$ matrix $\vq_1 \vq_1^T$ sends a column vector $\vx$ in $\R^n$ to $\vq_1 \vq_1^T \vx = (\vq_1 \cdot \vx) \vq_1 = \proj_{\vq_1}(\vx)$, so it is orthogonal projection onto $\span(\vq_1)$. Thus you can compute $A \vx$ by projecting $\vx$ onto each $\vq_i$, multiplying by $\lambda_i$, and adding the results.

Example 5.20: Find a $2 \times 2$ matrix with eigenvalues 3 and -2 and corresponding eigenvectors $\coll 3 4$ and $\coll {-4} 3$.

Method 1: Let $P = \bmat{rr} 3 & -4 \\ 4 & 3 \emat$ and $D = \bmat{rr} 3 & 0 \\ 0 & -2 \emat$. Then $$ \begin{aligned} A\ &= P D P^{-1} = \bmat{rr} 3 & -4 \\ 4 & 3 \emat \bmat{rr} 3 & 0 \\ 0 & -2 \emat \bmat{rr} 3 & -4 \\ 4 & 3 \emat^{-1} \\ &= \bmat{rr} 9 & 8 \\ 12 & -6 \emat \frac{1}{25} \bmat{rr} 3 & 4 \\ -4 & 3 \emat \\ &= \frac{1}{25} \bmat{rr} -5 & 60 \\ 60 & -30 \emat = \bmat{rr} -1/5 & 12/5 \\ 12/5 & -6/5 \emat \end{aligned} $$ This didn't use anything from this section and works for any diagonalizable matrix.

Method 2: First normalize the eigenvectors to have length 1. Then use the spectral decomposition: $$ \kern-9ex \begin{aligned} A\ &= \lambda_1 \vq_1 \vq_1^T + \lambda_2 \vq_2 \vq_2^T \\ &= 3 \coll {3/5} {4/5} \bmat{rr} 3/5 & 4/5 \emat -2 \coll {-4/5} {3/5} \bmat{rr} -4/5 & 3/5 \emat \\ &= 3 \bmat{rr} 9/25 & 12/25 \\ 12/25 & 16/25 \emat -2 \bmat{rr} 16/25 & -12/25 \\ -12/25 & 9/25 \emat = \bmat{rr} -1/5 & 12/5 \\ 12/5 & -6/5 \emat \end{aligned} $$ This method only works because the given vectors are orthogonal.

True/false: The matrix $$ \bmat{rrrrr} 1 & 2 & 3 & 4 & 5 \\ 2 & 6 & 7 & 8 & 9 \\ 3 & 7 & 10 & 11 & 12 \\ 4 & 8 & 11 & 13 & 14 \\ 5 & 9 & 12 & 14 & 15 \emat $$ is diagonalizable.