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

\usepackage{hyperref}

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

\usepackage{wasysym}

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{-0.5in}
\setlength{\evensidemargin}{-0.5in}
\setlength{\topmargin}{-0.5in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{9.6in}
\setlength{\textwidth}{7.5in}

\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.1in} \noindent {\bf Proof:} }
\newcommand{\eproof}{$\blacksquare$ \vspace{0.05in}}

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

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

\newcommand{\rank}{\mathrm{rank}}

\newcommand{\spn}{\mathrm{span}\,}

\begin{document}

%\pagestyle{empty}

\noindent
{\bf Math 4010}
\hfill {\Large \bf Jordan Form} \hfill 
{\bf Linear Algebra}

\vspace{0.1in}

Since we compute with coordinates and coordinate matrices, when dealing with a linear transformation, it is natural to ask, ``What is the nicest/simplest possible coordinate matrix representing our transformation?'' If we are allowed to specify both the domain and codomain basis, the answer is quite simple. 

\PROP Let $T:V \to W$ be a linear transformation between two finite dimensional vector spaces over some field. Then there is a basis $\alpha$ for $V$ and basis $\beta$ for $W$ such that $[T]_\alpha^\beta = \begin{bmatrix} 0 & I \\ 0 & 0 \end{bmatrix}$ where the zeros are appropriately sized zero matrices and $I$ is an $r \times r$ identity matrix where $r=\rank(T)$.

\bproof
Let $\{ \B v_1,\dots,\B v_n\}$ be a basis for $\ker(T)$. This is a linearly independent subset of $V$ so we can extend it to a basis for $V$: $\alpha = \{\B v_1,\dots,\B v_n, \B u_1,\dots,\B u_r\}$. We have that $T(V) = T(\spn \alpha) = \spn T(\alpha) = \spn \{T(\B v_1)\,\dots,T(\B v_n), T(\B u_1),\dots,T(\B u_r)\} = \spn \{T(\B u_1),\dots,T(\B u_r)\}$ since $T(\B v_i)=\B 0$ for $i=1,\dots,n$. Suppose $c_1T(\B u_1)+\cdots+c_rT(\B u_r)=\B 0$ so that $T(c_1\B u_1+\cdots+c_r\B u_r)=\B 0$. Thus $c_1\B u_1+\cdots+c_r\B u_r \in \ker(T)$. This means that $c_1\B u_1+\cdots+c_r\B u_r = a_1\B v_1+\cdots+a_n\B v_n$ for some scalars $a_1,\dots,a_n$. But then $c_1\B u_1+\cdots+c_r\B u_r -a_1\B v_1-\cdots-a_n\B v_n=\B 0$ and so $c_1=\cdots=c_r=-a_1=\cdots=-a_n=0$ since $\alpha = \{\B v_1,\dots,\B v_n, \B u_1,\dots,\B u_r\}$ is linearly independent. Therefore, $\{T(\B u_1),\dots,T(\B u_r)\}$ is linearly indpendent. This is a basis for the range of $T$ so that $r=\rank(T)$. We extend this linearly independent subset of the codomain $W$ to a basis for $W$, say $\beta = \{ T(\B u_1),\dots,T(\B u_r), \B w_1,\dots, \B w_m\}$. Then $T(\B v_i)=\B 0$ for $i=1,\dots,n$ implies that the first $n$ columns of $[T]_\alpha^\beta$ are filled with zeros. Evaluating $T$ on the rest of $\alpha$ (i.e., plugging in $\B u_j$ for $j=1,\dots,r$) we have $T(\B u_j)$. Since this is the $j$-th element in of $\beta$, the $(n+j)$-th column of $[T]_\alpha^\beta$ has a 1 in the $j$-th row and zeros elsewhere. Thus $[T]_\alpha^\beta$ has the form we promised.
\eproof 

This above result is nice enough, but in the case that $T$ is a linear operator (i.e., $T:V \to V$) it seems strange to have different bases for the domain ($=V$) and codomain (also $=V$). Thus we ask, ``What is a nicest/simplest possible coordinate matrix $[T]_\beta^\beta$ for a linear operator $T:V \to V$?'' This is a much more difficult problem. In fact, our field starts playing a role in this problem. If the characteristic polynomial of $T$ {\it splits} (i.e., factors into linear factors), we can demand $[T]_\beta^\beta$ be in {\it Jordan Form}. This is {\it almost} diagonal. However, if the characteristic polynomial does not split and we don't want to enlarge our field of scalars, we have to resort to {\it Rational Canonical Form} (based on so-called invariant factors) or {\it Primary Rational Canonical Form} (based on elementary divisors). We shall not pursue these forms here. 

\vspace{0.05in}

\noindent {\bf Assumption:} $T:V \to V$ is a linear operator on a finite dimensional vector space $V$ over a field $\mathbb{F}$, say $\dim(V)=n$. Moreover, assume that the characteristic polynomial splits (over $\mathbb{F}$): \fbox{$\det(tI-T) = (t-\lambda_1)^{a_1}\cdots(t-\lambda_\ell)^{a_\ell}$} where we assume that $\lambda_i \not= \lambda_j$ for $i\not=j$ and $a_i>0$. 

\vspace{0.05in}

Recall that $a_j$ is the {\it algebraic multiplicity} of the {\it eigenvalue} $\lambda_j$. Let $E_\lambda = \ker(T-\lambda I) = \{ \B v\in V \;|\; T(\B v)=\lambda \B v\}$ be the {\it eigenspace} associated with $\lambda$. We call $g_\lambda= \dim(E_\lambda)$ the {\it geometric multiplicity} of $\lambda$. Notice that $g_\lambda>0$ if and only if $\lambda$ is an eigenvalue. If (and it turns out -- only if) $g_j=a_j$ for all $j=1,\dots,\ell$, we have a basis of eigenvectors, $\beta$, and $[T]_\beta^\beta$ is a diagonal matrix with the eigenvalues appearing on the diagonal (each repeated according to its algebraic multiplicity). We now seek to have a basis of vectors that are close to being eigenvectors so our coordinate matrix is close to being diagonal. 

\vspace{0.05in}

\DEF Let $K_\lambda = \{ \B v \in V \;|\; (T-\lambda I)^k(\B v)=\B 0 \text{ for some } k >0\}$. We call  $K_\lambda$ a {\it generalized eigenspace} associated with $\lambda$. Its nonzero members (if it has any) are called {\it generalized eigenvectors}. 

\vspace{0.05in}

{\it Note:} Let $\B v \not= \B 0$ and $\B v \in K_\lambda$. Let $k$ be the smallest positive integer such that $(T-\lambda I)^k(\B v)=\B 0$. Then $\B w=(T-\lambda I)^{k-1}(\B v) \not= \B 0$ but $(T-\lambda I)(\B w) = (T -\lambda I)^k(\B v)=\B 0$. This means $\B w$ is an eigenvector with eigenvalue $\lambda$. In other words, $K_\lambda \not= \{\B 0\}$ if and only if $\lambda$ is an eigenvalue. 

In fact, $\{\B 0\} =\ker(I)=\ker(T-\lambda I)^0 \subseteq E_\lambda =\ker(T-\lambda I) \subseteq \ker(T-\lambda I)^2 \subseteq \ker(T-\lambda I)^3 \subseteq \cdots \subseteq \bigcup_{k=1}^\infty \ker(T-\lambda I)^k = K_\lambda$ since a lower power of $T-\lambda I$ killing a vector implies that any higher power does as well. Recall that $V$ is {\it finite dimensional}. This implies that our {\it chain} of subspaces $\cdots \subseteq \ker(T-\lambda I)^k \subseteq \ker(T-\lambda I)^{k+1} \subseteq \cdots$ cannot grow forever (each proper containment implies a growth in dimension which is capped at $\dim(V)=n$). In particular, $K_\lambda=\ker(T-\lambda I)^n$. In fact, we can do much better. Once we know about Jordan form, it is obvious that $K_{\lambda_j} = \ker(T-\lambda_j I)^{m}$ where $m$ is the size of the largest Jordan block associated with $\lambda_j$.

\THM Our vector space is the direct sum of generalized eigenspaces: $V=K_{\lambda_1} \oplus K_{\lambda_2} \oplus \cdots \oplus K_{\lambda_\ell}$. In particular, $V$ has a basis of generalized eigenvectors. Moreover, $K_{\lambda_j}=\ker(T-\lambda_j I)^{a_j}$ and $\dim(K_{\lambda_j})=a_j$ (the algebraic multiplicity of $\lambda_j$) for each $j=1,\dots,\ell$.

\bproof
First, we show that the generalized eigenspaces form a direct sum. For each $i=1,\dots,\ell$, let $k_i$ be a positive integer such that $K_{\lambda_i} = \ker(T-\lambda_i)^{k_i}$. Let $\B v \in K_{\lambda_j} \cap \left( \sum_{i \not= j} K_{\lambda_i} \right)$. Now $(t-\lambda_j)^{k_j}$ and $\prod_{i\not=j} (t-\lambda_i)^{k_i}$ are relatively prime polynomials. Thus, by the extended Euclidean algorithm, there exists polynomials $f(t)$ and $g(t)$ such that $f(t)(t-\lambda_j)^{k_j}+g(t)\prod_{i\not=j} (t-\lambda_i)^{k_i} = 1$. Therefore, $\B v = I(\B v) = f(T)(T-\lambda_j I)^{k_j}(\B v)+g(T)\prod_{i\not=j} (T-\lambda_i I)^{k_i}(\B v)=f(T)(\B 0)+g(T)(\B 0)=\B 0$ since vectors in $K_{\lambda_j}$ are killed by $(T-\lambda_j I)^{k_j}$ and vectors in $\sum_{i \not= j} K_{\lambda_i}$ are killed by $\prod_{i\not=j} (T-\lambda_i I)^{k_i}$. Therefore, $K_{\lambda_j} \cap \left( \sum_{i \not= j} K_{\lambda_i} \right) = \{\B 0\}$ and thus our sum is direct.

Next, for some $1 \leq j \leq \ell$, let $W=(T-\lambda_j I)^{k_j}(V)$ (i.e., $K_{\lambda_j}$ is the kernel and $W$ is the image of $(T-\lambda_j I)^{k_j}$). Let $\B v \in K_{\lambda_j} \cap W$. Since $\B v \in W$, there exists some $\B w \in V$ such that $(T-\lambda_j I)^{k_j}(\B w)=\B v$. Therefore, by the definition of $\B w$ and since $\B v$ lies in the kernel of $(T-\lambda_j I)^{k_j}$, we have $(T-\lambda_j I)^{2{k_j}}(\B w) = (T-\lambda_j I)^{k_j}[(T-\lambda_j I)^{k_j}(\B w)] = (T -\lambda_j I)^{k_j}(\B v)=\B 0$. Thus $\B w \in \ker(T-\lambda_j I)^{2k_j} = \ker(T-\lambda_j I)^{k_j}=K_{\lambda_j}$. In other words, $\B v =(T-\lambda_j I)^{k_j}(\B w)=\B 0$. Thus $K_{\lambda_j} \cap W =\{\B 0\}$.  Notice that $\dim(K_{\lambda_j})+\dim(W) = \mathrm{nullity}(T-\lambda_j I)^{k_j} + \mathrm{rank}(T-\lambda_j I)^{k_j}=\dim(V)$. Therefore, $V=K_{\lambda_j} \oplus W$. Also, notice that since $T$ commutes with $(T-\lambda_j I)^{k_j}$, we have both $T(K_{\lambda_j}) \subseteq K_{\lambda_j}$ and $T(W) \subseteq W$ (i.e., our decomposition is $T$-invariant). 

Let $T_1$ be the restriction of $T$ to $K_{\lambda_j}$ and $T_2$ be the restriction of $T$ to $W$. Since $K_{\lambda_j} \cap W=\{\B 0\}$ and $K_{\lambda_j}$ contains all of the eigenvectors associated with eigenvalue $\lambda_j$, we have that $\lambda_j$ is not an eigenvalue of $T_2$. Also, since $K_{\lambda_j} \cap K_{\lambda_i} =\{\B 0\}$ for $i \not=j$ (because the generalized eigenspaces form a direct sum), we have that $\lambda_j$ is the only eigenvalue of $T_1$. Next, because $V=K_{\lambda_j} \oplus W$ (and these subspaces are $T$-invariant), the characteristic polynomial of $T$ is the product of the characteristic polynomials of $T_1$ and $T_2$. But $\lambda_j$ is the only eigenvalue of $T_1$ and it is not an eigenvalue of $T_2$. Therefore, the characteristic polynomial of $T_1$ only has $t-\lambda_j$ factors and $T_2$'s characteristic polynomial cannot have any $t-\lambda_j$ factors. Thus the characteristic polynomial of $T_1$ must be $(t-\lambda_j)^{a_j}$ and the characteristic polynomial of $T_2$ must be $\prod_{i\not=j} (t-\lambda_i)^{a_i}$. Consequently, $\dim(K_{\lambda_j})$ (i.e., the dimension of the domain of $T_1$) must be $a_j$ (i.e., the degree of $T_1$'s characteristic polynomial).

Finally, we have $\dim(K_{\lambda_1} \oplus K_{\lambda_2} \oplus \cdots \oplus K_{\lambda_\ell}) = \dim(K_{\lambda_1})+\cdots+\dim(K_{\lambda_\ell})=a_1+\cdots+a_\ell$ (i.e., the degree of the characteristic polynomial of $T$). Thus  $\dim(K_{\lambda_1} \oplus K_{\lambda_2} \oplus \cdots \oplus K_{\lambda_\ell}) = n=\dim(V)$. Therefore, $K_{\lambda_1} \oplus K_{\lambda_2} \oplus \cdots \oplus K_{\lambda_\ell}=V$ and so the theorem follows.
\eproof

\COR We have $1 \leq g_j \leq a_j$ (i.e., the geometric multiplicity never exceeds the algebraic mulitiplicity) since $E_{\lambda_j} \subseteq K_{\lambda_j}$. Also, $E_{\lambda_1} \oplus \cdots \oplus E_{\lambda_\ell}$ (i.e., eigenspaces form a direct sum) since $E_{\lambda_j} \cap \left(\sum_{i\not=j} E_{\lambda_i}\right) \subseteq K_{\lambda_j} \cap \left(\sum_{i\not=j} K_{\lambda_i}\right) = \{\B 0\}$.

\vspace{0.05in}

We note that since $T$ commutes with $(T-\lambda I)^k$ for any positive integer $k$, we have $\ker(T-\lambda I)^k$ is $T$-invariant. In particular, eigenspaces and generalized eigenspaces are $T$-invariant. This means that if we create a basis for $V$ by (disjoint) unioning bases for our generalized eigenspaces, our coordinate matrix will be block diagonal with $a_j \times a_j$ blocks ($j=1,\dots,\ell$).

To finish developing Jordan form we need to seek nicely structured bases for our generalized eigenspaces. In particular, we wish to form bases consisting of {\it chains} of generalized eigenvectors: $\B v, (T-\lambda I)(\B v), (T-\lambda I)^2(\B v), \dots, (T-\lambda I)^{k-1}(\B v)$ where $\B v\in K_{\lambda}$ and $(T-\lambda I)^{k}(\B v)=\B 0$. First, we recall a short proof by Mark Wildon establishing the existence a basis for $K_\lambda$ consisting of such chains. Then we will put this together with our previous theorem to establish the existence of our Jordan canonical form.

\vspace{0.05in}

\THM The generalized eigenspace $K_\lambda$  has a basis consisting of chains of generalized eigenvectors.

\bproof
First, restrict $T-\lambda I$ to the domain $K_\lambda$ (this is possible since $K_\lambda$ is $(T-\lambda I)$-invariant).
We proceed by induction on the dimension on the domain of our linear operator. The zero dimensional base case is trivial: If $K_\lambda =\{\B 0\}$, then $\lambda$ is not an eigenvalue. Its basis is the empty set and thus the theorem is vacuously satisfied. Suppose $K_\lambda \not= \{\B 0\}$ and let $a$ be the algebraic multiplicity of $\lambda$ (i.e., $\dim(K_\lambda)=a$) so that $K_\lambda = \ker(T-\lambda I)^a$. Assume the theorem holds for all spaces of dimension less than $a$.

Notice that $(T-\lambda I)(K_\lambda)$ is properly contained in $K_\lambda$ since otherwise $K_\lambda = (T-\lambda I)(K_\lambda) = (T-\lambda I)^2(K_\lambda) = \cdots = (T-\lambda I)^a(K_\lambda) = \{ \B 0\}$ (contradiction). Also, if $T-\lambda I=0$ on $K_\lambda$, then $K_\lambda=E_\lambda$ and we have a basis of eigenvectors (and thus are done since eigenvectors are chains of length 1).

Therefore, we may assume that $(T-\lambda I)(K_\lambda)$ is non-zero and properly contained in $K_\lambda$. We apply an inductive hypothesis to $(T-\lambda I)(K_\lambda)$ and find $\B v_1,\dots,\B v_m \in (T-\lambda I)(K_\lambda)$ so that $\B v_1,(T-\lambda I)(\B v_1),\dots,(T-\lambda I)^{b_1-1}(\B v_1),\dots,\B v_m,(T-\lambda I)(\B v_m),\dots,(T-\lambda I)^{b_m-1}(\B v_m)$ is a basis of chains of  generalized eigenvectors for $(T-\lambda I)(K_\lambda)$ and $(T-\lambda I)^{b_j}(\B v_j)=\B 0$ for $j=1,\dots,m$. Consequently, $\dim((T-\lambda I)(K_\lambda))=b_1+\cdots+b_m$.

Notice $\B v_j \in (T-\lambda I)(K_\lambda)$ implies we may choose some $\B u_j \in K_\lambda$ such that $(T-\lambda I)(\B u_j)=\B v_j$ (so now $\B v_j,\dots,(T-\lambda I)^{b_j-1}(\B v_j)$ becomes $(T-\lambda I)(\B u_j),\dots,(T-\lambda I)^{b_j})(\B u_j)$). Clearly $\ker(T-\lambda I)$ contains the linearly indpendent vectors $(T-\lambda I)^{b_1}(\B u_1),\dots,(T-\lambda I)^{b_m}(\B u_m)$ (formerly called $(T-\lambda I)^{b_1-1}(\B v_1),\dots,(T-\lambda I)^{b_m-1}(\B v_m)$). We extend this set to a basis for $\ker(T-\lambda I)$ by adjoining $\B w_1,\dots,\B w_p$. 

Claim: $\B u_1,(T-\lambda I)(\B u_1),\dots,(T-\lambda I)^{b_1}(\B u_1),\dots,\B u_m,(T-\lambda I)(\B u_m),\dots,(T-\lambda I)^{b_m}(\B u_m),\B w_1,\dots,\B w_p$ is a basis for $K_\lambda$ consisting of chains of generalized eigenvectors. Notice that $(T-\lambda)^{b_i+1}(\B u_i)=\B 0$ for $i=1,\dots,m$ and $(T-\lambda I)(\B w_q)=\B 0$ for $q=1,\dots,p$. Suppose $\sum_{i=1}^m \sum_{j=0}^{b_i} c_{ij} (T-\lambda I)^j(\B u_i)+\sum_{q} d_q\B w_q=\B 0$. Applying $T-\lambda I$ to this equation, we kill off the terms coming from elements of $\ker(T-\lambda I)$. We are left with $\sum_{i=1}^m\sum_{j=0}^{b_i-1} c_{ij}(T-\lambda I)^{j+1}(\B u_i)=\B 0$. But this is just a linear combination of vectors coming from our basis for $(T-\lambda I)(K_\lambda)$. Therefore, $c_{ij}=0$ for all $i=1,\dots,m$ and $j=0,\dots,b_i-1$. Thus our equation is becomes: $c_{1b_1}(T-\lambda I)^{b_1}(\B u_1)+\cdots+c_{mb_m}(T-\lambda I)^{b_m}(\B u_m)+d_1\B w_1+\cdots+d_p\B w_p=\B 0$. But these form a basis for $\ker(T-\lambda I)$ and thus the rest of our scalar coefficients are zero.
Therefore, our set is linearly independent. Finally, notice that our proposed basis has $(b_1+1)+\cdots+(b_m+1)+p = b_1+\cdots+b_m+m+p$ vectors in it. We already noted that $\dim((T-\lambda I)(K_\lambda))=b_1+\cdots+b_m$ and from our construction of $\B w_q$'s we have $\dim(\ker(T-\lambda I))=m+p$. Therefore, by the rank nullity theorem $\dim(K_\lambda) = b_1+\cdots+b_m+m+p$. Thus our set also spans $K_\lambda$. This establishes our claim.
\eproof

These theorems put together tells us that $V$ has a basis consisting of chains of generalized eigenvectors. Once again, since $T$ commutes with $T-\lambda I$, it is not hard to see that the span of a chain of generalized eigenvectors is a $T$-invariant subspace of $V$. Thus if we use a basis consisting of chains of generlized eigenvectors our coordinate matrix will be block diagonal with each block corresponding to some chain. Let us see what such a block looks like. To that end suppose $\B v_1 = (T-\lambda I)^{k-1}(\B v), \dots,\B v_{k-1}=(T-\lambda I)(\B v), \B v_1=\B v$ is a chain of generalized eigenvectors with $(T-\lambda I)^k(\B v)=\B 0$. You may notice that we are writing our chains backwards from our previous convention. Also, for convenience let $\B v_{0}=\B 0$. Notice that $(T-\lambda I)(\B v_j)=\B v_{j-1}$. Therefore, $T(\B v_j) = \B v_{j-1}+\lambda \B v_j$. Thus the $j$-th column of our block will have a 1 in the $(j-1)$-st row and a $\lambda$ in its $j$-th row -- unless we are looking at the very first column where: $T(\B v_1)=\lambda \B v_1+\B v_{0}=\lambda \B v_1$ so the first column is just a $\lambda$ followed by zeros. We get the following matrix:
$$J_\lambda = \begin{bmatrix} \lambda &           1  &         0 & \cdots & 0 & 0 \\
                                         0 & \lambda &         1 & \cdots  & 0 & 0 \\
                                         0 &  0           & \lambda & \cdots & 0 & 0 \\
                                 \vdots &  \vdots  &  \vdots    & \ddots & \vdots & \vdots \\
                                        0  &           0  &         0 & \cdots & \lambda & 1 \\
                                        0  &           0  &         0  & \cdots & 0 & \lambda \end{bmatrix} 
=\begin{bmatrix} \lambda &           0  &         0 & \cdots & 0 & 0 \\
                                         0 & \lambda &         0 & \cdots  & 0 & 0 \\
                                         0 &  0           & \lambda & \cdots & 0 & 0 \\
                                 \vdots &  \vdots  &  \vdots    & \ddots & \vdots & \vdots \\
                                        0  &           0  &         0 & \cdots & \lambda & 0 \\
                                        0  &           0  &         0  & \cdots & 0 & \lambda \end{bmatrix}+
\begin{bmatrix} 0 &           1  &         0 & \cdots & 0 & 0 \\
                                         0 & 0 &         1 & \cdots  & 0 & 0 \\
                                         0 &  0           & 0 & \cdots & 0 & 0 \\
                                 \vdots &  \vdots  &  \vdots    & \ddots & \vdots & \vdots \\
                                        0  &           0  &         0 & \cdots & 0 & 1 \\
                                        0  &           0  &         0  & \cdots & 0 & 0 \end{bmatrix}=\lambda I_k+N_k$$
It is interesting to note that $(N_k)^k=0$ so that $N_k$ is {\it nilpotent}. More precisely $(N_k)^{k-1}\not=0$ but $(N_k)^{k}=0$ so it is nilpotent of degree $k$. Obviously the diagonal part (i.e., $\lambda I$) and the nilpontent part of our Jordan block commute with each other. In general, if $\beta$ is a basis consisting of chains of generalized eigenvectors, we get 
$$[T]_\beta^\beta = J = \begin{bmatrix} J_1 & 0                       & \cdots & 0 \\
                                                              0                       & J_2 & \cdots & 0 \\
                                                              \vdots               & \vdots              & \ddots & \vdots \\
                                                              0                        & 0                      & \cdots & J_s \end{bmatrix}$$
where $J_1,J_2,\dots,J_k$ are the Jordan blocks corresponding to our various chains of generalized eigenvectors. This is called a {\it Jordan form} for $T$. Notice that since each block can be written as a sum of a diagonal and nilpotent part, we can write $J=D+N$ where $D$ is diagonal and $N$ is nilpotent (its degree of nilpotency will be $k$ if the size of the largest Jordan block is $k \times k$). It isn't hard to show that the diagonal and nilpotent parts of $J$ commute: $DN=ND$. So while it is not always possible to diagonalize our linear operator, under the condition our characteristic polynomial splits, we can get close to diagonalizing. We are off by a nilpotent part and better yet, that part commutes with our diagonal part.

The question of whether Jordan form is unique is wrapped up with computing the Jordan form of a matrix. To determine the Jordan form we need to determine the number and length of our chains associated with each eigenvalue. Notice that each chain starts with an eigenvector. Thus $\dim(E_\lambda)=\dim(\ker(T-\lambda I))$ is equal to the number of chains associated with $\lambda$. More generally, let $n_k = \dim(\ker(T-\lambda I)^k)$. Let us call $\B v$ such that $(T-\lambda I)^k(\B v)=\B 0$ but $(T-\lambda I)^{k-1}(\B v) \not= \B 0$ a generalized eigenvector of degree $k$ (so eigenvectors have degree 1 and the zero vector has degree 0). Then $n_0=0$, $n_1$ is the number of independent eigenvectors, $n_2$ is the number of independent eigenvectors plus generalized eigenvectors of degree 2. In general, $n_k$ is the number of linearly independent eigenvectors of degree at most $k$. Notice that a $k$-chain is made up from one generalized eigenvector of each degree from 1 up to $k$. Thus the numbers $n_1,n_2,\dots$ will let us determine how many chains we have (and how long they are). In particular, these numbers completely determine our Jordan block structure associated with $\lambda$. Putting this together, we have that our Jordan form is uniquely determined up to rearraging the order of our Jordan blocks.

%P = matrix(SR,[[0,1,1,0,-1],[1,0,-1,1,0],[2,1,1,0,1],[0,1,2,0,1],[1,1,1,-1,1]])
%A = matrix(SR,[[2,1,0,0,0],[0,2,1,0,0],[0,0,2,0,0],[0,0,0,2,0],[0,0,0,0,2]])
%pretty_print("A = ", A)
%pretty_print("P^(-1) = ", P^(-1))
%B = 2*P^(-1)*A*P
%pretty_print("B = ", B)
%pretty_print(B.eigenvalues())
%print(latex(B))

\EX Consider $B=\begin{bmatrix} 2 & -1 & -1 & 0 & -1 \\ 7 & 7 & 2 & 1 & 3 \\ -4 & -2 & 2 & 0 & -2 \\ 2 & 1 & 1 & 4 & 1 \\  1 & 1 & 2 & -1 & 5 \end{bmatrix}$. We can use software to find that $\det(tI-B)=(t-4)^5$. Therefore, the only eigenvalue of $B$ is $\lambda=4$. Next, we compute the nullity of powers of $B-4I$: $n_0=0$, $n_1=\mathrm{nullity}(B-4I)=3$, $n_2=\mathrm{nullity}(B-4I)^2=4$, $n_3=\mathrm{nullity}(B-4I)^3=5$, $n_4=\mathrm{nullity}(B-4I)^2=5$ (in fact, $n_k=5$ for all $k \geq 3$). This means we have 3 chains of generalized eigenvectors. But only one of them is longer than 1 vector long. This chain then also extends to length 3. So we have two 1-chains and one 3-chain. Therefore, the Jordan form of $B$ is
$J = \begin{bmatrix} 4 & 0 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 & 0\\ 0 & 0 & 4 & 1 & 0\\ 0 & 0 & 0 & 4 & 1 \\ 0 & 0 & 0 & 0 & 4 \end{bmatrix}$. 

%B = matrix(SR,[[2,-1,-1,0,-1],[7,7,2,1,3],[-4,-2,2,0,-2],[2,1,1,4,1],[1,1,2,-1,5]])
%C = B-4*matrix.identity(5)
%for k in range(0,6):
%    print((C^k).nullity())
%C.echelon_form()

The task of finding a matrix $P$ such that $P^{-1}BP=J$ is considerbly more difficult. This amounts to actually finding our chains of generalized eigenvectors. We simply find one chain at a time and then when finding a new chain, make sure it is independent from the previously found ones. We start with our longest chain. We need a vector $\B v_1$ such that $(B-4I)^3\B v_1=\B 0$ but $(B-4I)^2\B v_1 \not= \B 0$. This is easy since $(B-4I)^3$ is the zero matrix. Examining $(B-4I)^2$, we see that $\B v_3=[1\;0\;0\;0\;0]^T$ will do the job. Then let $\B v_2=(B-4I)\B v_3 = [-2\;7\;-4\;2\;1]^T$ and $\B v_1 = (B-4I)\B v_2 = [0\;4\;0\;0\;-4]^T$. Our next longest chains are the only remaining chains (of length 1). To find these we need to find vectors such that $(B-4I)\B x=\B 0$ but $(B-4I)^0\B x=\B x\not=\B 0$ {\it and} they must be independent from our other vector at this level (i.e., independent from $\B v_1$). Thus we find a basis for $\ker(B-4I)$ and then extend $\{ \B v_1 \}$ (a linearly indpendent set) to a basis. The extension part is gives us our missing vectors. We find that $\B u_1 = [1\;-3\;1\;0\;0]^T$, $\B w_1 = [-1\;2\;0\;1\;0]^T$, and a multiple of $\B v_1$ form a basis for $\ker(B-4I)$. Thus the first two vectors are our desired extension. Therefore: $\{\B u_1,\B w_1,\B v_1,\B v_2,\B v_3\}$ is our basis of chains of generalized eigenvectors. Thus letting $P=\begin{bmatrix} 1 & -1 & 0 & -2 & 1 \\ -3 & 2 & 4 & 7 & 0 \\ 1 & 0 & 0 & -4 & 0 \\ 0 & 1 & 0 & 2 & 0 \\ 0 & 0 & -4 & 1 & 0 \end{bmatrix}$, we find that $P^{-1}BP=J$ (since we organized our chains so they had length 1, length 1, then length 3).

Since finding the Jordan form of a matrix is relatively easy, but finding the change of basis matrix is hard, we will pass this task off to software. In Maple, after loading the linear algebra package (i.e., {\color{red}\verb|with(LinearAlgebra):|}) and defining your matrix (e.g. {\color{red}\verb|A|}), you can find a transition matrix with the command {\color{red}\verb|P := JordanForm(A,output='Q');|}. Then {\color{red}\verb|J := P^(-1).A.P;|} will be your Jordan form.

\vspace{0.05in}

\noindent 
{\bf {}[Sketch] Finding $P$ -- An Algorithm:} (I) Compute the characteristic polynomial and determine all eigenvalues, $\lambda$, and their algebraic multiplicities, $a$. (II) For each eigenvalue $\lambda$: (1) Compute the nullity of $\ker(T-\lambda I)^k$ (call it $n_k$) for $k=1,2,\dots$ until $n_k=n_{k+1}$ (this must happen by $n_a$). The last number in this list is $\dim(K_\lambda)$. Use these numbers to determine the number of and length of each chain of generalized eigenvectors. (2) Let $W=\spn(\text{previously found basis vectors})$ (initially $W=\{\B 0\}$). (3) Determine the largest positive integer $k$ such that $\ker(T-\lambda I)^{k-1}+W$ is properly contained in $\ker(T-\lambda I)^k$. (4) Pick some $\B v \in \ker(T-\lambda I)^k$ such that $\B v \not\in \ker(T-\lambda I)^{k-1}+W$. (5) Add $(T-\lambda I)^{k-1}(\B v), (T-\lambda I)^{k-2}(\B v), \dots, (T-\lambda I)(\B v), \B v$ to your basis. (6) If you have not found $\dim(K_\lambda)$ vectors, go back to (2). (III) Now let assemble the (coordinate representations) of each basis vector found for each generalized eigenspace in some order (making sure to keep chains together and in the order listed in (5)) into your matrix $P$.

\vspace{0.05in}

This leaves many questions. One big one might be, ``Why do we care?'' In the end, having a standard form is incredibly useful. If you want to test a theorem about linear operators, you most likely just need to think about how it works in the case your matrix is in Jordan form. For example, we already know that $\det(A)$ is the product of the eigenvalues of $A$ (counting multiplicity) and $\mathrm{trace}(A)$ is the sum. This is obvious from the Jordan form. Notice that the number of Jordan blocks counts the number of linearly independent eigenvectors. Our matrix is diagonalizable if and only if all of our Jordan blocks are $1 \times 1$! 

If we let $f(t)=\det(tI-A)$ (i.e., the characteristic polynomial of $A$), then the Cayley-Hamilton Theorem states that $f(A)=0$ (you cannot just plug $t=A$ into the definition to prove this -- why?). Thus $A$ is a root of a polynomial of degree $n$ (given $A$ is $n \times n$). One might ask what the minimum degree polynomial might be. The {\it minimal polynomial} for $A$ is the monic (=leading coefficient is 1) polynomial $m(t)$ such that $m(A)=0$ and $A$ is not the root of any lower degree polynomial. It isn't hard to see from the Jordan form of $A$, if the size of the largest Jordan block associated with $\lambda_i$ is $m_i\times m_i$ (for each eigenvalue $\lambda_i$), then $m(t)=(t-\lambda_1)^{m_1}\cdots(t-\lambda_\ell)^{m_\ell}$. Not only does this imply that the minimal polynomial divides the characteristic polynomial, but it also reveal the theorem: $A$ is diagonalizable if and only if its minimal polynomial has no repeated roots!

Finally, Jordan form is useful if one wants to define functions of matrices. Suppose you have a function $f(x)$ defined via a power series: $f(x)=c_0+c_1x+c_2x^2+\cdots = \sum\limits_{k=0}^\infty c_k x^k$. Notice that if $A = PJP^{-1}$ then $A^k=(PJP^{-1})\cdots(PJP^{-1})=PJP^{-1}PJP^{-1}\cdots PJP^{-1}=PJ\cdots JP^{-1}=PJ^kP^{-1}$. Thus (excusing sum analytic/convergence type issues), $f(A) = \sum\limits_{k=0}^\infty c_kA^k= \sum\limits_{k=0}^\infty c_kPJ^kP^{-1} = P \left(\sum\limits_{k=0}^\infty c_kJ^k \right) P^{-1} = Pf(J)P^{-1}$. Therefore, if you can sort out how to evaluate your function on a Jordan block, you can figure out how to evaluate it on any matrix! 

In particular, $e^x = 1+x+\frac{x^2}{2}+\frac{x^3}{3!}+\cdots = \sum\limits_{k=0}^\infty \frac{x^k}{k!}$. One can show that if $x$ and $y$ are {\it commuting} formal variables, then $e^{x+y}=e^xe^y$. Notice that $J=D+N$ where $D$ and $N$ are the diagonal and nilpotent parts of the Jordan form $J$. But $D$ and $N$ commute! Thus $e^J=e^{D+N}=e^De^N$. Since computing powers of a diagonal matrix just amounts to computing powers of its diagonals, applying a function to a diagonal matrix just amounts to applying that function to its diagonals. Thus we can easily compute $e^D$. On the other hand, a high enough power of a nilpotent matrix is zero, so a power series $f(N)$ is actually a finite sum (a polynomial in $N$). Thus we can compute $e^N$. Therefore, we can effectively compute $e^A = Pe^JP^{-1}=Pe^De^NP^{-1}$. [Although there are easier ways to compute $e^A$.] Why it this useful? The answer is differential equations and much more! 



\end{document}