
\section{Diagonalization }

Let $V$ and $W$ be vector spaces, with bases $S=\{e_1, \ldots, e_n\}$ and $T=\{f_1, \ldots, f_m\}$ respectively.  Since these are bases, there exist constants $v^i$ and $w^j$ such that any vectors $v\in V$ and $w\in W$ can be written as:
\begin{eqnarray*}
v & = & v^1e_1 \ + v^2e_2 \ + \ldots + v^ne_n \\
w & = & w^1f_1 + w^2f_2 + \ldots + w^mf_m \\
\end{eqnarray*}
We call the coefficients $v^1, \ldots, v^n$ the \emph{components}\index{Components of a vector} of $v$ in the basis\footnote{To avoid confusion, it helps to notice that components of a vector are almost always labeled by a superscript, while basis vectors are labeled by subscripts in the conventions of these lecture notes.} $\{e_1, \ldots, e_n\}$. It is often convenient to arrange the components $v^i$ in a column vector and the basis vector in a row vector by writing
\[
v=\rowvec{e_1 & e_2 & \cdots & e_n}\colvec{v^1 \\ v^2 \\ \vdots \\  v^n}\, .
\]

\begin{example}
Consider the basis $S=\{1-t, 1+t \}$ for the vector space $P_1(t)$.  The vector $v=2t$ has components $v^1=-1, v^2=1$, because 
\[v=-1(1-t) + 1(1+t)=\rowvec{(1-t) & (1+t)}\colvec{-1 \\[2mm] 1}\, .\]
\end{example}

We may consider these components as vectors in $\Re^n$ and $\Re^m$:
\[
\colvec{v^1\\ \vdots \\ v^n}\in \Re^n, \qquad 
\colvec{w^1\\ \vdots \\ w^m}\in \Re^m.
\]

Now suppose we have a linear transformation $L:V\rightarrow W$.
Then we can expect to write $L$ as an $m\times n$ matrix, turning an $n$-dimensional vector of coefficients corresponding to $v$ into an $m$-dimensional vector of coefficients for $w$.

Using linearity, we write:
\begin{eqnarray*}
L(v) & = & L( v^1e_1 + v^2e_2 + \ldots + v^ne_n) \\[2mm]
     & = & v^1L(e_1) + v^2L(e_2) + \ldots + v^nL(e_n)\\[2mm]
     &=&\rowvec{L(e_1) & L(e_2) & \cdots & L(e_n)}\colvec{v^1 \\ v^2 \\ \vdots \\ v^n}\, .
\end{eqnarray*}
This is a vector in $W$.  Let's compute its components in $W$.

We know that for each $e_j$, $L(e_j)$ is a vector in $W$, and can thus be written uniquely as a linear combination of vectors in the basis $T$.  Then we can find coefficients $M^i_j$ such that:
\[
L(e_j)=f_1M^1_j + \ldots + f_mM^m_j = \sum_{i=1}^m f_iM^i_j
=\rowvec{f_1 & f_2 & \cdots & f_m}\colvec{M^1_j \\[1mm] M^2_j \\[1mm] \vdots \\[1mm] M^m_j}\, .
\]
We've written the $M^i_j$ on the right side of the $f$'s to agree with our previous notation for matrix multiplication.  We have an ``up-hill rule'' where the matching indices for the multiplied objects run up and to the left, like so:~$f_iM^i_j$.

Now $M^i_j$ is the $i$th component of $L(e_j)$.  Regarding the coefficients $M^i_j$ as a matrix, we can see that the $j$th column of $M$ is the coefficients of $L(e_j)$ in the basis $T$.

Then we can write:
\begin{eqnarray*}
L(v) & = & L( v^1e_1 + v^2e_2 + \ldots + v^ne_n) \\
     & = & v^1L(e_1) + v^2L(e_2) + \ldots + v^nL(e_n) \\
     & = & \sum_{i=1}^m v^j L(e_j) \\
     & = & \sum_{i=1}^m v^j ( M^1_jf_1 + \ldots + M^m_jf_m)\\
     & = & \sum_{i=1}^m f_i [ \sum_{j=1}^n M^i_jv^j ]\\
     &=&\rowvec{f_1 & f_2 & \cdots & f_m}
             \begin{pmatrix}M^1_1&M^1_2&\cdots &M^1_n\\ M^2_1 & M^2_2 && \\
                                              \vdots &&&\vdots\\ M^m_1 &&\cdots & M^m_n\end{pmatrix}\colvec{v^1 \\ v^2 \\ \vdots \\ v^n}
\end{eqnarray*}
The second last equality is the definition of matrix multiplication which is obvious from the last line.  Thus:
\[
\colvec{v^1\\ \vdots \\ v^n} \stackrel{L}{\mapsto}
\begin{pmatrix}
M^1_1 & \ldots & M^1_n \\
\vdots & & \vdots \\
M^m_1 & \ldots & M^m_n \\
\end{pmatrix}
\colvec{v^1\\ \vdots \\ v^n},
\]
and $M=(M^i_j)$ is called the matrix of $L$.  Notice that this matrix depends on a \emph{choice} of bases for both $V$ and $W$.
Also observe that the columns of $M$ are computed by examining $L$ acting on each basis vector in $V$ expanded in the 
basis vectors of $W$.

\begin{example}
Let $L:P_1(t) \mapsto P_1(t)$, such that $L(a+bt)=(a+b)t$.  Since $V=P_1(t)=W$, let's choose the same basis for $V$ and $W$.  We'll choose the basis $\{1-t, 1+t \}$ for this example.

Thus:
\begin{eqnarray*}
L(1-t)&=&(1-1)t=\ 0\ =(1-t)\cdot 0 + (1+t)\cdot 0=
\rowvec{(1-t)& (1+t)}\colvec{0\\0}\\
L(1+t)&=&(1+1)t=2t\ =(1-t)\cdot -1 + (1+t)\cdot 1=
\rowvec{(1-t)& (1+t)}\colvec{-1\\1}\\
\Rightarrow M &=& \begin{pmatrix}
0 & -1 \\
0 & 1 \\
\end{pmatrix}
\end{eqnarray*}
To obtain the last line we used that fact that the columns of $M$ are just the coefficients of $L$ on each of the basis vectors; this always makes it easy to write down $M$ in terms of the basis we have chosen.
\end{example}

Now suppose we are lucky, and we have $L:V\mapsto V$, and the basis $\{v_1, \ldots, v_n \}$ is a set of linearly independent eigenvectors for $L$, with eigenvalues $\lambda_1, \ldots, \lambda_n$.  Then:

\begin{eqnarray*}
L(v_1)&=&\lambda_1 v_1 \\
L(v_2)&=&\lambda_2 v_2 \\
&\vdots & \\
L(v_n)&=&\lambda_n v_n \\
\end{eqnarray*}

As a result, the matrix of $L$ in the basis of eigenvectors is:
\[
M = \begin{pmatrix}
\lambda_1    \\
& \lambda_2 &  & \\
&  & \ddots &  \\
& & & \lambda_n
\end{pmatrix},
\]
where all entries off of the diagonal are zero.

We call the $n\times n$ matrix of a linear transformation $L: V\mapsto V$ \emph{diagonalizable}\index{Diagonalizable} if there exists a collection of $n$ linearly independent eigenvectors for $L$.  In other words, $L$ is diagonalizable if there exists a basis for $V$ of eigenvectors for $L$.  

In a basis of eigenvectors, the matrix of a linear transformation is diagonal.  On the other hand, if an $n \times n$ matrix $M$ is diagonal, then the standard basis vectors $e_i$ are already a set of $n$ linearly independent eigenvectors for~$M$.  We have shown:

\begin{theorem}
Given a basis $S$ for a vector space $V$ and a linear transformation $L:V\rightarrow V$, then the matrix for $L$ in the basis $S$ is diagonal if and only if $S$ is a basis of eigenvectors for $L$.
\end{theorem}

\subsection{Change of Basis}\index{Change of basis}

Suppose we have two bases $S=\{v_1, \ldots, v_n \}$ and 
$T=\{u_1, \ldots, u_n \}$ for a vector space $V$. (Here $v_i$ and $u_i$ are {\it vectors}, not components of vectors in a basis!) 
Then we may write each $v_i$ uniquely as a linear combination of the~$u_j$:

\[
v_j = \sum_i u_iP^i_j\, ,
\]
or in a matrix notation
\[ 
\rowvec{v_1 & v_2 & \cdots & v_n} = \rowvec{u_1 & u_2 & \cdots & u_n}
\begin{pmatrix}P^1_1&P^1_2&\cdots &P^1_n\\ P^2_1 & P^2_2 && \\
                                              \vdots &&&\vdots\\ P^n_1 &&\cdots & P^n_n\end{pmatrix}\, .
\]
Here, the $P^i_j$ are constants, which we can regard as entries of  a square matrix~$P=(P^i_j)$.  The matrix~$P$ must have an inverse, since we can also write each~$u_i$ uniquely as a linear combination of the~$v_j$:
\[
u_j = \sum_k v_kQ^k_j.
\]

Then we can write:
\[
v_j = \sum_k \sum_i v_kQ^k_jP^i_j.
\]
But $\sum_i Q^k_jP^i_j$ is the $k,j$ entry of the product of the matrices $QP$.  Since the only expression for $v_j$ in the basis $S$ is $v_j$ itself, then $QP$ fixes each $v_j$.  As a result, each $v_j$ is an eigenvector for $QP$ with eigenvalues $1$, so $QP$ is the identity.

\vspace{1mm}
The matrix $P$ is  called a \emph{change of basis} matrix\index{Change of basis matrix}.
\vspace{1mm}

Changing basis changes the matrix of a linear transformation.  To wit, suppose $L:V \mapsto V$ has matrix $M=(M^i_j)$ in the basis $T=\{u_1, \ldots, u_n \}$, so
\[
L(u_i) = \sum_k M^k_iu_k.
\]
Now, let $S=\{v_1, \ldots, v_n \}$ be a basis of eigenvectors for $L$, with eigenvalues $\lambda_1,\ldots, \lambda_n$.  Then
\[
L(v_i)=\lambda_iv_i = \sum_kv_kD^k_i
\]
where $D$ is the diagonal matrix whose diagonal entries $D^k_k$ are the eigenvalues~$\lambda_k$; ie, $D = \begin{pmatrix}
\lambda_1    \\
& \lambda_2 &  & \\
&  & \ddots &  \\
& & & \lambda_n
\end{pmatrix}$.  Let $P$ be the change of basis matrix from the basis $T$ to the basis $S$.  Then:
\[
L(v_j)=L(\sum_i u_i P^i_j) = \sum_i L(u_i)P^i_j
= \sum_i \sum_k u_k M^k_i P^i_j.
\]
Meanwhile, we have:
\[
L(v_i) = \sum_kv_kD^k_i = \sum_k \sum_j u_j P^j_kD^k_i.
\]
Since the expression for a vector in a basis is unique, then we see that the entries of $MP$ are the same as the entries of $PD$.  In other words, we see that
\[
MP = PD \qquad \text{or}\qquad D=P^{-1}MP.
\]

This motivates the following definition:
\begin{definition}
A matrix $M$ is \emph{diagonalizable} if there exists an invertible matrix $P$ and a diagonal matrix $D$ such that 
\[
D=P^{-1}MP.
\]
\end{definition}

We can summarize as follows:
\begin{itemize}
\item Change of basis multiplies vectors by the change of basis matrix $P$, to give vectors in the new basis.
\item To get the matrix of a linear transformation in the new basis, we \emph{conjugate}\index{Conjugation} the matrix of $L$ by the change of basis matrix: $M\rightarrow P^{-1}MP$.
\end{itemize}

If for two matrices $N$ and $M$ there exists an invertible matrix $P$ such that $M=P^{-1}NP$, then we say that $M$ and $N$ are \emph{similar}\index{Similar matrices}.  Then the above discussion shows that diagonalizable matrices are similar to diagonal matrices.

\begin{corollary}
A square matrix $M$ is diagonalizable if and only if there exists a basis of eigenvectors for $M$.
\end{corollary}






\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/Change_of_basis}{Change of Basis}
\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 Show that similarity of matrices is an \emph{equivalence relation}\index{Equivalence relation}.  (The definition of an equivalence relation is given in \href{http://math.ucdavis.edu/~linear/notes2.pdf}{Section 2}, in the fourth review problem.)



\item When is the $2\times 2$ matrix 
$\begin{pmatrix}
a & b \\
c & d \\
\end{pmatrix}$ diagonalizable?  Include examples in your answer.




\item Let $P_n(t)$ be the vector space of degree $n$ polynomials, and $\frac{d}{dt}:P_n(t) \mapsto P_{n-1}(t)$ be the derivative operator.  Find the matrix of $\frac{d}{dt}$ in the bases $\{1,t,\ldots,t^n \}$ for $P_n(t)$ and $\{1,t,\ldots,t^{n-1} \}$ for $P_{n-1}(t)$.

\item When writing a matrix for a linear transformation, we have seen that the choice of basis matters.  In fact, even the order of the basis matters!
\begin{itemize}
\item Write all possible reorderings of the standard basis $\{e_1,e_2,e_3\}$ for~$\Re^3$.
\item Write each change of basis matrix between the standard basis $\{e_1,e_2,e_3\}$ and each of its reorderings.  Make as many observations as you can about these matrices.  (Note: These matrices are known as \emph{permutation matrices}\index{Permutation matrices}.)
\item Given the linear transformation $L(x,y,z)=(2y-z,3x,2z+x+y)$, write the matrix $M$ for $L$ in the standard basis, and two other reorderings of the standard basis.  Can you make any observations about the resulting matrices?
\end{itemize}
\end{enumerate}

\newpage
