% DEFINE some information that will be populated throughout the course notes.
\def \coursename {Advanced Linear Algebra}
\def \coursecode {MATH 3221}
\def \courseterm {Fall 2020}
\def \instructorname {Nathan Johnston}
% END DEFINITIONS


% IMPORT the course note formatting and templates
\input{course_notes_template}
% END IMPORT


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{chapter}{6} % Set to one less than the week number
\chapter{Schur Triangularization and \\ the Spectral Decomposition(s)}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\large This week we will learn about:

\begin{itemize}
	\item Schur triangularization,
	\item The Cayley--Hamilton theorem,
	\item Normal matrices, and
	\item The real and complex spectral decompositions.
\end{itemize}\bigskip\bigskip

\noindent Extra reading and watching:
\begin{itemize}
	\item Section 2.1 in the textbook
	\item Lecture videos \href{https://www.youtube.com/watch?v=cTCLCKaFzqw&list=PLOAf1ViVP13jdhvy-wVS7aR02xnDxueuL&index=26}{25}, \href{https://www.youtube.com/watch?v=yK08yrPk_ns&list=PLOAf1ViVP13jdhvy-wVS7aR02xnDxueuL&index=27}{26}, \href{https://www.youtube.com/watch?v=DcTASCmQnIc&list=PLOAf1ViVP13jdhvy-wVS7aR02xnDxueuL&index=28}{27}, \href{https://www.youtube.com/watch?v=6RnRn9QUw50&list=PLOAf1ViVP13jdhvy-wVS7aR02xnDxueuL&index=29}{28}, and \href{https://www.youtube.com/watch?v=WU6LCIdLB-M&list=PLOAf1ViVP13jdhvy-wVS7aR02xnDxueuL&index=30}{29} on YouTube
	\item \href{https://en.wikipedia.org/wiki/Schur_decomposition}{Schur decomposition} at Wikipedia
	\item \href{https://en.wikipedia.org/wiki/Normal_matrix}{Normal matrix} at Wikipedia
	\item \href{https://en.wikipedia.org/wiki/Spectral_theorem}{Spectral theorem} at Wikipedia
\end{itemize}\bigskip\bigskip

\noindent Extra textbook problems:
\begin{itemize}
	\item[$\star$] 2.1.1, 2.1.2, 2.1.5
	\item[$\phantom{\star}\star\star$] 2.1.3, 2.1.4, 2.1.6, 2.1.7, 2.1.9, 2.1.17, 2.1.19
	\item[$\star\star\star$] 2.1.8, 2.1.11, 2.1.12, 2.1.18, 2.1.21
	\item[$\skull$] 2.1.22, 2.1.26
\end{itemize}}


\newpage

We're now going to start looking at \textbf{matrix decompositions}, which are ways of writing down a matrix as a product of (hopefully simpler!) matrices. For example, we learned about diagonalization at the end of introductory linear algebra, which said that...

\horlines{5}
% We can write a matrix $A \in \M_n(\mathbb{F})$ in the form $A = PDP^{-1}$, where $P$ is invertible and $D$ is diagonal
% if and only if there is a basis of $\mathbb{F}^n$ consisting of eigenvectors of $A$.

\noindent While diagonalization let us do great things with certain matrices, it also raises some new questions:\smallskip

\horlines{6}
% 1:  What if $A$ is not diagonalizable---how ``close'' to diagonal can we make $D = P^{-1}AP$ when $P$ is invertible?
% 2: How simple can we make $A$ if we multiply by something other than $P$ and $P^{-1}$ on the left and right? For example, how simple can we make $A$ if we multiply by a unitary matrix on the left?
% Introduce terminology "similarity" or "similarity transformation"

Over the next few weeks, we will thoroughly investigate these types of questions, starting with this one:

\horlines{5}
% How simple we can make a matrix via a UNITARY similarity? That is, given a matrix $A \in \M_n(\mathbb{F})$, how simple can $U^*AU$ be if $U$ is a unitary matrix? Phrased differently, how simple can we make the standard matrix of a linear transformation $T : F^n \rightarrow F^n$ with respect to an orthonormal basis (rather than just \emph{any} basis)?


\newpage


\section*{Schur Triangularization}

We know that we cannot hope in general to get a diagonal matrix via unitary similarity (since not every matrix is diagonalizable via \emph{any} similarity). However, the following theorem says that we can get partway there and always get an upper triangular matrix.

\begin{theorem}[Schur Triangularization]
	Suppose $A \in \M_n(\C)$. Then there exists a unitary matrix $U \in \M_n(\C)$ and an upper triangular matrix $T \in \M_n(\C)$ such that\\[0.1cm]
	\[
	{}% A = UTU^*.
	\]
\end{theorem}

\begin{proof}
	We prove the result by induction on $n$ (the size of $A$). For the base case, we simply notice that the result is trivial if $n = 1$: every $1 \times 1$ matrix is upper triangular.
	
	\horlines{14}
	
	
	\newpage
	
	
	\horlines{5}\vspace*{-1.3cm}
	% KEY POINTS of inductive step: choose eigenvalue and UNIT eigenvector lambda, v. Put v as first column of unitary. Then induct and repeat on lower-right block after you do V^*AV.
%	For the inductive step, suppose that every $(n-1) \times (n-1)$ matrix can be upper triangularized. Well, recall that the Fundamental Theorem of Algebra tells us that $A \in \M_n(\C)$ has an eigenvalue $\lambda$, and there is an associated eigenvector $\v \in \C^n$. Furthermore, since $\v \neq \0$, we can scale $\v$ so that $\|\v\| = 1$ and then extend it to an orthonormal basis of $\C^n$ via the Gram--Schmidt process. In other words, we can find a unitary matrix $V \in \M_n(\C)$ with $\v$ as its first column:
%\[
%V = \big[ \ \v \ {\color{gray}|} \ V_2 \ \big],
%\]
%where $V_2 \in \M_{n,n-1}(\C)$ satisfies $V_2^*\v = \0$ (since $\v$ is orthogonal to every column of $V_2$). Then direct computation shows that\marginnote{The final step in this computation follows because $A\v = \lambda\v$, $\v^*\v = \|\v\|^2 = 1$, and $V_2^*\v = \0$.}[0.75cm]
%\begin{align*}
%	V^*AV = \big[ \ \v \ {\color{gray}|} \ V_2 \ \big]^*A\big[ \ \v \ {\color{gray}|} \ V_2 \ \big]
%	& = \left[\begin{array}{c}
%		\v^* \\\hline
%		V_2^* \\
%	\end{array}\right]\big[ \ A\v \ {\color{gray}|} \ AV_2 \ \big] \\
%	& = \left[\begin{array}{c|c}
%		\v^*A\v & \v^*AV_2 \\\hline
%		\lambda V_2^*\v & V_2^*AV_2
%	\end{array}\right]
%	= \left[\begin{array}{c|c}
%		\lambda & \v^*AV_2 \\\hline
%		\0 & V_2^*AV_2
%	\end{array}\right].
%\end{align*}
%We now apply the inductive hypothesis---since $V_2^*AV_2$ is an $(n-1) \times (n-1)$ matrix, there exists a unitary matrix $U_2 \in \M_{n-1}(\C)$ and an upper triangular $T_2 \in \M_{n-1}(\C)$ such that $V_2^*AV_2 = U_2T_2U_2^*$. Thus
%\begin{align*}
%	V^*AV = \left[\begin{array}{c|c}
%		\lambda & \v^*AV_2 \\\hline
%		\0 & U_2T_2U_2^*
%	\end{array}\right] = \left[\begin{array}{c|c}
%		1 & \0^T \\\hline
%		\0 & U_2
%	\end{array}\right]\left[\begin{array}{c|c}
%		\lambda & \v^*AV_2 \\\hline
%		\0 & T_2
%	\end{array}\right]\left[\begin{array}{c|c}
%		1 & \0^T \\\hline
%		\0 & U_2^*
%	\end{array}\right].
%\end{align*}
%
%By multiplying on the left by $V$ and on the right by $V^*$, we see that $A = UTU^*$, \marginnote{Recall from Exercise~\ref{exer:product_of_unitary} that the product of unitary matrices is unitary.}[0.25cm] where \[U = V\left[\begin{array}{c|c}
%1 & \0^T \\\hline
%\0 & U_2
%\end{array}\right] \quad \text{and} \quad T = \left[\begin{array}{c|c}
%\lambda & \v^*AV_2 \\\hline
%\0 & T_2
%\end{array}\right].\]
%Since $U$ is unitary and $T$ is upper triangular, this completes the inductive step and the proof.
\end{proof}

Let's make some notes about Schur triangularizations before proceeding...

\begin{itemize}
	\item The diagonal entries of $T$ are the eigenvalues of $A$. To see why, recall that the eigenvalues of a triangular matrix are its diagonal entries (theorem from previous course), and...
	
	\horlines{3}
	% Show that two matrices that are similar have the same eigenvalues, since det(A - lambda I) = det(UTU^* - lambda I) = det(uTu^* - UU^*) = det(U)det(T - lambda I)det(U^*) = det(T - lambda I).
	
	\item The other pieces of Schur triangularization are
	
	\horlines{3}
	% very non-unique---the unitary matrix $U$ and the entries in the strictly upper-triangular portion of $T$ can vary wildly.
	% Draw picture of A = UTU^* with diagonal of T highlighted and note it's the only unique part
	
	\item To compute a Schur decomposition, follow the method given in the proof of the theorem:
	
	\horlines{3}
	% Find an eigenvalue and eigenvector of an $n \times n$ matrix, an $(n-1) \times (n-1)$ matrix, and so on down to a $2 \times 2$ matrix.
	% OK, nevermind, don't bother. Schur triangularization is a theoretical tool, not a computational one.
\end{itemize}


\newpage


The beauty of Schur triangularization is that it applies to \emph{every} square matrix (unlike diagonalization), which makes it very useful when trying to prove theorems. For example...

\begin{theorem}[Trace and Determinant in Terms of Eigenvalues]
	Suppose $A \in \M_n(\C)$ has eigenvalues $\lambda_1, \lambda_2, \ldots, \lambda_n$. Then\\[0.1cm]
	\[
		{}% \[\det(A) = \lambda_1 \lambda_2 \cdots \lambda_n \qquad \text{and} \qquad \mathrm{tr}(A) = \lambda_1 + \lambda_2 + \cdots + \lambda_n.\]
	\]
\end{theorem}

\begin{proof}
	Use Schur triangularization to write $A = UTU^*$ with $U$ unitary and $T$ upper triangular. Then...
	
	\horlines{7}\vspace*{-1.3cm}
%	recall that the diagonal entries of $T$ are the eigenvalues of $A$. In particular,
%	\begin{align*}
%		\det(A) & = \det(UTU^*) & & \text{\color{gray}(Schur triangularization)} \\
%		& = \det(U)\det(T)\det(U^*) & & \text{\color{gray}(multiplicativity of $\det$)} \\
%		& = \det(UU^*)\det(T) & & \text{\color{gray}(multiplicativity of $\det$)} \\
%		& = \det(T) & & \text{\color{gray}($\det(UU^*) = \det(I) = 1$)} \\
%		& = \lambda_1 \lambda_2 \cdots \lambda_n. & & \text{\color{gray}(determinant of a triangular matrix)}
%	\end{align*}
%	The corresponding statement about the trace is proved analogously:
%	\begin{align*}
%		\mathrm{tr}(A) & = \mathrm{tr}(UTU^*) & & \text{\color{gray}(Schur triangularization)} \\
%		& = \mathrm{tr}(U^*UT) & & \text{\color{gray}(cyclic commutativity of trace)} \\
%		& = \mathrm{tr}(T) & & \text{\color{gray}($U^*U = I$)} \\
%		& = \lambda_1 + \lambda_2 + \cdots + \lambda_n. & & \text{\color{gray}(definition of trace)}\qedhere
%	\end{align*}
\end{proof}

As another application of Schur triangularization, we prove an important result called the Cayley--Hamilton theorem, which says that every matrix satisfies its own characteristic polynomial.

\begin{theorem}[Cayley--Hamilton]\label{thm:cayley_hamilton}
	Suppose $A \in \M_n(\C)$ has characteristic polynomial $p(\lambda) = \det(A - \lambda I)$. Then $p(A) = O$.
\end{theorem}

For example...

\horlines{4}
% Note what p(A) *is* in the first place, and note that P(A) = det(A - A) = 0 is not OK.
% Do a concrete example. Just ask students for a 2x2 matrix, compute its char poly and then plug A in.


\newpage



\begin{proof}[Proof of Theorem~\ref{thm:cayley_hamilton}.]
	Because we are working over $\C$, the Fundamental Theorem of Algebra says that we can factor the characteristic polynomial as a product of linear terms:
	
	\horlines{2}
	% p(\lambda) = (\lambda_1 - \lambda)(\lambda_2 - \lambda)\cdots(\lambda_n - \lambda), so
	% p(A) = (\lambda_1I - A)(\lambda_2I - A)\cdots(\lambda_nI - A).
	
	\noindent Well, let's Schur triangularize $A$:
	
	\horlines{17}\vspace*{-1.3cm}
%	 we write $A = UTU^*$ where $U,T \in \M_n(\C)$ are unitary and upper triangular, respectively. Then by factoring somewhat cleverly, we see that
%	\begin{align*}
%		p(A) & = (\lambda_1I - UTU^*)(\lambda_2I - UTU^*)\cdots(\lambda_nI - UTU^*) \\
%		& = (\lambda_1UU^* - UTU^*)(\lambda_2UU^* - UTU^*)\cdots(\lambda_nUU^* - UTU^*) \\
%		& = \big(U(\lambda_1I - T)U^*\big)\big(U(\lambda_2I - T)U^*\big)\cdots \big(U(\lambda_nI - T)U^*\big) \\
%		& = U(\lambda_1I - T)(\lambda_2I - T)\cdots (\lambda_nI - T)U^* \\
%		& = Up(T)U^*.
%	\end{align*}
%	
%	Thus it is enough to prove that $p(T) = O$. For simplicity, let's suppose that the diagonal entries of $T$ are in the same order that we have been using for the eigenvalues here (i.e., the first diagonal entry of $T$ is $\lambda_1$, the second is $\lambda_2$, and so on). Then
%	\begin{align*}
%		\lambda_1 I - T = \begin{bmatrix}
%			0 & * & \cdots & * \\
%			0 & \lambda_1-\lambda_2 & \cdots & * \\
%			\vdots & \vdots & \ddots & \vdots \\
%			0 & 0 & \cdots & \lambda_1 - \lambda_n
%		\end{bmatrix}, \ \lambda_2 I - T = \begin{bmatrix}
%			\lambda_2 - \lambda_1 & * & \cdots & * \\
%			0 & 0 & \cdots & * \\
%			\vdots & \vdots & \ddots & \vdots \\
%			0 & 0 & \cdots & \lambda_2 - \lambda_n
%		\end{bmatrix},
%	\end{align*}
%	and so on. We now claim that the left $k$ columns of $(\lambda_1I - T)(\lambda_2I - T)\cdots (\lambda_kI - T)$ consist entirely of zeroes whenever $1 \leq k \leq n$, and thus $p(T) = (\lambda_1I - T)(\lambda_2I - T)\cdots (\lambda_nI - T) = O$. Proving this claim is a straightforward (albeit rather ugly) matrix multiplication exercise, which we solve via induction.
%	
%	The base case $k = 1$ is straightforward, as we wrote down the matrix $\lambda_1 I - T$ above, and its leftmost column is indeed the zero vector. For the inductive step, define $T_k = (\lambda_1I - T)(\lambda_2I - T)\cdots (\lambda_kI - T)$ and suppose that the leftmost $k$ columns of $T_k$ consist entirely of zeroes. We know that each $T_k$ is upper triangular (since the product of upper triangular matrices is again upper triangular---see Exercise~??), so some rather unpleasant block matrix multiplication shows that
%	\begin{align*}
%		T_{k+1} & = T_k(\lambda_{k+1}I - T) \\
%		& = \left[\begin{array}{c|c}\mbox{\Large $O_k$} & \mbox{\LARGE $*$} \\\hline \mbox{\Large $O$} & \begin{matrix}* & * & \cdots & * \\
%				0 & * & \cdots & * \\
%				\vdots & \vdots & \ddots & \vdots \\
%				0 & 0 & \cdots & *\end{matrix}\end{array}\right]\left[\begin{array}{c|c|c}\mbox{\LARGE $*$} & \mbox{\LARGE $*$} & \mbox{\LARGE $*$} \\\hline \mbox{\Large $O$} & {}_{} \ \ {}_{}\begin{matrix}0\\
%				0\\
%				\vdots\\
%				0\end{matrix} & \begin{matrix}* & \cdots & * \\
%				\lambda_{k+1}-\lambda_{k+2} & \cdots & * \\
%				\vdots & \ddots & \vdots \\
%				0 & \cdots & \lambda_{k+1}-\lambda_{n}\end{matrix}\end{array}\right] \\
%		& = \left[\begin{array}{c|c|c}\mbox{\large $O_k$} & {}_{} \ {}_{}\begin{matrix}\0\end{matrix} & \mbox{\LARGE $*$} \\\hline \mbox{\Large $O$} & {}_{} \ {}_{}\begin{matrix}0\\
%				0\\
%				\vdots\\
%				0\end{matrix} & {}_{} \ {}_{}\begin{matrix}* & \cdots & * \\
%				* & \cdots & * \\
%				\vdots & \ddots & \vdots \\
%				0 & \cdots & *\end{matrix}\end{array}\right],
%	\end{align*}
%	which has its leftmost $k+1$ columns equal to the zero vector. This completes the inductive step and the proof.
% DON"T GO THROUGH FULL ARGUMENT IN CLASS. Just mention that left k columns equals 0, easy to prove by induction and "see" well enough in class.
\end{proof}


\newpage


One useful feature of the Cayley--Hamilton theorem is that if $A \in \M_n(\C)$ then it lets us write every power of $A$ as a linear combination of $I, A, A^2, \ldots, A^{n-1}$. In particular,

\horlines{2}
% the powers of $A$ all live within an $n$-dimensional subspace of the $n^2$-dimensional vector space $\M_n(\C)$.

\exx[9]{Use the Cayley--Hamilton theorem to come up with a formula for $A^4$ as a linear combination of $A$ and $I$, where \[A = \qquad \qquad \qquad {}_{}\]}
% Same 2x2 matrix as earlier.
% Here is how it goes for the matrix [1 2;3 4]
%	As noted earlier, the characteristic polynomial of $A$ is $p(\lambda) = \lambda^2 - 5\lambda - 2$, so $A^2 - 5A - 2I = O$. Rearranging somewhat gives $A^2 = 5A + 2I$. To get higher powers of $A$ as linear combinations of $A$ and $I$, just multiply this equation through by $A$:
%\begin{align*}
%A^3 & = 5A^2 + 2A = 5(5A + 2I) + 2A = 25A + 10I + 2A = 27A + 10I, \ \text{and} \\
%A^4 & = 27A^2 + 10A = 27(5A + 2I) + 10A = 135A + 54I + 10A \\
%& = 145A + 54I.
%\end{align*}

\exx[5]{Use the Cayley--Hamilton theorem to find the inverse of the same matrix.}
% Same 2x2 matrix as earlier.
%	As before, we know from the Cayley--Hamilton theorem that $A^2 - 5A - 2I = O$. If we solve this equation for $I$, we get $I = (A^2 - 5A)/2$. Factoring this equation gives $I = A(A - 5I)/2$, from which it follows that $A$ is invertible, with inverse
%\[
%A^{-1} = (A - 5I)/2 = \frac{1}{2}\left(\begin{bmatrix}1 & 2 \\ 3 & 4\end{bmatrix} - \begin{bmatrix}5 & 0 \\ 0 & 5\end{bmatrix}\right) = \frac{1}{2}\begin{bmatrix} -4 & 2 \\ 3 & -1\end{bmatrix}.
%\]
% Alternatively, first check that $\det(A) \neq 0$ so that you know $A^{-1}$ exists, and then find it by multiplying both sides of $A^2 - 5A - 2I = O$ by $A^{-1}$.


\newpage


\section*{Normal Matrices and the Spectral Decomposition}

We now start looking at when Schur triangularization actually results in a \emph{diagonal} matrix, rather than just an upper triangular one. We first need to introduce another new family of matrices:

\begin{definition}[Normal Matrix]\label{defn:normal_matrix}
	A matrix $A \in \M_n(\C)$ is called \textbf{normal} if $A^*A = AA^*$.
\end{definition}

Many of the important families of matrices that we are already familiar with are normal. For example...

\horlines{6}
% unitary, hermitian, skew-hermitian, diagonal

\noindent However, there are also other matrices that are normal:

\exx[6]{Show that the matrix $\displaystyle A = \begin{bmatrix}1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1\end{bmatrix}$ is normal.}
% A^*A = \begin{bmatrix}1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1\end{bmatrix}\begin{bmatrix}1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1\end{bmatrix} = \begin{bmatrix}2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2\end{bmatrix} = AA^*.


\newpage

Our primary interest in normal matrices comes from the following theorem, which says that normal matrices are exactly those that can be diagonalized by a unitary matrix:

\begin{theorem}[Complex Spectral Decomposition]
	Suppose $A \in \M_n(\C)$. Then there exists a unitary matrix $U \in \M_n(\C)$ and diagonal matrix $D \in \M_n(\C)$ such that\\[0.1cm]
	\[
		{} %A = UDU^*
	\]
	if and only if $A$ is normal (i.e., $A^*A = AA^*$).
\end{theorem}

\noindent In other words, normal matrices are the ones with a diagonal Schur triangularization.

\begin{proof}
	To see the ``only if'' direction, we just compute	
	
	\horlines{15}\vspace*{-1.3cm}
%\begin{align*}
%A^*A & = (UDU^*)^*(UDU^*) = UD^*U^*UDU^* = UD^*DU^* = U|D|^2U^*, \quad \text{and} \\
%AA^* & = (UDU^*)(UDU^*)^* = UDU^*UD^*U^* = UDD^*U^* = U|D|^2U^*.
%\end{align*}
%Thus $A^*A = AA^*$, so $A$ is normal.
%
%For the ``if'' direction, use Schur triangularization to write $A = UTU^*$, where $U$ is unitary and $T$ is upper triangular. Since $A$ is normal, we know that $A^*A = AA^*$. Thus
%\begin{align*}
%UTT^*U^* = (UTU^*)(UTU^*)^* = AA^* = A^*A & = (UTU^*)^*(UTU^*) = UT^*TU^*.
%\end{align*}
%Multiplying on the left by $U^*$ and on the right by $U$ then shows that $T^*T = TT^*$ (i.e., $T$ is also normal).
%
%Let's compute the diagonal entries of $T^*T$ and $TT^*$, starting with $[T^*T]_{1,1} = [TT^*]_{1,1}$. It is perhaps useful to write out the matrices $T$ and $T^*$ to highlight what this tells us:
% DRAW matrices
%Since $[T^*T]_{1,1} = [TT^*]_{1,1}$, this tells us that $|t_{1,1}|^2 = |t_{1,1}|^2 + |t_{1,2}|^2 + \cdots + |t_{1,n}|^2$. Since each term in that sum is non-negative, it follows that $|t_{1,2}|^2 = \cdots = |t_{1,n}|^2 = 0$. In other words, the only non-zero entry in the first row of $T$ is the $(1,1)$-entry.
%
%Now let's compute $[T^*T]_{2,2} = [TT^*]_{2,2}$. Again, direct computation shows that $|t_{2,2}|^2 = |t_{2,2}|^2 + |t_{2,3}|^2 + \cdots + |t_{2,n}|^2$. Since each term in this sum is non-negative, it follows that $|t_{2,3}|^2 = \cdots = |t_{2,n}|^2 = 0$. In other words, the only non-zero entry in the second row of $T$ is the $(2,2)$-entry.
%
%By repeating this argument for $[T^*T]_{k,k} = [TT^*]_{k,k}$ for $3 \leq k \leq n$, we similarly see that all of the off-diagonal entries in $T$ equal $0$, so $T$ is diagonal. Thus we can simply choose $D = T$, and the proof is complete.
\end{proof}


\newpage


While we proved the spectral decomposition via Schur triangularization, that is not how it is computed in practice. Instead, we notice that the spectral decomposition is a special case of diagonalization where the invertible matrix that does the diagonalization is unitary, so we compute it via eigenvalues and eigenvectors (like we did for diagonalization last semester). Just be careful to choose the eigenvectors to have length~$1$ and be mutually orthogonal.

\exx[18]{Find a spectral decomposition of the matrix...} % Ask students for a 2x2 matrix. MAKE SURE IT IS NOT SYMMETRIC, but it should be real. Want complex numbers in decompositions. Work through the details. Example given below.
%	We start by finding its eigenvalues:
%\begin{align*}
%\det(A - \lambda I) & = \det\left(\begin{bmatrix}
%1-\lambda & 2 \\ 2 & 1-\lambda
%\end{bmatrix}\right) \\
%& = (1-\lambda)^2 - 4 = \lambda^2 - 2\lambda - 3.
%\end{align*}
%Setting this polynomial equal to $0$ and solving (either via factoring or the quadratic equation) gives $\lambda = -1,3$ as the eigenvalues of $A$.
%
%For the eigenvectors, we solve the equations $A - \lambda I = 0$ for each of $\lambda = -1$ and $\lambda = 3$.\smallskip
%
%\noindent $\lambda = -1$: The system of equations has the form
%\begin{align*}
%\begin{bmatrix}
%2 & 2 \\ 2 & 2
%\end{bmatrix}\begin{bmatrix}
%v_1 \\ v_2
%\end{bmatrix} = \begin{bmatrix}
%0 \\ 0
%\end{bmatrix}.
%\end{align*}
%Solving this linear system gives $v_2 = -v_1$, so any vector of the form $(v_1,-v_1)$ (with $v_1 \neq 0$) is an eigenvector associated with this eigenvalue. \marginnote{We could have also chosen $v_1 = -1/\sqrt{2}$.} However, we want to choose it to have length~$1$, since we want the eigenvectors to form an orthonormal basis of $\C^n$. Thus we choose $v_1 = 1/\sqrt{2}$, so that the eigenvector is $(1,-1)/\sqrt{2}$.\smallskip
%
%\noindent $\lambda = 3$: The system of equations has the form
%\begin{align*}
%\begin{bmatrix}
%-2 & 2 \\ 2 & -2
%\end{bmatrix}\begin{bmatrix}
%v_1 \\ v_2
%\end{bmatrix} = \begin{bmatrix}
%0 \\ 0
%\end{bmatrix}.
%\end{align*}
%Solving this linear system gives $v_2 = v_1$, so we choose $(1,1)/\sqrt{2}$ to be our (unit length) eigenvector.\smallskip
%
%To construct a spectral decomposition of $A$, we then place the eigenvalues as the diagonal entries in a diagonal matrix $D$, and we place the associated eigenvectors as columns (in the same order) in a matrix $U$:
%\begin{align*}
%D = \begin{bmatrix}
%-1 & 0 \\ 0 & 3
%\end{bmatrix}, \quad U = \frac{1}{\sqrt{2}}\begin{bmatrix}
%1 & 1 \\ -1 & 1
%\end{bmatrix}.
%\end{align*}
%It is then straightforward to verify that $U$ is indeed unitary, and $A = UDU^*$, so we have found a spectral decomposition of $A$.


\newpage


\exx[17]{Find a spectral decomposition of the matrix\[A = \begin{bmatrix}
	1 & 2 & 2 \\
	2 & 1 & 2 \\
	2 & 2 & 1    
	\end{bmatrix}.\]}

% Maybe just show the eigenvalues/eigenvectors rather than working through them?
% EIGS:  5, (1,1,1)
%       -1, v_2(-1,1,0) + v_3(-1,0,1)   (choose (v-1,v_2) = (1,\pm 1))
%	Since this matrix is Hermitian (and thus normal), we know that it will have a spectral decomposition, and furthermore will have real eigenvalues. To actually find them, we carry out the same procedure as always:
%\begin{align*}
%\det(A - \lambda I) & = \det\left(\begin{bmatrix}
%1-\lambda & 2 & 2 \\
%2 & 1-\lambda & 2 \\
%2 & 2 & 1-\lambda
%\end{bmatrix}\right) \\
%& = (1-\lambda)^3 + 8 + 8 - 4(1-\lambda) - 4(1-\lambda) - 4(1-\lambda) \\
%& = (1+\lambda)^2(5-\lambda).
%\end{align*}
%Setting the above characteristic polynomial equal to $0$ gives $\lambda = -1$ (with multiplicity $2$) or $\lambda = 5$ (with multiplicity $1$). For the eigenvectors, we solve the equations $A - \lambda I = 0$ for each of $\lambda = 5$ and $\lambda = -1$.\smallskip
%
%\noindent $\lambda = 5$: The system of \marginnote{I'm glad we're not doing this for a $4 \times 4$ matrix. We'll save that for the exercises.} equations has the form
%\begin{align*}
%\begin{bmatrix}
%-4 & 2 & 2 \\ 2 & -4 & 2 \\ 2 & 2 & -4
%\end{bmatrix}\begin{bmatrix}
%v_1 \\ v_2 \\ v_3
%\end{bmatrix} = \begin{bmatrix}
%0 \\ 0 \\ 0
%\end{bmatrix}.
%\end{align*}
%Solving this linear system gives $v_1 = v_2 = v_3$, so any vector of the form $(v_1,v_1,v_1)$ (with $v_1 \neq 0$) is an eigenvector associated with this eigenvalue. However, we want to choose it to have length~$1$, so we choose $v_1 = 1/\sqrt{3}$, so that the eigenvector is $(1,1,1)/\sqrt{3}$.\smallskip
%
%\noindent $\lambda = -1$: The system of equations has the form
%\begin{align*}
%\begin{bmatrix}
%2 & 2 & 2 \\ 2 & 2 & 2 \\ 2 & 2 & 2
%\end{bmatrix}\begin{bmatrix}
%v_1 \\ v_2 \\ v_3
%\end{bmatrix} = \begin{bmatrix}
%0 \\ 0 \\ 0
%\end{bmatrix}.
%\end{align*}
%Solving this linear system gives $v_1 = -v_2-v_3$, so any vector of the form $v_2(-1,1,0) + v_3(-1,0,1)$ is an eigenvector associated with this eigenvalue. Since this eigenspace has dimension $2$, we have to choose two eigenvectors, and we furthermore have to be careful to choose them to form an orthonormal basis of the space (i.e., they must be orthogonal to each other, and we must scale them each to have length $1$).
%
%There are many possible pairs of orthogonal eigenvectors to choose from, but one of the easiest pairs to ``eyeball'' is $\{(-2,1,1),(0,1,-1)\}$ (which correspond to $(v_2,v_3) = (1,1)$ and $(v,2,v_3) = (1,-1)$, respectively). After normalizing these eigenvectors, we get $\{(-2,1,1)/\sqrt{6},(0,1,-1)/\sqrt{2}\}$ as the orthonormal basis of this eigenspace.\smallskip
%
%To construct a spectral decomposition of $A$, we then place the eigenvalues as the diagonal entries in a diagonal matrix $D$, and we place the associated eigenvectors as columns (in the same order) in a matrix $U$: \marginnote{Note that we pulled a common factor of $1/\sqrt{6}$ outside of $U$, which makes its columns look slightly different from what we saw when computing the eigenvectors.}
%\begin{align*}
%D = \begin{bmatrix}
%5 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & -1
%\end{bmatrix}, \quad U = \frac{1}{\sqrt{6}}\begin{bmatrix}
%\sqrt{2} & -2 & 0 \\ \sqrt{2} & 1 & \sqrt{3} \\ \sqrt{2} & 1 & -\sqrt{3}
%\end{bmatrix}.
%\end{align*}
%To double-check our work, we could verify that $U$ is indeed unitary, and $A = UDU^*$, so we have indeed found a spectral decomposition of $A$.

Sometimes, we can just ``eyeball'' an orthonormal set of eigenvectors, but if we can't, we can instead apply the Gram--Schmidt process to any basis of the eigenspace.


\newpage



\section*{The Real Spectral Decomposition}

In the previous example, the spectral decomposition ended up making use only of real matrices. We now note that this happened because the original matrix was symmetric:

\begin{theorem}[Real Spectral Decomposition]
	Suppose $A \in \M_n(\R)$. Then there exists a unitary matrix $U \in \M_n(\R)$ and diagonal matrix $D \in \M_n(\R)$ such that\\[0.1cm]
	\[
		{} %A = UDU^T
	\]
	if and only if $A$ is symmetric (i.e., $A^T = A$).
\end{theorem}

To give you a rough idea of why this is true, we note that every Hermitian (and thus every symmetric) matrix has real eigenvalues:

\horlines{3}
% Proof: if lambda an EV with vector v, then lambda v^*v = v^*Av = v^*A^*v = (v^*Av)^* = (lambda v^*v)^*, so lambda = overline(lambda), so lambda is real.

It follows that if $A$ is Hermitian then we can choose the ``$D$'' piece of the spectral decomposition to be real. Also, it should not be too surprising, that if $A$ is \emph{real} and Hermitian (i.e., symmetric) that we can choose the ``$U$'' piece to be real as well.\\

We thus get the following $3$ types of spectral decompositions for different types of matrices:

\horlines{7}
% Table from textbook with normal, hermitian, and real symmetric matrices.


\newpage


Geometrically, the real spectral decomposition says that real symmetric matrices are exactly those that act as follows:

\horlines{14}
% Rotate, stretch, rotate back. Say in words, then draw.

\end{document}