Proof of Jordan Normal Form

$\newenvironment {prompt}{}{} \newcommand {\Sec }[2]{\section {#1}} \newcommand {\trademark }[0]{{R\!\!\!\!\!\bigcirc }} \newcommand {\EXER }[0]{\section *{Exercises}} \newcommand {\CEXER }[0]{} \newcommand {\TEXER }[0]{} \newcommand {\R }[0]{\mbox {$\Bbb {R}$}} \newcommand {\C }[0]{\mbox {$\Bbb {C}$}} \newcommand {\Z }[0]{\mbox {$\Bbb {Z}$}} \newcommand {\N }[0]{\mbox {$\Bbb {N}$}} \newcommand {\D }[0]{\mbox {{\bf D}}} \newcommand {\setmin }[0]{\;\mbox {--}\;} \newcommand {\Matlab }[0]{{M\small {AT\-LAB}} } \newcommand {\Matlabp }[0]{{M\small {AT\-LAB}}} \newcommand {\computer }[0]{\Matlab Instructions} \newcommand {\half }[0]{\mbox {$\frac {1}{2}$}} \newcommand {\compose }[0]{\raisebox {.15ex}{\mbox {{\scriptsize $\circ $}}}} \newcommand {\AND }[0]{\quad \mbox {and}\quad } \newcommand {\vect }[2]{\left (\begin {array}{c} #1_1 \\ \vdots \\ #1_{#2}\end {array}\right )} \newcommand {\mattwo }[4]{\left (\begin {array}{rr} #1 & #2\\ #3 &#4\end {array}\right )} \newcommand {\mattwoc }[4]{\left (\begin {array}{cc} #1 & #2\\ #3 &#4\end {array}\right )} \newcommand {\vectwo }[2]{\left (\begin {array}{r} #1 \\ #2\end {array}\right )} \newcommand {\vectwoc }[2]{\left (\begin {array}{c} #1 \\ #2\end {array}\right )} \newcommand {\inv }[0]{^{-1}} \newcommand {\CC }[0]{{\cal C}} \newcommand {\CCone }[0]{\CC ^1} \newcommand {\Span }[0]{{\rm span}} \newcommand {\rank }[0]{{\rm rank}} \newcommand {\trace }[0]{{\rm tr}} \newcommand {\RE }[0]{{\rm Re}} \newcommand {\IM }[0]{{\rm Im}} \newcommand {\nulls }[0]{{\rm null\;space}} \newcommand {\dps }[0]{\displaystyle } \newcommand {\arraystart }[0]{\renewcommand {\arraystretch }{1.8}} \newcommand {\arrayfinish }[0]{\renewcommand {\arraystretch }{1.2}} \newcommand {\Start }[1]{\vspace {0.08in}\noindent {\bf Section~\ref {#1}}} \newcommand {\exer }[1]{\noindent {\bf \ref {#1}}} \newcommand {\ans }[0]{} \newcommand {\matthree }[9]{\left (\begin {array}{rrr} #1 & #2 & #3 \\ #4 & #5 & #6 \\ #7 & #8 & #9\end {array}\right )} \newcommand {\cvectwo }[2]{\left (\begin {array}{c} #1 \\ #2\end {array}\right )} \newcommand {\cmatthree }[9]{\left (\begin {array}{ccc} #1 & #2 & #3 \\ #4 & #5 & #6 \\ #7 & #8 & #9\end {array}\right )} \newcommand {\vecthree }[3]{\left (\begin {array}{r} #1 \\ #2 \\ #3\end {array}\right )} \newcommand {\cvecthree }[3]{\left (\begin {array}{c} #1 \\ #2 \\ #3\end {array}\right )} \newcommand {\cmattwo }[4]{\left (\begin {array}{cc} #1 & #2\\ #3 &#4\end {array}\right )} \newcommand {\thehelp }[0]{\thesection .\arabic {equation}} \newcommand {\matlabEquation }[0]{\let \oldtheequation \theequation \renewcommand {\theequation }{\oldtheequation *}\begin {equation}} \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument } \newcommand {\epstopdfsetup }[0]{\setkeys {ETE}} changed the theorem header of amsthm failed\MessageBreak }}} \newcommand {\GetTitleStringSetup }[0]{\setkeys {gettitlestring}} \newcommand {\Sectionformat }[2]{#1}$ $% This file was *autogenerated* from proofOfJordanNormalForm.sagetex.sage with % sagetex.py version 2015/08/26 v3.0-92d9f7a %bc5ee41734e1c11558aa1d9f6c6bcc0d% md5sum of corresponding .sage file (minus "goboom","current_tex_line",and pause/unpause lines)$

We prove the Jordan normal form theorem under the assumption that the eigenvalues of $A$ are all real. The proof for matrices having both real and complex eigenvalues proceeds along similar lines.

Let $A$ be an $n\times n$ matrix, let $\lambda _1,\ldots ,\lambda _s$ be the distinct eigenvalues of $A$ , and let $A_j = A-\lambda _jI_n$ .

The linear mappings $A_i$ and $A_j$ commute.

Proof: Just compute $A_iA_j = (A-\lambda _iI_n)(A-\lambda _jI_n)= A^2-\lambda _iA-\lambda _jA+ \lambda _i\lambda _jI_n,$ and $A_jA_i = (A-\lambda _jI_n)(A-\lambda _iI_n)= A^2-\lambda _jA-\lambda _iA+ \lambda _j\lambda _iI_n.$ So $A_iA_j=A_jA_i$ , as claimed. $\blacksquare$

Let $V_j$ be the generalized eigenspace corresponding to eigenvalue $\lambda _j$ .

$A_i:V_j\to V_j$ is invertible when $i\neq j$ .

Proof: Recall from Lemma ?? that $V_j=\nulls (A_j^k)$ for some $k\ge 1$ . Suppose that $v\in V_j$ . We first verify that $A_iv$ is also in $V_j$ . Using Lemma ??, just compute $A_j^kA_iv = A_iA_j^kv = A_i0 = 0.$ Therefore, $A_iv\in \nulls (A_j^k)=V_j$ .
Let $B$ be the linear mapping $A_i|V_j$ . It follows from Chapter ??, Theorem ?? that ${\rm nullity}(B) +\dim {\rm range}(B) = \dim (V_j).$ Now $w\in \nulls (B)$ if $w\in V_j$ and $A_iw=0$ . Since $A_iw = (A-\lambda _iI_n)w = 0$ , it follows that $Aw = \lambda _iw$ . Hence $A_jw = (A-\lambda _jI_n)w = (\lambda _i-\lambda _j)w$ and $A_j^kw = (\lambda _i-\lambda _j)^kw.$ Since $\lambda _i\neq \lambda _j$ , it follows that $A_j^kw=0$ only when $w=0$ . Hence the nullity of $B$ is zero. We conclude that $\dim {\rm range}(B) = \dim (V_j).$ Thus, $B$ is invertible, since the domain and range of $B$ are the same space. $\blacksquare$

Nonzero vectors taken from different generalized eigenspaces $V_j$ are linearly independent. More precisely, if $w_j\in V_j$ and $w = w_1 + \cdots + w_s = 0,$ then $w_j=0$ .

Proof: Let $V_j=\nulls (A_j^{k_j})$ for some integer $k_j$ . Let $C=A_2^{k_2}\compose \cdots \compose A_s^{k_s}$ . Then $0 = Cw = Cw_1,$ since $A_j^{k_j}w_j=0$ for $j=2,\ldots ,s$ . But Lemma ?? implies that $C|V_1$ is invertible. Therefore, $w_1=0$ . Similarly, all of the remaining $w_j$ have to vanish. $\blacksquare$

Every vector in $\R ^n$ is a linear combination of vectors in the generalized eigenspaces $V_j$ .

Proof: Let $W$ be the subspace of $\R ^n$ consisting of all vectors of the form $z_1+\cdots +z_s$ where $z_j\in V_j$ . We need to verify that $W=\R ^n$ . Suppose that $W$ is a proper subspace. Then choose a basis $w_1,\ldots ,w_t$ of $W$ and extend this set to a basis $\cal W$ of $\R ^n$ . In this basis the matrix $[A]_{\cal W}$ has block form, that is, $[A]_{\cal W} = \mattwo {A_{11}}{A_{12}}{0}{A_{22}},$ where $A_{22}$ is an $(n-t)\times (n-t)$ matrix. The eigenvalues of $A_{22}$ are eigenvalues of $A$ . Since all of the distinct eigenvalues and eigenvectors of $A$ are accounted for in $W$ (that is, in $A_{11}$ ), we have a contradiction. So $W=\R ^n$ , as claimed. $\blacksquare$

Let ${\cal V}_j$ be a basis for the generalized eigenspaces $V_j$ and let $\cal V$ be the union of the sets ${\cal V}_j$ . Then $\cal V$ is a basis for $\R ^n$ .

Proof

We first show that the vectors in $\cal V$ span $\R ^n$ . It follows from Lemma ?? that every vector in $\R ^n$ is a linear combination of vectors in $V_j$ . But each vector in $V_j$ is a linear combination of vectors in ${\cal V}_j$ . Hence, the vectors in $\cal V$ span $\R ^n$ .

Second, we show that the vectors in $\cal V$ are linearly independent. Suppose that a linear combination of vectors in $\cal V$ sums to zero. We can write this sum as $w_1 + \cdots + w_s = 0,$ where $w_j$ is the linear combination of vectors in ${\cal V}_j$ . Lemma ?? implies that each $w_j=0$ . Since ${\cal V}_j$ is a basis for $V_j$ , it follows that the coefficients in the linear combinations $w_j$ must all be zero. Hence, the vectors in $\cal V$ are linearly independent.

Finally, it follows from Theorem ?? of Chapter ?? that $\cal V$ is a basis. $\blacksquare$

In the basis $\cal V$ of $\R ^n$ guaranteed by Lemma ??, the matrix $[A]_{\cal V}$ is block diagonal, that is, $[A]_{\cal V} = \left (\begin {array}{ccc} A_{11} & 0 & 0 \\ 0 & \ddots & 0 \\ 0 & 0 & A_{ss} \end {array}\right ),$ where all of the eigenvalues of $A_{jj}$ equal $\lambda _j$ .

Proof: It follows from Lemma ?? that $A:V_j\to V_j$ . Suppose that $v_j\in {\cal V}_j$ . Then $Av_j$ is in $V_j$ and $Av_j$ is a linear combination of vectors in ${\cal V}_j$ . The block diagonalization of $[A]_{\cal V}$ follows. Since $V_j=\nulls (A_j^{k_j})$ , it follows that all eigenvalues of $A_{jj}$ equal $\lambda _j$ . $\blacksquare$

Lemma ?? implies that to prove the Jordan normal form theorem, we must find a basis in which the matrix $A_{jj}$ is in Jordan normal form. So, without loss of generality, we may assume that all eigenvalues of $A$ equal $\lambda _0$ , and then find a basis in which $A$ is in Jordan normal form. Moreover, we can replace $A$ by the matrix $A-\lambda _0I_n$ , a matrix all of whose eigenvalues are zero. So, without loss of generality, we assume that $A$ is an $n\times n$ matrix all of whose eigenvalues are zero. We now sketch the remainder of the proof of Theorem ??.

Let $k$ be the smallest integer such that $\R ^n = \nulls (A^k)$ and let $s=\dim \nulls (A^k)-\dim \nulls (A^{k-1})>0.$ Let $z_1,\ldots ,z_{n-s}$ be a basis for $\nulls (A^{k-1})$ and extend this set to a basis for $\nulls (A^k)$ by adjoining the linearly independent vectors $w_1,\ldots ,w_s$ . Let $W_k=\Span \{w_1,\ldots ,w_s\}.$ It follows that $W_k\cap \nulls (A^{k-1})=\{0\}$ .

We claim that the $ks$ vectors ${\cal W}=\{w_{j\ell }=A^\ell (w_j)\}$ where $0\le \ell \le {k-1}$ and $1\le j\le s$ are linearly independent. We can write any linear combination of the vectors in $\cal W$ as $y_k+\cdots +y_1$ , where $y_j\in A^{k-j}(W_k)$ . Suppose that $y_k+\cdots +y_1=0.$ Then $A^{k-1}(y_k+\cdots +y_1)= A^{k-1}y_k=0$ . Therefore, $y_k$ is in $W_k$ and in $\nulls (A^{k-1})$ . Hence, $y_k=0$ . Similarly, $A^{k-2}(y_{k-1}+\cdots +y_1)= A^{k-2}y_{k-1}=0$ . But $y_{k-1}=A\hat {y}_k$ where $\hat {y}_k\in W_k$ and $\hat {y}_k\in \nulls (A^{k-1})$ . Hence, $\hat {y}_k=0$ and $y_{k-1}=0$ . Similarly, all of the $y_j=0$ . It follows from $y_j=0$ that a linear combination of the vectors $A^{k-j}(w_1),\ldots ,A^{k-j}(w_s)$ is zero; that is $0 = \beta _1A^{k-j}(w_1) + \cdots + \beta _sA^{k-j}(w_s) = A^{k-j}(\beta _1w_1+\cdots +\beta _sw_s).$ Applying $A^{j-1}$ to this expression, we see that $\beta _1w_1+\cdots +\beta _sw_s$ is in $W_k$ and in the $\nulls (A^{k-1})$ . Hence, $\beta _1w_1+\cdots +\beta _sw_s = 0.$ Since the $w_j$ are linearly independent, each $\beta _j=0$ , thus verifying the claim.

Next, we find the largest integer $m$ so that $t=\dim \nulls (A^m)-\dim \nulls (A^{m-1})>0.$ Proceed as above. Choose a basis for $\nulls (A^{m-1})$ and extend to a basis for $\nulls (A^m)$ by adjoining the vectors $x_1,\ldots ,x_t$ . Adjoin the $mt$ vectors $A^\ell x_j$ to the set $\cal V$ and verify that these vectors are all linearly independent. And repeat the process. Eventually, we arrive at a basis for $\R ^n=\nulls (A^k)$ .

In this basis the matrix $[A]_{\cal V}$ is block diagonal; indeed, each of the blocks is a Jordan block, since $A(w_{j\ell }) = \left \{\begin {array}{cl}w_{j(\ell -1)} & 0<\ell \le k-1\\ 0 & \ell =1 \end {array}\right . .$ Note the resemblance with (??).