# Understanding the proof of Jordan normal form, by matrix trick

I read a proof for JNF which I am unclear.

Proof:

For any complex matrix $$A$$. Assume $$Av_1=\lambda v_1$$ for some $$v_1 \in \mathbb{C}^n$$, then $$A(v_1, \cdots, v_n)=(v_1, \cdots, v_n)\begin{pmatrix}\lambda & *\\ & A_0\end{pmatrix}$$.

So $$A$$ is similar to $$A(v_1, \cdots, v_n)=(v_1, \cdots, v_n)\begin{pmatrix}\lambda & *\\ & A_0\end{pmatrix}$$. By induction, we can assume that $$A_0$$ is in form of Jordan norm form. Assume more that $$A_0=\begin{pmatrix}A_1 & \\ & A_2\end{pmatrix}$$. Where $$A_1$$ arranges Jordan block belonging to $$\lambda$$, and $$A_2$$ arranges the others.

Existence: Using the following trick: $$$$\label{eq:1} \begin{pmatrix}1 & & x & \\ &\ddots &&\\ & & 1&\\ &&&\ddots\end{pmatrix}\begin{pmatrix}\lambda &0 & a & * \\ &\ddots &&\\ & & \mu&\\&&&\ddots\end{pmatrix}\begin{pmatrix}1 & & -x & \\ &\ddots &&\\ & & 1&\\ &&&\ddots\end{pmatrix}=\begin{pmatrix}\lambda &0 & a+\mu x-\lambda x & * \\ &\ddots &&\\ & & \mu& * \\&&&\ddots\end{pmatrix}$$$$ to eliminate all the entries over $$A_2$$ in the first row.

Using the following trick: $$$$\label{eq:2} \begin{pmatrix}1 & & x & \\ &\ddots &&\\ & & 1&\\ &&&\ddots\end{pmatrix}\begin{pmatrix}\lambda &0 & a & b \\ &\ddots &&\\ & & \lambda&\\&&&\ddots\end{pmatrix}\begin{pmatrix}1 & & -x & \\ &\ddots &&\\ & & 1&\\ &&&\ddots\end{pmatrix}=\begin{pmatrix}\lambda &0 & a & b+x \\ &\ddots &&\\ & & \mu& 1 \\&&&\ddots\end{pmatrix}$$$$ to eliminate all the entries over $$A_1$$ except the first column of each Jordan block.

Using the following trick: $$$$\label{eq:3} \begin{pmatrix}1 & & & \\ & I & & xI \\ & & \ddots &\\ &&& I \end{pmatrix}\begin{pmatrix}\lambda & ae_1 & 0 & be_1 \\ &J & \Delta &\\ & & J'&\\&&& J\end{pmatrix}\begin{pmatrix}1 & & & \\ &I&&-xI\\ & & \ddots&\\ &&&I\end{pmatrix}=\begin{pmatrix}\lambda & ae_1 & 0 & (b-xa)e_1 \\ &J & \Delta &\\ & & J'&\\&&& J\end{pmatrix}$$$$ to eliminate all the entries at the first column of each Jordan block and the first row except at most one entry. Where $$e_1=(1,0,\cdots,0)$$, $$\begin{pmatrix}J & \Delta \\ & J'\end{pmatrix}$$ is a Jordan block bigger than J.

Last step is $$$$\begin{pmatrix}1/a&\\&1\end{pmatrix} \begin{pmatrix}\lambda/a&\\&\lambda\end{pmatrix}\begin{pmatrix}a&\\&1\end{pmatrix}=\begin{pmatrix}\lambda&1\\&\lambda\end{pmatrix}$$$$ the proof is complete.

So far, I have a question: why can we assume $$A_0$$ is in Jordan normal form?

(original) all matrices in the proof of existence are upper triangular :

That's because the product of two upper triangular matrices is also upper triangular.

$$A = (a_{i,j}) \in \mathcal{M}_n(K)$$ is upper triangular if $$j>i \Rightarrow a_{i,j} = 0$$.

Suppose $$A, B$$ are upper triangular, let $$C = AB$$, then $$C = (c_{i,j})_{1\leqslant i,j \leqslant n}$$ where $$c_{i,j} = \sum_{1\leqslant k \leqslant n} a_{i,k}b_{k,j}$$ Suppose $$j>i$$. Since $$a_{i,k} = 0$$ for $$k>i$$, one gets $$c_{i,j} = \sum_{1\leqslant k \leqslant i} a_{i,k}b_{k,j}$$ But when $$k\leqslant i$$, one has $$b_{k,j} = 0$$.

Hence, $$c_{i,j} = 0$$ for all $$j>i$$ : $$C$$ is upper triangular.

(edit) wlog $$A_0$$ is in Jordan normal form :

Assume $$A(v_1, \cdots, v_n)= \begin{pmatrix}\lambda & *\\ & B\end{pmatrix}$$ for some $$B \in \mathcal{M}_{n - 1}(K)$$.
(edit_2) Here we use the following induction hypothesis :
For every $$k < n$$, every endomorphism of $$\mathbb{C}^k$$ can be put is Jordan normal form.

One should think of $$B$$ as the matrix representing an endomorphism of $$\operatorname{Span}(v_2, \dots, v_n) \cong \mathbb{C}^{n-1}$$. By induction hypothesis, we can find a new basis $$(v'_2,\dots,v'_n)$$ of $$\operatorname{Span}(v_2, \dots, v_n)$$ in which $$B$$ is in Jordan normal form.

Now we have :
1. $$(v_1, v'_2, \dots, v'_n)$$ is a basis of $$\mathbb{C}^n$$.
2. $$A_0 := B(v'_2,\dots,v'_n)$$ is in Jordan normal form.
3. $$A(v_1, v'_2, \cdots, v'_n)=\begin{pmatrix}\lambda & *\\ & A_0\end{pmatrix}$$
NB: $$*$$ is not the same as before, but who cares?

And everything is fine! :-)

• But how can we conclude $A_0$ is upper triangular from the start? – Tengerye Sep 5 '19 at 13:56
• Well my answer is obsolete since you edited your question. You should leave the original question, then add the other question after a markup like Edit – Olivier Roche Sep 5 '19 at 14:00
• As to this second question, you should reformulate it as "why can we assume $A_0$ is in Jordan normal form?". – Olivier Roche Sep 5 '19 at 14:02
• Thank you for your kind suggestion. – Tengerye Sep 5 '19 at 14:22
• Oh, and don't forget to mark the answer if it answers your question(s). ;) – Olivier Roche Sep 5 '19 at 14:56