
\section*{ Diagonalizing Symmetric Matrices }

Symmetric matrices have many applications.  For example, if we consider the shortest distance between pairs of important cities, we might get a table like this:
\[
\begin{array}{c|ccc}
 & \text{Davis} & \text{Seattle} 
& \text{San Francisco} \\ \hline
\text{Davis} & 0 & 2000 & 80 \\
\text{Seattle} & 2000 & 0 & 2010 \\
\text{San Francisco} & 80 & 2010 & 0
\end{array}
\]
Encoded as a matrix, we obtain:
\[
M=\begin{pmatrix}
0 & 2000 & 80 \\
2000 & 0 & 2010 \\
80 & 2010 & 0
\end{pmatrix}=M^T.
\]

\begin{definition}
A matrix is \emph{symmetric}\index{Symmetric matrix} if it obeys
\[
M=M^T.
\]
\end{definition}

One very nice property of symmetric matrices is that they always have real eigenvalues.  The general proof is an exercise, but here's an example for $2\times 2$ matrices.

\begin{example}
For a general symmetric $2\times 2$ matrix, we have:
\begin{eqnarray*}
P_\lambda \begin{pmatrix} a & b \\ b& d \end{pmatrix}
 &=&
\det\begin{pmatrix}\lambda-a&-b\\-b&\lambda-d \end{pmatrix}\\
&=& (\lambda-a)(\lambda-d)-b^2 \\
&=& \lambda^2-(a+d)\lambda-b^2+ad\\
\Rightarrow \lambda &=& \frac{a+d}{2}\pm \sqrt{b^2+\left(\frac{a-d}{2}\right)^2}.
\end{eqnarray*}
Notice that the discriminant $4b^2+(a-d)^2$ is always positive, so that the eigenvalues must be real.
\end{example}

Now, suppose a symmetric matrix $M$ has two distinct eigenvalues $\lambda \neq \mu$ and eigenvectors $x$ and $y$:
\[
Mx=\lambda x, \qquad My=\lambda y.
\] 


%Checked Through Here!!!!


Consider the dot product $x\dotprod y = x^Ty = y^Tx$.  And now calculate:
\begin{eqnarray*}
x^TM y &=& x^T\mu y = \mu x\dotprod y, \text{ and }\\[3mm]
x^TM y &=& (y^TMx)^T \text{ (by transposing a $1\times 1$ matrix)}\\[1mm]
       &=& x^TM^Ty \\
       &=& x^TMy \\
       &=& x^T\lambda y \\
       &=& \lambda x\dotprod y.
\end{eqnarray*}
Subtracting these two results tells us that:
\begin{eqnarray*}
0 &=& x^TMy-x^TMy=(\mu-\lambda)\,x\dotprod y.
\end{eqnarray*}
Since $\mu$ and $\lambda$ were assumed to be distinct eigenvalues, $\lambda-\mu$ is non-zero, and so $x\dotprod y=0$.  Then we have proved the following theorem.

\begin{theorem}
Eigenvectors of a symmetric matrix with distinct eigenvalues are orthogonal.
\end{theorem}

\begin{example}
The matrix $M=\begin{pmatrix}2&1\\1&2\end{pmatrix}$
has eigenvalues determined by
\[
\det(M-\lambda)=(2-\lambda)^2-1=0.
\] 
Then the eigenvalues of $M$ are $3$ and $1$, and the associated eigenvectors turn out to be 
$\colvec{1\\1}$ and $\colvec{1\\-1}$.  It is easily seen that these eigenvectors are orthogonal: 
\[
\colvec{1\\1} \dotprod \colvec{1\\-1}=0
\]
\end{example}

Last lecture we saw that the matrix $P$ built from orthonormal basis vectors $\{v_1,\ldots, v_n \}$
\[
P=\rowvec{v_1 & \ldots & v_n}
\]
was an orthogonal matrix:
\[
P^{-1}=P^T, \text{ or } PP^T=I=P^TP.
\]

Moreover, given any (unit) vector $x_1$, one can always find vectors $x_2$, $\ldots$, $x_n$ such that $\{x_1,\ldots, x_n \}$ is an orthonormal basis.  (Such a basis can be obtained using the ``Gram-Schmidt'' procedure,
\edz{Hyperlink to notes24!}
which we will present later.)

Now suppose $M$ is a symmetric $n\times n$ matrix and $\lambda_1$ is an eigenvalue with eigenvector $x_1$.  Let the square matrix of column vectors $P$ be the following:
\[
P=\rowvec{x_1 & x_2 & \ldots & x_n},
\]
where $x_1$ through $x_n$ are orthonormal, and $x_1$ is an eigenvector for $M$, but the others are not necessarily eigenvectors for $M$.  Then
\[
MP=\rowvec{\lambda_1 x_1 & Mx_2 & \ldots & Mx_n}.
\]
But $P$ is an orthogonal matrix, so $P^{-1}=P^T$.  Then:
\begin{eqnarray*}
P^{-1}=P^T &=& \colvec{x_1^T\\ \vdots \\ x_n^T} \\
\Rightarrow P^TMP &=& \begin{pmatrix}
  x_1^T\lambda_1x_1  & * & \ldots & *\\
  x_2^T\lambda_1x_1  & * & \ldots & *\\
  \vdots             &   & & \vdots\\
   x_n^T\lambda_1x_1 & * & \ldots & *\\
  \end{pmatrix}\\
&=& \begin{pmatrix}
  \lambda_1  & * & \ldots & *\\
  0  & * & \ldots & *\\
  \vdots             & *  & & \vdots\\
  0 & * & \ldots & *\\
  \end{pmatrix}\\
&=& \begin{pmatrix}
  \lambda_1  & 0 & \ldots & 0\\
  0          & & & \\
  \vdots     & & \hat{M} & \\
  0          & & & \\
  \end{pmatrix}\\
\end{eqnarray*}
The last equality follows since $P^TMP$ is symmetric.  The asterisks in the matrix are where ``stuff'' happens; this extra information is denoted by $\hat{M}$ in the final equation.  We know nothing about $\hat{M}$ except that it is an $(n-1)\times (n-1)$ matrix and that it is symmetric.  But then, by finding an (unit) eigenvector for $\hat{M}$, we could repeat this procedure successively.  The end result would be a diagonal matrix with eigenvalues of $M$ on the diagonal.  Then we have proved a theorem.

\begin{theorem}
Every symmetric matrix is similar to a diagonal matrix of its eigenvalues.  In other words,
\[
M=M^T \Rightarrow M=PDP^T
\]
where $P$ is an orthogonal matrix and $D$ is a diagonal matrix whose entries are the eigenvalues of $M$.
\end{theorem}

To diagonalize a real symmetric matrix, begin by building an orthogonal matrix from an orthonormal basis of eigenvectors.

\begin{example}
The symmetric matrix 
$M=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ has eigenvalues $3$ and $1$ with eigenvectors $\colvec{1\\1}$ and $\colvec{1\\-1}$ respectively.  From these eigenvectors, we normalize and build the orthogonal matrix:
\[
P = \begin{pmatrix}
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\[1mm]
\frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}}
\end{pmatrix}
\]
Notice that $P^TP=I_2$.  Then:
\[
MP = \begin{pmatrix}
\frac{3}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\[1mm]
\frac{3}{\sqrt{2}} & \frac{-1}{\sqrt{2}}
\end{pmatrix} = 
\begin{pmatrix}
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\[1mm]
\frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}}
\end{pmatrix} \begin{pmatrix}
3 & 0 \\
0 & 1
\end{pmatrix}.
\]
In short, $MP=DP$, so $D=P^TMP$.  Then $D$ is the diagonalized form of $M$ and $P$ the associated change-of-basis matrix from the standard basis to the basis of eigenvectors.
\end{example}















\section*{References}
\begin{itemize}
\item Hefferon, Chapter Three, Section V: Change of Basis
\end{itemize}

Wikipedia:
\begin{itemize}
\item \href{http://en.wikipedia.org/wiki/Symmetric_matrix}{Symmetric Matrix}
\item \href{http://en.wikipedia.org/wiki/Diagonalizable_matrix}{Diagonalizable Matrix}
\item \href{http://en.wikipedia.org/wiki/Similar_matrix}{Similar Matrix}
\end{itemize}


\section*{Review Questions}

\begin{enumerate}
\item (On Reality of Eigenvectors) \begin{itemize}
\item[$i.$] 
Suppose $z=x+iy$ where $x,y \in \Re, i=\sqrt{-1}$, and $\overline{z}=x-iy$.  Compute $ \overline{\overline{z}}$.  What can you say about $z\overline{z}$ and $\overline{z}z$?  This operation is called \emph{complex conjugation}.

\item[$ii.$] What can you say about complex numbers $\lambda$ that obey $\lambda=\overline{\lambda}$?

\item[$iii.$] Let $x=\colvec{z^1\\ \vdots \\ z^n}\in \C^n$.  Let $x^\dagger=\rowvec{\overline{z^1}& \ldots & \overline{z^n}}\in \C^n$.  Compute $x^\dagger x$.  What can you say about the result?

\item[$iv.$] Suppose $M=M^T$ is an $n\times n$ symmetric matrix with real entries.  Let $\lambda$ be an eigenvalue of $M$ with eigenvector $x$, so $Mx=\lambda x$. Compute:
\[
\frac{x^\dagger Mx}{x^\dagger x}
\]

\item[$v.$] Suppose $\Lambda$ is a $1\times 1$ matrix.  What is $\Lambda^T$?

\item[$vi.$] What is the size of the matrix $x^\dagger Mx$?

\item[$vii.$] For any matrix (or vector) $N$, we can compute $\overline{N}$ by applying complex conjugation to each entry of $N$.
Compute $\overline{(x^\dagger)^T}$.  
Then compute $\overline{(x^\dagger M x)^T}$.

\item[$viii.$] Show that $\lambda=\overline{\lambda}$.  What does this say about $\lambda$?
\end{itemize}

\item Let $x_1=\colvec{a\\ b \\ c}$, where $a^2+b^2+c^2=1$.  Find vectors $x_2$ and $x_3$ such that $\{x_1,x_2,x_3\}$ is an orthonormal basis for $\Re^3$.

\item What can you say about the sum of the dimensions of the eigenspaces of a real symmetric matrix? 

\end{enumerate}

\newpage
