Spectral Theory

The diagonalization notebook ended on a slightly sour note. Not every matrix is diagonalizable, and if we insist on working with real numbers (as we try to in this course), even more matrices fail. The $90^\circ$ rotation, for instance, has no real eigenvalues at all. \textit{Spectral theory} is the study of when, and how nicely, a matrix can be diagonalized. Here we focus on one case, which happens to be the nicest one possible: \textbf{real symmetric matrices}, i.e. real matrices with $A^T = A$. Recall the exploration at the end of the diagonalization notebook. For both symmetric matrices, the eigenvectors were perpendicular, and the eigenbasis grid was just a square grid turned on its side. That was no accident! By the end of this notebook we will see that every real symmetric matrix has real eigenvalues, a basis of perpendicular eigenvectors, and as a result, a diagonalization that is really just a rotation, a stretch, and a rotation back.

A priori, the eigenvalues of a real matrix are roots of its characteristic polynomial, and those roots can be complex (as they were for the rotation). So to show the eigenvalues of a symmetric matrix are real, we have to allow complex eigenvalues and eigenvectors for a moment, and then show that they could not have been complex after all. For a complex vector or matrix, we write $^*$ for the \textbf{conjugate transpose}: take the transpose and the complex conjugate of every entry, so that $\mathbf{x}^* = \overline{\mathbf{x}}^T$. For a scalar (a $1 \times 1$ matrix), this is just the conjugate, $\lambda^* = \overline{\lambda}$, and a scalar is real exactly when $\lambda^* = \lambda$. The conjugate transpose follows the same rule as the transpose, $(BC)^* = C^*B^*$. Notably, $$\mathbf{x}^*\mathbf{x} = \overline{x_1}x_1 + \cdots + \overline{x_n}x_n = |x_1|^2 + \cdots + |x_n|^2 = \|\mathbf{x}\|^2,$$ which is positive for any $\mathbf{x} \neq \mathbf{0}$. (This is why we need the conjugate. Without it, $\mathbf{x}^T\mathbf{x}$ can be zero for a nonzero complex vector: try $\mathbf{x} = (1, i)$.) Finally, if $A$ is real, conjugating does nothing, so $A^* = A^T$; and if $A$ is also symmetric, then $A^* = A^T = A$. \begin{lemma}\label{lem:real} If $A$ is a real symmetric matrix, then every eigenvalue of $A$ is real. Consequently, each eigenvalue has a real eigenvector. \end{lemma} \begin{proof} Suppose $A\mathbf{x} = \lambda\mathbf{x}$ for some $\lambda \in \C$ and some $\mathbf{x} \in \C^n$ with $\mathbf{x} \neq \mathbf{0}$. Using $A^* = A$ in the middle step, $$\lambda^*\|\mathbf{x}\|^2 = \lambda^*\mathbf{x}^*\mathbf{x} = (\lambda\mathbf{x})^*\mathbf{x} = (A\mathbf{x})^*\mathbf{x} = \mathbf{x}^*A^*\mathbf{x} = \mathbf{x}^*A\mathbf{x} = \mathbf{x}^*(\lambda\mathbf{x}) = \lambda\mathbf{x}^*\mathbf{x} = \lambda\|\mathbf{x}\|^2.$$ Since $\mathbf{x}$ is an eigenvector, $\mathbf{x} \neq \mathbf{0}$, so $\|\mathbf{x}\|^2 > 0$ and we can divide both sides by it to get $\lambda^* = \lambda$. That is, $\lambda$ is real.

For the second claim, $\lambda$ being real means $A - \lambda I$ is a real matrix, and it is singular since $\lambda$ is an eigenvalue. Row reducing a real matrix only ever uses real arithmetic, so its null space contains a nonzero real vector, which is a real eigenvector for $\lambda$. \end{proof} This also explains the rotation from the eigenvectors notebook. The $90^\circ$ rotation has eigenvalues $\pm i$, and sure enough, it is not symmetric: $$\begin{bmatrix} 0 & -1 \\ 1 & \phantom{-}0 \end{bmatrix}^T = \begin{bmatrix} \phantom{-}0 & 1 \\ -1 & 0 \end{bmatrix} \neq \begin{bmatrix} 0 & -1 \\ 1 & \phantom{-}0 \end{bmatrix}.$$ \begin{remark*} The proof above is quite slick, and it is fair to wonder how anyone would come up with it. Really, the idea is the following. We want to prove something about a \textit{scalar} ($\lambda^* = \lambda$), but all we are handed is the equation $A\mathbf{x} = \lambda\mathbf{x}$, which is about vectors and a matrix. So we need some way to turn vectors and a matrix into a single number. The expression $$\mathbf{y}^*A\mathbf{x} = (\text{row vector})(\text{matrix})(\text{column vector}) = (1 \times n)(n \times n)(n \times 1) = (1 \times 1)$$ does exactly that: it combines a row vector, a matrix, and a column vector, and returns a scalar.

Now take $\mathbf{y} = \mathbf{x}$, and evaluate the scalar $\mathbf{x}^*A\mathbf{x}$ in two ways. Letting $A$ act on the column vector to its right gives $\mathbf{x}^*(A\mathbf{x}) = \mathbf{x}^*(\lambda\mathbf{x}) = \lambda\|\mathbf{x}\|^2$. Letting $A$ act on the row vector to its left, and using $A = A^*$, gives $(\mathbf{x}^*A)\mathbf{x} = (\mathbf{x}^*A^*)\mathbf{x} = (A\mathbf{x})^*\mathbf{x} = \lambda^*\|\mathbf{x}\|^2$. These are the same number, so $\lambda\|\mathbf{x}\|^2 = \lambda^*\|\mathbf{x}\|^2$. The one-line proof is just these two computations glued together at $\mathbf{x}^*A\mathbf{x}$. We will use this exact trick again in the next lemma, this time with two different eigenvectors on either side of $A$. \end{remark*} From here on, \Cref{lem:real} lets us stay entirely in the real world: every eigenvalue is real, and we may always pick real eigenvectors. In particular, the conjugate transpose of a real vector is just its transpose, so we go back to writing $^T$.

\begin{lemma}\label{lem:orth} Let $A$ be a real symmetric matrix with $A\mathbf{x} = \lambda\mathbf{x}$ and $A\mathbf{y} = \mu\mathbf{y}$, where $\mathbf{x}, \mathbf{y}$ are real eigenvectors and $\lambda \neq \mu$. Then $\mathbf{y}^T\mathbf{x} = 0$, i.e. $\mathbf{x}$ and $\mathbf{y}$ are orthogonal. \end{lemma} \begin{proof} As in the remark above, evaluate the scalar $\mathbf{y}^TA\mathbf{x}$ in two ways. Letting $A$ act to the right, $$\mathbf{y}^TA\mathbf{x} = \mathbf{y}^T(\lambda\mathbf{x}) = \lambda\,\mathbf{y}^T\mathbf{x}.$$ Letting $A$ act to the left, and using $A = A^T$, $$\mathbf{y}^TA\mathbf{x} = \mathbf{y}^TA^T\mathbf{x} = (A\mathbf{y})^T\mathbf{x} = (\mu\mathbf{y})^T\mathbf{x} = \mu\,\mathbf{y}^T\mathbf{x}.$$ Subtracting the two, $(\lambda - \mu)\,\mathbf{y}^T\mathbf{x} = 0$. Since $\lambda \neq \mu$, we can divide by $\lambda - \mu$, leaving $\mathbf{y}^T\mathbf{x} = 0$. \end{proof} In a sense, both lemmas say the same thing: a symmetric matrix can be moved from one side of a dot product to the other, $(A\mathbf{y}) \cdot \mathbf{x} = \mathbf{y} \cdot (A\mathbf{x})$. This is exactly the step that fails for the not symmetric matrix in the diagonalization notebook, and sure enough, its eigenvectors $(1, 1)$ and $(2, -3)$ are not perpendicular.

Perpendicular eigenvectors are useful because we can also scale them to have length one, and a basis of perpendicular unit vectors gives a particularly nice matrix (see orthogonal bases and Gram–Schmidt). \begin{definition} A real $n \times n$ matrix $Q$ is \textbf{orthogonal} if $Q^TQ = I$, i.e. its columns $\mathbf{q}_1, \dots, \mathbf{q}_n$ form an orthonormal basis of $\R^n$. \end{definition} The two descriptions agree since the $(i, j)$ entry of $Q^TQ$ is $\mathbf{q}_i^T\mathbf{q}_j$, which is $1$ on the diagonal (unit length) and $0$ off of it (perpendicular). The important consequence is that $$Q^{-1} = Q^T.$$ That is, inverting an orthogonal matrix costs nothing: no row reduction, no determinant, just flip the matrix over its diagonal. Orthogonal matrices also preserve lengths, since $\|Q\mathbf{x}\|^2 = (Q\mathbf{x})^T(Q\mathbf{x}) = \mathbf{x}^TQ^TQ\mathbf{x} = \mathbf{x}^T\mathbf{x} = \|\mathbf{x}\|^2$, and (by the same computation with two vectors) angles. In $\R^2$, this means an orthogonal matrix is a rotation or a reflection, and in a diagonalization we can always make it a rotation by flipping the sign of one eigenvector. \begin{theorem}[Spectral theorem]\label{thm:spectral} A real $n \times n$ matrix $A$ is symmetric if and only if $$A = PDP^T, \qquad \text{equivalently} \qquad D = P^TAP,$$ for some orthogonal matrix $P$ and real diagonal matrix $D$. The columns of $P$ form an orthonormal eigenbasis of $A$, and $D$ has the corresponding eigenvalues on its diagonal. \end{theorem} We will mostly take this one on faith, but it is worth seeing how much of it we already have. One direction, that an orthonormal eigenbasis forces $A$ to be symmetric, is Problem 10.18 on Homework 10. For the other, suppose $A$ is symmetric with $n$ distinct eigenvalues. By \Cref{lem:real} they are all real with real eigenvectors, by \Cref{lem:orth} those eigenvectors are pairwise orthogonal, and dividing each by its length makes them orthonormal. So the matrix $P$ of these unit eigenvectors is orthogonal, and the diagonalization theorem gives $A = PDP^{-1} = PDP^T$. The genuinely hard part is a repeated eigenvalue: there, the theorem promises that a symmetric matrix still has "enough" eigenvectors (an eigenvalue repeated $k$ times has a $k$-dimensional eigenspace), and Gram–Schmidt inside each eigenspace makes them orthonormal. Proving that takes more work than we will do here. To reiterate the payoff: for a general diagonalizable matrix, $D = P^{-1}AP$ needs the inverse of $P$. For a symmetric matrix, $D = P^TAP$ only needs a transpose. \begin{example} Consider the symmetric matrix $$A = \frac{1}{8}\begin{bmatrix} 11 & 5 \\ 5 & 11 \end{bmatrix}.$$ As in the diagonalization notebook, clear the fraction first. The characteristic polynomial of $8A$ is $(11 - \mu)^2 - 25 = (\mu - 16)(\mu - 6)$, so $A$ has eigenvalues $\lambda_1 = \frac{16}{8} = 2$ and $\lambda_2 = \frac{6}{8} = \frac{3}{4}$, exactly the same as the matrix in Figure 1 there. Row reducing, $$8A - 16I = \begin{bmatrix} -5 & \phantom{-}5 \\ \phantom{-}5 & -5 \end{bmatrix} \;\Longrightarrow\; E_2 = \operatorname{span}\left\{\begin{bmatrix} 1 \\ 1 \end{bmatrix}\right\}, \qquad 8A - 6I = \begin{bmatrix} 5 & 5 \\ 5 & 5 \end{bmatrix} \;\Longrightarrow\; E_{3/4} = \operatorname{span}\left\{\begin{bmatrix} -1 \\ \phantom{-}1 \end{bmatrix}\right\}.$$ As promised by Lemma 2, $(1, 1) \cdot (-1, 1) = 0$. Both have length $\sqrt{2}$, so the unit eigenvectors are $\mathbf{u}_1 = \frac{1}{\sqrt{2}}(1, 1)$ and $\mathbf{u}_2 = \frac{1}{\sqrt{2}}(-1, 1)$, and $$P = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & -1 \\ 1 & \phantom{-}1 \end{bmatrix} = \begin{bmatrix} \cos 45^\circ & -\sin 45^\circ \\ \sin 45^\circ & \phantom{-}\cos 45^\circ \end{bmatrix}, \qquad D = \begin{bmatrix} 2 & 0 \\ 0 & \tfrac{3}{4} \end{bmatrix}, \qquad P^T = \frac{1}{\sqrt{2}}\begin{bmatrix} \phantom{-}1 & 1 \\ -1 & 1 \end{bmatrix}.$$ So $P$ is the rotation by $45^\circ$, and $P^T$ is the rotation back by $-45^\circ$. Multiplying out confirms $PDP^T = A$. \end{example} For comparison, recall the matrix from Figure 1 of the diagonalization notebook, which has the same eigenvalues and even shares the eigenline through $(1, 1)$. We call it $B$ here, and write its basis matrix as $M = \begin{bmatrix} \mathbf{v}_1 & \mathbf{v}_2 \end{bmatrix}$ to keep it apart from the orthogonal $P$: $$B = \frac{1}{4}\begin{bmatrix} 6 & 2 \\ 3 & 5 \end{bmatrix} = MDM^{-1}, \qquad M = \begin{bmatrix} 1 & -2 \\ 1 & \phantom{-}3 \end{bmatrix}, \qquad M^{-1} = \frac{1}{5}\begin{bmatrix} \phantom{-}3 & 2 \\ -1 & 1 \end{bmatrix}.$$ (We flipped the sign of $\mathbf{v}_2 = (2, -3)$, which is still an eigenvector, so that $M$, like $P$, does not reflect the plane.) Notice that $M^{-1}$ took real work to find, and $M^T$ is nowhere close to it.

The factorization $A\mathbf{x} = P(D(P^T\mathbf{x}))$ reads right to left as three steps. \begin{itemize} \item $P^T$ rotates by $-45^\circ$, carrying $\mathbf{u}_1, \mathbf{u}_2$ onto $\mathbf{e}_1, \mathbf{e}_2$. In terms of coordinates, $P^T\mathbf{x} = [\mathbf{x}]_\beta$, the coordinates of $\mathbf{x}$ in the eigenbasis. \item $D$ stretches by $2$ along the first axis and by $\frac{3}{4}$ along the second. \item $P$ rotates by $45^\circ$, putting the stretched axes back along $\mathbf{u}_1, \mathbf{u}_2$. \end{itemize} The same reading of $B\mathbf{x} = M(D(M^{-1}\mathbf{x}))$ also has three steps, and the middle one is identical. The difference is the first and last steps. The eigenvectors $\mathbf{v}_1, \mathbf{v}_2$ are neither perpendicular nor of length one, so $M^{-1}$ cannot simply turn them onto $\mathbf{e}_1, \mathbf{e}_2$. It has to shear and squash the whole plane to get them there, and $M$ has to undo all of it at the end. The figure below runs both side by side, with one slider for both. I invite you to step through it slowly, and to drag $\mathbf{x}$ around.

Some things to look for: \begin{itemize} \item After step 1, both purple grids land exactly on the faint standard grid. That is, both $P^T$ and $M^{-1}$ convert to eigenbasis coordinates. On the left the grid simply turns; on the right it gets sheared into place. \item The green circle stays a circle through step 1 on the left, since a rotation preserves lengths. On the right it is already squashed into an ellipse before $D$ has done anything. \item Step 2 is the same stretch on both sides. \item At the end, the circle has become an ellipse on both sides. On the left, the axes of the ellipse are exactly the eigenvectors, with half-lengths $2 \cdot 2 = 4$ and $2 \cdot \frac{3}{4} = \frac{3}{2}$. On the right, the axes of the ellipse do not line up with the eigenvectors at all. \end{itemize} To reiterate: every diagonalization is a change of basis, a stretch, and a change back. What being symmetric buys us is that the change of basis is a rotation, so it keeps the geometry intact (lengths and right angles), and undoing it is only a transpose.

There is a second, equally geometric way to read $A = PDP^T$. Writing $\mathbf{u}_1, \dots, \mathbf{u}_n$ for the orthonormal eigenvectors (the columns of $P$) and $\lambda_1, \dots, \lambda_n$ for their eigenvalues, the product can be rewritten as a sum, $$A = \lambda_1\mathbf{u}_1\mathbf{u}_1^T + \lambda_2\mathbf{u}_2\mathbf{u}_2^T + \cdots + \lambda_n\mathbf{u}_n\mathbf{u}_n^T,$$ which is called the \textbf{spectral decomposition} of $A$ (this is Problem 10.19 on Homework 10). The set of eigenvalues $\{\lambda_1, \dots, \lambda_n\}$ is often called the \textit{spectrum} of $A$, which is where the name spectral theory comes from. Notably, each $\mathbf{u}_i\mathbf{u}_i^T$ is an $n \times n$ matrix, and since $\|\mathbf{u}_i\| = 1$, it is exactly the projection matrix onto the line through $\mathbf{u}_i$ (recall orthogonal bases and projections): $$P_{\mathbf{u}_i} = \frac{\mathbf{u}_i\mathbf{u}_i^T}{\|\mathbf{u}_i\|^2} = \mathbf{u}_i\mathbf{u}_i^T, \qquad P_{\mathbf{u}_i}\mathbf{x} = (\mathbf{u}_i^T\mathbf{x})\,\mathbf{u}_i.$$ (Each of these has rank one, by Problem 10.1.) So the spectral decomposition says $$A\mathbf{x} = \lambda_1P_{\mathbf{u}_1}\mathbf{x} + \lambda_2P_{\mathbf{u}_2}\mathbf{x} + \cdots + \lambda_nP_{\mathbf{u}_n}\mathbf{x},$$ and we can read the action of $A$ on $\mathbf{x}$ in three steps: \begin{itemize} \item Project $\mathbf{x}$ onto each eigenline, i.e. drop a perpendicular from $\mathbf{x}$ onto the line through each $\mathbf{u}_i$. These pieces $P_{\mathbf{u}_i}\mathbf{x}$ add back up to $\mathbf{x}$. \item Each piece $P_{\mathbf{u}_i}\mathbf{x}$ lies in the eigenspace $E_{\lambda_i}$, so $A$ simply scales it by $\lambda_i$. \item Add the scaled pieces back together, which gives $A\mathbf{x}$. \end{itemize} In a sense, this is the same story as rotate, stretch, rotate back, just told in different words. The numbers $\mathbf{u}_i^T\mathbf{x}$ are exactly the entries of $P^T\mathbf{x}$ (the coordinates of $\mathbf{x}$ in the eigenbasis), multiplying by $\lambda_i$ is $D$, and putting $\lambda_i(\mathbf{u}_i^T\mathbf{x})\,\mathbf{u}_i$ back together is $P$. It is worth comparing with the not symmetric $B$. There we can still write $\mathbf{x} = c_1\mathbf{v}_1 + c_2\mathbf{v}_2$ and get $B\mathbf{x} = \lambda_1c_1\mathbf{v}_1 + \lambda_2c_2\mathbf{v}_2$ (see eigenbases in the diagonalization notebook). However, since $\mathbf{v}_1$ and $\mathbf{v}_2$ are not perpendicular, the pieces $c_1\mathbf{v}_1$ and $c_2\mathbf{v}_2$ are not found by dropping perpendiculars. We have to solve for $c_1, c_2$, which is exactly the work that $M^{-1}$ does. The figure below builds a symmetric $2 \times 2$ matrix from its spectrum: choose the direction of $\mathbf{u}_1$ (and $\mathbf{u}_2$ is perpendicular to it) and the two eigenvalues, then drag $\mathbf{x}$ around. The defaults give the matrix $A$ from the example above.

I invite you to try the following: \begin{itemize} \item Make $\lambda_2$ negative. The scaled piece $\lambda_2P_{\mathbf{u}_2}\mathbf{x}$ flips to the other side of the origin, and $A\mathbf{x}$ follows it. \item Set $\lambda_2 = 0$. Now $A\mathbf{x}$ always lands on the line through $\mathbf{u}_1$, no matter where $\mathbf{x}$ is, and $A = \lambda_1\mathbf{u}_1\mathbf{u}_1^T$ has rank one. The end of Homework 10 asks how the rank of $A$ relates to its eigenvalues in general, and this picture is a good place to start. \item Set $\lambda_1 = \lambda_2$. The matrix stops depending on the angle at all (why?). \item Turn $\mathbf{u}_1$ while keeping the eigenvalues fixed. The matrix changes, but it stays symmetric. \end{itemize}