\documentstyle[12pt]{article}
\input amssym.def
\input amssym

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{DEF}[theorem]{Definition}

\newtheorem{define}[theorem]{Definition}
%\newenvironment{define}{\begin{DEF}\bf}{\end{DEF}}

\newtheorem{exercise}[theorem]{Exercise}

\def\proof{\par\noindent proof:\par }
\def\qed{\par\noindent QED\par}
\def\col{{\rm col}}
\def\span{{\rm span}}
\def\complex{{\Bbb C}}

\begin{document}

\begin{flushright}
  A. Miller\\
  M340 \\
  May 97
\end{flushright}

\begin{center}
  Similarity, diagonalization, and eigenvalues
\end{center}



Remark.  From now on all matrices are square, i.e., $n\times n$
for some $n$ and our field of scalars is the complex numbers,
$\complex$.

\begin{define}
  $A$ is \underline{similar} to $B$ (written $A\sim B$) iff there
  exists an invertible matrix $P$ such that $A=PBP^{-1}$.
\end{define}

\begin{theorem}
  \begin{enumerate}
    \item $A\sim A$
    \item $A\sim B$ implies $B\sim A$, and
    \item $A\sim B$ and $B\sim C$ implies $A\sim C$.
  \end{enumerate}
\end{theorem}
\proof
For (1) $A=IAI^{-1}$.

For (2) if $A=PBP^{-1}$, then $B=QAQ^{-1}$ where $Q=P^{-1}$.

For (3) suppose $A=PBP^{-1}$ and $B=QCQ^{-1}$. Then
$$A=(PQ)C(PQ)^{-1}.$$
\qed


\begin{define}
 $A$ is diagonalizable iff $A$ is similar to a diagonal matrix.
\end{define}

\begin{define}
  $\lambda\in\complex$ is an \underline{eigenvalue} of $A$ iff
  for some $X\not=Z$ we have $AX=\lambda X$.  Such an $X$ is called
  an \underline{eigenvector} of $A$.
\end{define}

\begin{theorem}
  An $n\times n$ matrix $A$ is diagonalizable iff $\complex^n$ has
  a basis consisting of eigenvectors of $A$.
\end{theorem}
\proof
Suppose first that $\complex^n$ has a basis $X_1,\ldots,X_n$ consisting
of eigenvectors of $A$, so $AX_i=\lambda_iX_i$.  Let
$P$ be the $n\times n$ matrix with $\col_j(P)=X_j$ for each
$j=1,\ldots,n$ and let $D$ be the diagonal matrix with
$\lambda_1,\lambda_2,\ldots,\lambda_n$ on its diagonal, i.e.,
$$D=
\left[
\begin{array}{ccccc}
                \lambda_1 &  0         &  0    & \cdots & 0   \\
                0         &  \lambda_2 &  0    & \cdots & 0   \\
                \vdots    &  0         & \ddots&  0      &  \vdots \\
                \vdots    &  \vdots    &  0    & \lambda_{n-1} & 0 \\
                0         &  0         &  0    & 0 & \lambda_n \\
\end{array}
\right].
$$

Since the $X_j$'s are a basis $P$ is invertible.

\medskip
\noindent {\bf Claim} $AP=PD$.
\proof
For any $j$
$$\begin{array}{rcl}
\col_j(AP)&=&A\col_j(P)\\
          &=&\lambda_j\col_j(P)\\
\end{array}$$
since $\col_j(P)=X_j$ an eigenvector associated to $\lambda_j$.
Also
$$
\begin{array}{rcl}
\col_j(PD)&=&P\col_j(D)\\
          &=&P\col_j(\lambda_jI)\\
          &=&\lambda_jP\col_j(I)\\
          &=&\lambda_j\col_j(PI)\\
          &=&\lambda_j\col_j(P)\\
\end{array}
$$
Hence $AP$ and $PD$ have the same columns, and so they are equal.
This proves the Claim and so $A=PDP^{-1}$.

\bigskip

Now we prove the converse. Suppose that $A=PDP^{-1}$.
Where $D$ is a diagonal matrix with $\lambda_1,\ldots,\lambda_n$
on its diagonal.
We have that
$$AP=PD$$
and by the same argument as the Claim, we have
for each $j=1,\ldots,n$ that
$$A\col_j(P)=\lambda_j\col_j(P)$$
Then since $P$ is invertible the columns $P$ are a basis
of $\complex^n$ and the formula
implies that each $\col_j(P)$ is an eigenvector of $A$.
\qed

\begin{theorem}
  If $\lambda_1,\lambda_2,\ldots,\lambda_m$ are distinct eigenvalues
  of $A$ and $AX_i=\lambda_iX_i$ for $i=1,\ldots,m$ are (nontrivial)
  eigenvectors of $A$, then $X_1,X_2,\ldots,X_m$ are linearly independent.
\end{theorem}
\proof
Nontrivial means that $X_i\not=Z$ all $i$.

Suppose they are linearly dependent.  Then (by an exercise)
either $X_1=Z$ or there exists $k$ such that
$X_k\in\span(\{X_1,\ldots,X_{k-1}\})$.  If we choose $k$ minimal such
that $X_k\in\span(\{X_1,\ldots,X_{k-1}\})$, then it follows that
$X_1,\ldots,X_{k-1}$ are linearly independent.

Now let $a_1,\ldots,a_{k-1}$
be such that
$$X_k=a_1X_1+\cdots+a_{k-1}X_{k-1}.$$
Multiplying by $A$ gives us
$$AX_k=a_1AX_1+\cdots+a_{k-1}AX_{k-1}$$
and using $AX_i=\lambda_iX_i$ gives us
$$\lambda_kX_k=a_1\lambda_1X_1+\cdots+a_{k-1}\lambda_{k-1}X_{k-1}.$$

Case 1. $\lambda_k=0$.

In this case we have
$$Z=a_1\lambda_1X_1+\cdots+a_{k-1}\lambda_{k-1}X_{k-1}.$$
and since $X_1,\ldots,X_{k-1}$ are linearly independent we have
that $\lambda_ia_i=0$ for all $i=1,\ldots,k-1$.  But the $\lambda$'s are
all distinct, so $\lambda_i\not=\lambda_k=0$ for all $i=1,\ldots,k-1$.
Hence $a_i=0$ and so $X_k=a_1X_1+\cdots+a_{k-1}X_{k-1}=Z$, which contradicts
the fact that $X_k$ is nontrivial.

\bigskip

Case 2. $\lambda_k\not=0$.

In this case we can divide by $\lambda_k$ and get
$$X_k=a_1{\lambda_1\over\lambda_k}X_1+\cdots+a_{k-1}
{\lambda_{k-1}\over\lambda_k}X_{k-1}.$$
subtracting this from
$$X_k=a_1X_1+\cdots+a_{k-1}X_{k-1}$$
gives
$$Z=(a_1-a_1{\lambda_1\over\lambda_k})X_1+\cdots+(a_{k-1}-a_{k-1}
{\lambda_{k-1}\over\lambda_k})X_{k-1}.$$
Since
$X_1,\ldots,X_{k-1}$ are linearly independent we have
that $a_i-a_i{\lambda_1\over\lambda_k}=0$ for all $i=1,\ldots,k-1$.
Since $X_k$ is nontrivial at least one $i\leq k-1$ exists such
that $a_i\not=0$, but then
$$a_i-a_i{\lambda_i\over\lambda_k}=0$$
implies
that $\lambda_i=\lambda_k$ contradicting the fact that
the $\lambda$'s are distinct.

In either case we get a contradiction and so our ``suppose not'' is
impossible and therefore $X_1,\ldots,X_m$ are linearly independent.
\qed

\begin{corollary}
  If an $n\times n$ matrix $A$ has $n$ distinct eigenvalues, then
  it is diagonalizable.
\end{corollary}
\proof
Since any set of $n$ independent vectors in $\complex^n$ must be
a basis, it must be that $\complex^n$ has a basis consisting
of eigenvectors of $A$ and so $A$ is diagonalizable.
\qed


\end{document}