\documentclass{article}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{enumerate}

\usepackage{hyperref}

\usepackage{tikz}

\usepackage{ifthen}
\usepackage{ulem} % for strikethrough \sout{...} command
\usepackage{color}

\usepackage{wasysym}

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{-0.25in}
\setlength{\evensidemargin}{-0.25in}
\setlength{\topmargin}{-0.5in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{9.7in}
\setlength{\textwidth}{7in}

\newcommand{\bdot}{\, {\scriptstyle{\bullet}} \,}
\newcommand{\B}[1]{{\bf {#1}}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}

\newcommand{\myspace}{\parbox[c][0.25in]{0.25in}{\hfill}}
\newcommand{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}}
\newcommand{\force}{{\noindent $\mbox{\;}$}}

\newcommand{\diagquotient}[2]{\displaystyle{{#1 \atop \;}\hspace*{-0.1in} \mbox{\put(0,0){\line(2,1){2}}} \hspace*{0.1in} {\; \atop #2}}}


\newcommand{\F}{\mathbb{F}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}

\newcommand{\LEMMA}{\vspace{0.05in} \noindent \fbox{\large\bf Lemma:}  }
\newcommand{\COR}{\vspace{0.05in} \noindent \fbox{\large\bf Corollary:}  }
\newcommand{\PROP}{\vspace{0.05in} \noindent \fbox{\large\bf Proposition:}  }
\newcommand{\DEF}{\vspace{0.05in} \noindent \fbox{\large\bf Definition:}  }
\newcommand{\THM}{\vspace{0.05in} \noindent \fbox{\large\bf Theorem:}  }
\newcommand{\EX}{\vspace{0.05in} \noindent \fbox{\large\bf Example:}  }
\newcommand{\bproof}{\vspace{0.05in} \noindent {\bf Proof:} }
\newcommand{\eproof}{$\blacksquare$ \vspace{0.05in}}

\newcommand{\vsp}{\vspace{0.035in}}

\newcommand{\std}{{\mathrm{std}}}

\newcommand{\KER}{\mathrm{Ker}}

\begin{document}

% Inspired by a weird conversion with Quinn and Jeff. Draft typed up circa October 2023.

%\pagestyle{empty}

\noindent
{\bf Math 5230}
\hfill {\Large \bf The Cayley-Hamilton Theorem} \hfill 
{\bf Linear Algebra}

\vspace{0.15in}

Here we will introduce the concepts of $T$-invariant subspaces, $T$-cyclic subspaces, companion matrices, and then prove the Cayley-Hamilton Theorem. The matrix version of the Cayley-Hamilton Theorem says plugging a square matrix into its characteristic polynomial will result in the zero matrix. This looks like it should work: Let $f(t)=\det(tI-A)$ for some square matrix $A$. Then $f(A)$ should be $\det(AI-A)=\det(A-A)=\det(0)=0$. So what's the problem? Well, the issue at hand is whether it is ok equate: ``plug in $t=A$ and take the determinant'' and ``take the determinant and then plug in $t=A$''. It is not obvious that these should result in the same answer. It is possible to repair the above attempt at a proof,\footnote{See Neal McCoy's {\it Rings and Ideals} where he carefully develops the theory of polynomials with non-commutative coefficients.} but we will follow a different path.

\vspace{0.05in}

In all that follows, we let $V$ be a finite dimensional vector space (over some field $\mathbb{F}$) and $T:V \to V$ a linear operator on $V$. Also, recall that $T^k(\B v) = \underbrace{T(T(\cdots T(\B v)\cdots))}_{k\mathrm{-times}}$ for $k \in \mathbb{Z}_{>0}$ and $T^0(\B v)=I(\B v)=\B v$ is just the identity. Also, given a polynomial $f(t)=a_mt^m+\cdots+a_0$, we have $f(T)(\B v)=a_mT^m(\B v)+\cdots+a_1T(\B v)+a_0\B v$. Also, recall that $\det(tI-T)$ is the characteristic polynomial of $T$ and that this can be calculated using a coordinate matrix $[T]_\beta^\beta$ for any basis $\beta$ of $V$.

\DEF Let $W$ be a subspace of $V$. We say $W$ is {\bf $T$-invariant} if $T(W) \subseteq W$ (i.e., for every $\B w \in W$, we have $T(\B w) \in W$). In words, $T$ maps $W$ back into itself. In such a case, we can consider $T\Big|_W:W \to W$ (i.e., $T$ restricted to the domain $W$) as a linear operator on $W$. 

\vspace{0.05in}

Let $W$ be some $T$-invariant subspace with basis $\alpha$. We can extend this basis to a basis for $V$, say $\beta=\alpha \,\dot\cup\, \alpha'$ where $\alpha=\{\B v_1,\dots,\B v_k\}$ and $\alpha' = \{\B v_{k+1},\dots,\B v_n\}$. Notice for any $1 \leq j \leq k$, we have $T(\B v_j) \in W$ since $\B v_j \in \alpha \subseteq W$. Thus $T(\B v_j)=c_1\B v_1+\cdots+c_k\B v_k$ for some $c_1,\dots,c_k \in \mathbb{F}$. These are precisely the coodinates of $\left[T\Big|_W(\B v_j)\right]_\alpha$. In other words, the $\beta$-coordinates of $T(\B v_j)$ are the $\alpha$-coordinates of $T\Big|_W(\B v_j)$ padded out with $(n-k)$ zeros. We have:
$$[T]_\beta^\beta = \begin{bmatrix} \left[T\Big|_W\right]_\alpha^\alpha & \mathrm{stuff} \\[5pt] \ \  0_{(n-k)\times k} & \mathrm{stuff}\large\strut \end{bmatrix}$$
Thus $T$'s coordinate matrix has an upper block matrix shape to it. Using similar reasoning, if $V=W_1\oplus \cdots \oplus W_\ell$ where each $W_i$ is $T$-invariant with basis $\alpha_i$, then $\beta=\alpha_1 \,\dot\cup\, \cdots \,\dot\cup\, \alpha_\ell$ is a basis for $V$ and $[T]_\beta^\beta$ is a block diagonal matrix whose diagonal blocks are $\left[T\Big|_{W_i}\right]_{\alpha_i}^{\alpha_i}$ for $i=1,\dots,\ell$. 

\vspace{0.05in}

Again, letting $\alpha$ be a basis for an $T$-invariant subspace $W$ and $\beta$ an extension of $\alpha$ to a basis for $V$,  if $B=[T]_\beta^\beta$ and $A=[T|_W]_\alpha^\alpha$, then $B=\begin{bmatrix} A & C \\ 0 & D \end{bmatrix}$ for some matrices $C,D$. Therefore, $\det(tI-B)=\det(tI-A)\det(tI-D)$. Consequently, we have:

\PROP Let $W$ be a $T$-invariant subspace.\\ \force\hfill Then the characteristic polynomial of $T\Big|_W$ divides the characteristic polynomial of $T$.


\DEF Let $\B v \in V$ and $W=\mathrm{span}\{\B v,T(\B v), T^2(\B v),\dots\}$ is the {\bf $T$-cyclic subspace} generated by $\B v$. 

\vspace{0.05in}

Let $\B 0 \not= \B v \in V$ and let $W=\mathrm{span}\{\B v, T(\B v), T^2(\B v),\dots\}$ be the $T$-cyclic subspace generated by $\B v$. Now $\dim(W)\leq \dim(V)<\infty$. Thus $\{\B v,T(\B v),\dots\}$ (an infinite set) must be linearly dependent. Let $k$ be the smallest positive integer such that $T^k(\B v) \in \mathrm{span}\{\B v, T(\B v),\dots, T^{k-1}(\B v)\}$ (call this space $W'$). Thus $T^k(\B v)=c_0\B v+c_1T(\B v)+\cdots+c_{k-1}T^{k-1}(\B v)$ for some $c_0,c_1,\dots,c_{k-1} \in \mathbb{F}$. Let $g(t)=t^k-c_{k-1}t^{k-1}+\cdots-c_1t-c_0$. Then $g(T)(\B v)=T^k(\B v)-c_{k-1}T^{k-1}(\B v)-\cdots-c_0\B v=\B 0$. Consider some $\ell>0$. Divide $t^\ell$ by $g(t)$ and get $t^\ell=q(t)g(t)+r(t)$ for some polynomials $q(t),r(t) \in \mathbb{F}[t]$ with $r(t)=0$ or $\deg(r(t))<\deg(g(t))=k$. Thus $r(t)=b_{k-1}t^{k-1}+\cdots+b_1t+b_0$ for some $b_0,\dots,b_{k-1} \in \mathbb{F}$. We have $T^\ell(\B v) = q(T)g(T)(\B v)+r(T)(\B v)=q(T)(\B 0)+r(T)(\B v)=b_{k-1}T^{k-1}(\B v)+\cdots+b_1T(\B v)+b_0\B v \in W'$. This implies $W=W'=\mathrm{span}\{\B v,\dots,T^{k-1}(\B v)\}$. Notice $\beta=\{\B v,\dots,T^{k-1}(\B v)\}$ must be linear independent since otherwise we would have some $T^\ell(\B v)$ as a linear combination of $\{\B v,\dots,T^{\ell-1}(\B v)\}$ for $\ell<k$ (contradicting $k$ being the smallest such positive integer). We say $g(t)$ is $W$'s associated polynoial and have:

\PROP Let $W=\mathrm{span}\{\B v,T(\B v),T^2(\B v),\dots\}$ be the $T$-cyclic subspace generated by $\B v$.\\ \force\hfill Then $\beta = \{\B v,T(\B v),\dots,T^{k-1}(\B v)\}$ is a basis for $W$ where $k=\dim(W)$. 

\newpage

Consider a $k$-dimensional $T$-cyclic subpace $W$ generated by $\B v \not= \B 0$. Again, $\beta=\{\B v,\dots, T^{k-1}(\B v)\}$ is a basis for $W$, and say $T^k(\B v)=c_0\B v+\cdots+c_{k-1}T^{k-1}(\B v)$. Then we have:

\noindent
$\displaystyle \left[T\Big|_W\right]_\beta^\beta = \Big[ [T(\B v)]_\beta \; [T(T(\B v))]_\beta \; \cdots \; [T(T^{k-1}(\B v)]_\beta \Big] = \Big[ [T(\B v)]_\beta \; [T^2(\B v)]_\beta \; \cdots \; [T^{k-1}(\B v)]_\beta \; [c_0\B v+\cdots+c_{k-1}T^{k-1}(\B v)]_\beta \Big]$ 

\noindent
$\displaystyle\phantom{\left[T\Big|_W\right]_\beta^\beta}=\begin{bmatrix} 0 & 0 & \cdots & 0 & c_0 \\ 1 & 0 & \cdots & 0 & c_1 \\ 0 & 1 & & 0 & c_2 \\ \vdots &  & \ddots & & \vdots \\ 0 & 0 & \cdots & 1 & c_{k-1} \end{bmatrix}$ \quad (for convenience, call this matrix $C$).

\DEF This is called the {\bf companion matrix} associated with the polynomial $t^k-c_{k-1}t^{k-1}-\cdots-c_1t-c_0$.

\PROP The characteristic polynomial of a companion matrix is its associated polynomial.

\bproof
Proceed by induction. The base case is silly: $C=[c_0]$ then $\det(tI-C)=\det([t-c_0])=t-c_0$. Assume this is true for $(k-1)\times(k-1)$ companion matrices and consider a $k\times k$ companion matrix $C$. To compute our characteristic polynomial, we expand the determinant along the first row:

\noindent $\displaystyle \det(tI-C) = \det\begin{bmatrix} t & &  & -c_0 \\ -1 & \ddots & & \vdots \\ & \ddots & t & -c_{k-2} \\ & & -1 & t-c_{k-1} \end{bmatrix} = t \cdot \det \begin{bmatrix} t & &  & -c_1 \\ -1 & \ddots & & \vdots \\ & \ddots & t & -c_{k-2} \\ & & -1 & t-c_{k-1} \end{bmatrix}+(-1)^{k+1}(-c_0)\det\begin{bmatrix} -1 & t &  &  \\ & \ddots & \ddots & \\ & & & t \\ & & & -1 \end{bmatrix}$

\vspace{0.025in}

\noindent $\displaystyle\phantom{\det(tI-C)} = t\cdot(t^{k-1}-c_{k-1}t^{k-2}-\cdots c_2t-c_1)+(-1)^{k+1}(-c_0)(-1)^{k-1} = t^k-c_{k-1}t^{k-1}-\cdots-c_2t^2-c_1t-c_0$

\vspace{0.025in}

\noindent where we used our inductive hypothesis on the first $(k\mathrm{-}1)\times(k\mathrm{-}1)$ determinant and the fact that other $(k\mathrm{-}1)\times(k\mathrm{-}1)$ determinant is just the product of its diagonals: $(-1)(-1)\cdots(-1)=(-1)^{k-1}$. Therefore, if the statement holds for $k\mathrm{-}1$, it also holds for $k$. Thus our proposition follows by induction. \eproof

\vspace{-0.05in}

\THM (Cayley-Hamilton Theorem) Let $T$ be a linear operator on a finite dimensional vector space $V$\\ \force\hfill with characteristic polynomial $f(t)=\det(tI-T)$. Then $f(T)=0$.

\bproof
Obviously, $f(T)(\B 0)=\B 0$. Let $\B 0\not=\B v \in V$ and $W=\mathrm{span}\{\B v,T(\B v),T^2(\B v),\dots\}$ be the $T$-cyclic subspace generated by $\B v$. We know that if $\dim(W)=k$, then $\beta=\{\B v,\dots,T^{k-1}(\B v)\}$ is a basis for $W$ and $T^k(\B v) =c_0\B v+c_1T(\B v)+\cdots+c_{k-1}T^{k-1}(\B v)$ for some $c_0,\dots,c_{k-1} \in \mathbb{F}$. Lettting $g(t)=t^k-c_{k-1}t^{k-1}-\cdots-c_1t-c_0$, we have that $C=\left[T|_W\right]_\beta^\beta$ is the companion matrix associated with $g(t)$. Also, we have shown that the charateristic polynomial of $C$ is just $g(t)$ itself. We also know when $W$ is $T$-invariant, the characteristic polynomial of $T\Big|_W$ (i.e., $g(t)$) must divide the characteristic polynomial of $T$ (i.e., $f(t)$). Thus there exists some polynomial $q(t) \in \mathbb{F}[t]$ such that $f(t)=q(t)g(t)$. We have $f(T)(\B v)=q(T)(g(T)(\B v))=q(T)(T^k(\B v)-c_{k-1}T^{k-1}(\B v)-\cdots-c_1T(\B v)-c_0\B v)=q(T)(\B 0)=\B 0$. 
We have shown that $f(T)(\B v)=\B 0$ for all $\B v \in V$. Thus $f(T)=0$ (i.e., the zero operator).
\eproof

%\vspace{0.05in}

Although we won't prove it here, it turns out that one can always find a set of vectors $\B v_1,\dots,\B v_\ell$ such that $V$ is a direct sum of the $T$-cyclic subspaces generated by these vectors. The existence of such generating vectors follows from the classification of finitely generated modules working over a principal ideal domain (in particular, $R=\mathbb{F}[t]$). The same classification applied to $R=\mathbb{Z}$ gives a classification of finitely generated Abelian groups. 

\vspace{0.025in}

Say we have such a set of vectors and let $W_{g_i(t)}$ be the $T$-cyclic subspace generated by $\B v_i$ with associated polynomial is $g_i(t)$. Then one has $V=W_{g_1(t)}\oplus \cdots \oplus W_{g_\ell(t)}$. Let $\beta_i = \{ \B v_i, T(\B v_i),\dots, T^{k_i-1}(\B v_i)\}$ be our usual basis for $W_{g_i(t)}$. Combine these: $\beta = \beta_1 \;\dot\cup\; \cdots \;\dot\cup\; \beta_\ell$ to get a basis for $V$. Then $[T]_\beta^\beta$ will be block diagonal and have companion matrices as its blocks on the diagonal. 

Moreover, it is possible to find cyclic subspaces such that our associated polynomials successively divide one another: $g_1(t)$ divides $g_2(t)$, $g_2(t)$ divides $g_3(t)$, etc. These polynomials are {\it uniquely determined} by $T$ and are called the {\bf invariant factors} of $T$. Thus we can find a basis such that the coordinate matrix of $T$ is block diagonal with companion matrices (associated with $T$'s invariant factors) blocks. This is $T$'s {\bf rational canonical form}. It is a kind of standardized coordinate matrix for $T$. One can also find vectors such that each associated polynomial $g_i(t)$, now called {\bf elementary divisors}, is a power of an irreducible polynomial. In this case, the corresponding coordinate matrix is called a {\bf primary rational canonical form} for $T$. 

These canonical forms are kind of unwieldy, but theoretically useful since they {\it always exist}. On the other hand, when $T$'s characteristic polynomial splits (i.e., factors into linear factors) over our field of scalars, we can do better. Here the $T$-invariant subspaces associated with elementary divisors turn out to be spaces of {\bf generalized eigenvectors}. By choosing a slightly different basis than the cyclic ones we've been using thus far, one can find a coordinate matrix for $T$ in {\bf Jordan form}. Jordan form is very useful and we will discuss it later.
\end{document}
