\documentclass[10pt]{article}
\usepackage{amsmath,amsfonts}

\newcommand{\x}{\boldsymbol{x}}
\renewcommand{\a}{\boldsymbol{a}}
\renewcommand{\b}{\boldsymbol{b}}
\renewcommand{\c}{\boldsymbol{c}}
\renewcommand{\v}{\boldsymbol{v}}
\newcommand{\e}{\boldsymbol{e}}

\newcommand{\R}{\mathbb{R}}

\renewcommand{\theenumi}{\roman{enumi}}
\renewcommand{\labelenumi}{(\theenumi)}

\begin{document}
\title{Diagonalization}
\author{Marcel Oliver}
\date{ESM 2B, Spring 2003}
\maketitle

\section{Main Idea}

Given a matrix $A\in M(n\times n)$, is it possible to find a basis in
which the associated linear transformation is represented by a
diagonal matrix?  In other words, can we find an invertible matrix $S$
such that
\begin{equation}
  \label{e.d}
  D = S^{-1}AS
\end{equation}
is diagonal?  Writing
\[
  D = 
  \begin{pmatrix}
    \lambda_1 & & 0 \\
    & \ddots & \\
    0 & & \lambda_n
  \end{pmatrix}
  \quad \text{and} \quad
  S =
  \begin{pmatrix}
  | && | \\
  \v_1 & \cdots & \v_n \\
  | && |
  \end{pmatrix} \,,
\]
i.e.\ $\v_1,\dots,\v_n$ are the columns of the matrix $S$, equation
\eqref{e.d} can be written $SD=AS$, or
\[
 \begin{pmatrix}
  | && | \\
  \lambda_1 \v_1 & \cdots & \lambda_n \v_n \\
  | && |
  \end{pmatrix}
  = A \,
  \begin{pmatrix}
  | && | \\
  \v_1 & \cdots & \v_n \\
  | && |
  \end{pmatrix} \,.  
\]
If we separate this matrix equation $n$ column vector equations, we
get
\[
  \lambda_1 \v_1 = A \v_1 \,, \dots, 
  \lambda_n \v_n = A \v_n \,.
\]
In other words, the entries on the diagonal of $D$ are the eigenvalues
of $A$, and the columns of $S$ are the corresponding eigenvectors.
Therefore, our task is the following:
\begin{quote}
  Find $n$ eigenvalues, and $n$ linearly independent eigenvectors of
  $A$.
\end{quote}

\section{Computing Eigenvalues and Eigenvectors}

As an example, let's consider the matrix
\[
  A =
  \begin{pmatrix}
  0 & -i & i \\ i & 0 & -i \\ -i & i & 0
  \end{pmatrix} \,.
\]
\subsubsection*{Step 1: Compute and factor the characteristic polynomial}

The characteristic polynomial is defined
\[
  p_A(\lambda) = \det (A - \lambda I) \,.
\]
It is zero if and only if $A-\lambda I$ is singular, i.e.\ if and only
if the equation $A\v=\lambda\v$ has a nontrivial solution, i.e.\ if
and only if $\lambda$ is an eigenvalue.  In order to find the zeros,
try to write the characteristic polynomial as a product of linear
factors:
\[
  p_A(\lambda) = \pm  (\lambda - \lambda_1) \cdots  (\lambda -
  \lambda_n) \,.
\]
Notice that some linear factor $\lambda - \lambda_k$ may occur more
than once.  In that case it is crucial that the dimension of the
corresponding eigenspace, i.e.\ the dimension of the solution space of
the linear system $(A-\lambda_k I)\v_k=0$ has the same multiplicity.
If its dimension is less than the multiplicity of the eigenvalue, the
matrix cannot be diagonalized.

In our example,
\begin{align*}
  p_A(\lambda)
  & = 
  \begin{vmatrix}
    -\lambda & -i & i \\ i & -\lambda & -i \\ -i & i & -\lambda
  \end{vmatrix} \\
  & = - \lambda^3 + (-i)^3 + i^3 -3 \, (-\lambda) \, i \, (-i) \\
  & = - \lambda \, (\lambda^2 - 3) \\
  & = - \lambda \, (\lambda + \sqrt 3) \, (\lambda - \sqrt3) \,.
\end{align*}
Therefore the three eigenvalues are $\lambda_1=0$,
$\lambda_2=-\sqrt3$, $\lambda_2=\sqrt3$.  Since the eigenvalues are
distinct, we already know that the matrix must be diagonalizable.

\subsubsection*{Step 2: Compute the eigenvectors for each eigenvalue}

For each of the $\lambda_k$ where $k=1,\dots,n$ we have to solve the
homogeneous equation
\[
  (A - \lambda_k) \v_k = 0 \,.
\]
In this example,
\[
  (A - \lambda_1) \v_1 =
  \begin{pmatrix}
  0 & -i & i \\ i & 0 & -i \\ -i & i & 0
  \end{pmatrix}
  =0 \,.
\]
After row-reduction, we obtain the matrix
\[
\begin{pmatrix}
  1 & 0 & -1 \\
  0 & 1 & -1 \\
  0 & 0 & 0
\end{pmatrix} \,,
\]
thus the first eigenvector is $\v_1=(-1,-1,-1)^T$.  Next,
\[
  (A - \lambda_2) \v_2 =
  \begin{pmatrix}
  \sqrt3 & -i & i \\ i & \sqrt3 & -i \\ -i & i & \sqrt3
  \end{pmatrix}
  =0 \,.
\]
Let's row-reduce this matrix:
\begin{align*}
  &
  \begin{pmatrix}
  \sqrt3 & -i & i \\ i & \sqrt3 & -i \\ -i & i & \sqrt3
  \end{pmatrix}
  \xrightarrow{\substack{\text{R1}/\sqrt3 \to\text{R1} \\
  i\text{R2} \to\text{R2}\\ i \text{R3} \to\text{R3}}}
  \begin{pmatrix}
  1 & -\tfrac{i}{\sqrt3}&\tfrac{i}{\sqrt3} \\
  -1 & \sqrt3 i & 1 \\
  1 & -1 & \sqrt3 i
  \end{pmatrix}
  \xrightarrow{\substack{\text{R1}+\text{R2} \to\text{R2} \\
  \text{R2}+ \text{R3} \to\text{R3}}} \\
  & \begin{pmatrix}
  1 & -\tfrac{i}{\sqrt3}&\tfrac{i}{\sqrt3} \\
  0 & \tfrac2{\sqrt3}i & 1 + \tfrac{i}{\sqrt3}\\
  0 & \sqrt3 i - 1 & 1 + \sqrt3 i
  \end{pmatrix}
  \xrightarrow{\substack{-\tfrac{\sqrt3}2 i \text{R2} \to\text{R2} \\ 
  \text{R3}/(\sqrt3 i - 1) \to\text{R3}}}
  \begin{pmatrix}
  1 & -\tfrac{i}{\sqrt3}&\tfrac{i}{\sqrt3} \\
  0 & 1 & \tfrac12 - \tfrac{\sqrt3}2i \\
  0 & 1 & \tfrac12 - \tfrac{\sqrt3}2i
  \end{pmatrix}\\
  &\xrightarrow{\substack{\text{R1}-\tfrac{i}{\sqrt3} \text{R2}
  \to\text{R1} \\  
  \text{R2}- \text{R3} \to\text{R3}}} 
  \begin{pmatrix}
  1 & 0 & \tfrac12 + \tfrac{\sqrt3}2i \\
  0 & 1 & \tfrac12 - \tfrac{\sqrt3}2i \\
  0 & 0 & 0 
  \end{pmatrix}
\end{align*}
Therefore, 
\[
  \v_2=
  \begin{pmatrix}
  \tfrac12 + \tfrac{\sqrt3}2i \\ \tfrac12 - \tfrac{\sqrt3}2i\\ -1
  \end{pmatrix} \,,
  \qquad
  \v_3 =
  \begin{pmatrix}
  \tfrac12 - \tfrac{\sqrt3}2i \\ \tfrac12 + \tfrac{\sqrt3}2i\\ -1
  \end{pmatrix} \,,
\]
where the computation for $\v_3$ is very similar to the previous one.
Hence, we can write
\[
  D =
  \begin{pmatrix}
  0 & 0 & 0 \\ 0 & -\sqrt3 & 0 \\ 0 & 0 & \sqrt3
  \end{pmatrix}\,, \qquad
  S =
  \begin{pmatrix}
  -1 & \tfrac12 + \tfrac{\sqrt3}2i & \tfrac12 - \tfrac{\sqrt3}2i \\
  -1 & \tfrac12 - \tfrac{\sqrt3}2i & \tfrac12 + \tfrac{\sqrt3}2i \\
  -1 & -1 & -1
  \end{pmatrix} \,.
\]

\subsubsection*{Step 3: Check your solution}

It is easiest to check that $SD = AS$, because this does not require the
computation of a matrix inverse.  In this example,
\begin{align*}
  SD & = 
  \begin{pmatrix}
  -1 & \tfrac12 + \tfrac{\sqrt3}2i & \tfrac12 - \tfrac{\sqrt3}2i \\
  -1 & \tfrac12 - \tfrac{\sqrt3}2i & \tfrac12 + \tfrac{\sqrt3}2i \\
  -1 & -1 & -1
  \end{pmatrix}
  \begin{pmatrix}
  0 & 0 & 0 \\ 0 & -\sqrt3 & 0 \\ 0 & 0 & \sqrt3
  \end{pmatrix}
  = 
  \begin{pmatrix}
  0 & -\tfrac{\sqrt3}2 - \tfrac{3}2i &\tfrac{\sqrt3}2 - \tfrac{3}2i \\
  0 & -\tfrac{\sqrt3}2 + \tfrac{3}2i &\tfrac{\sqrt3}2 + \tfrac{3}2i \\
  0 & \sqrt3 & -\sqrt3
  \end{pmatrix} \\
  AS & =
  \begin{pmatrix}
  0 & -i & i \\ i & 0 & -i \\ -i & i & 0
  \end{pmatrix}
  \begin{pmatrix}
  -1 & \tfrac12 + \tfrac{\sqrt3}2i & \tfrac12 - \tfrac{\sqrt3}2i \\
  -1 & \tfrac12 - \tfrac{\sqrt3}2i & \tfrac12 + \tfrac{\sqrt3}2i \\
  -1 & -1 & -1
  \end{pmatrix}
  =
  \begin{pmatrix}
  0 & -\tfrac{\sqrt3}2 - \tfrac{3}2i &\tfrac{\sqrt3}2 - \tfrac{3}2i \\
  0 & -\tfrac{\sqrt3}2 + \tfrac{3}2i &\tfrac{\sqrt3}2 + \tfrac{3}2i \\
  0 & \sqrt3 & -\sqrt3
  \end{pmatrix} \,.
\end{align*}
\end{document}
