I was questioned from my friend about a non-proof in a linear algebra textbook.
The author mentions that the following proof of the theorem, that every square matrix in $\Bbb{C}$ is triangularizable, has a gap and thus is invalid:
First, we have two preliminary lemmas.
Lemma 1. Let $I_m$ be the identity matrix of size $m$, $A\in \mathfrak{M}_{m\times m}(\Bbb{C})$, and $U, B \in \mathfrak{M}_{n\times n}(\Bbb{C})$ such that $U$ is invertible. Then $ \bigg(\begin{matrix} I_m & 0 \\ 0 & U^{-1} \end{matrix}\bigg) \bigg( \begin{matrix} A & * \\ 0 & B \end{matrix} \bigg) \bigg( \begin{matrix} I_m & 0 \\ 0 & U \end{matrix} \bigg) = \bigg( \begin{matrix} A & * \\ 0 & U^{-1}BU \end{matrix} \bigg). $
Lemma 2. Let $A \in \mathfrak{M}_{n\times n}(\Bbb{C})$. Then there exists an eigenvalue $\lambda \in \Bbb{C}$ and an invertible matrix $U \in \mathfrak{M}_{n\times n}(\Bbb{C})$ such that $ U^{-1}AU = \bigg( \begin{matrix} \lambda & * \\ 0 & * \end{matrix} \bigg).$
Proof. Let $v_1 \in \Bbb{C}^n$ be a nonzero eigenvector corresponding to $\lambda$. Let $\{v_1, \cdots, v_n\}$ be a basis of $\Bbb{C}^n$ containing $v_1$. Let $U$ be a matrix whose $k$-th column is $v_k$. Then $[AU]_{*1} = A[U]_{*1} = Av_1 = \lambda v_1 = \lambda [U]_{*1}$ and hence $ [U^{-1}AU]_{i1} = [U^{-1}]_{ij}[AU]_{j1} = \lambda [U^{-1}]_{ij}[U]_{j1} = \lambda \delta_{i1},$ which proves Lemma 2.
Now we claim that for each $1 \leq k \leq n$ there exist
- an upper-triangular matrix $T_k$ of size $k$,
- a square matrix $A_{n-k}$ of size $n-k$, and
- an invertible matrix $U_k \in \mathfrak{M}_{n\times n}(\Bbb{C})$
such that
$ U_k^{-1} A U_k = \bigg( \begin{matrix} T_k & * \\ 0 & A_{n-k} \end{matrix} \bigg).$
In particular, for $k = n$ this implies that $A$ is triangularizable.
We prove this claim by induction on $k$. For $k = 1$, this is a trivial consequence of Lemma 2. Now assume this holds for $k < n$. Then applying Lemma 2 to $A_{n-k}$, we obtain some $\tilde{\lambda} \in \Bbb{C}$ and an invertible matrix $\tilde{U}$ of size $n-k$ such that
$ \tilde{U}^{-1}A_{n-k}\tilde{U} = \bigg( \begin{matrix} \tilde{\lambda} & * \\ 0 & A_{n-k-1} \end{matrix} \bigg).$
Now let $U_{k+1}$ as
$U_{k+1} = U_k \bigg( \begin{matrix} I_k & 0 \\ 0 & \tilde{U} \end{matrix} \bigg). $
Then
$\begin{align*} U_{k+1}^{-1} A U_{k+1} &= \bigg( \begin{matrix} I_k & 0 \\ 0 & \tilde{U}^{-1} \end{matrix} \bigg) U_k^{-1} A U_k \bigg( \begin{matrix} I_k & 0 \\ 0 & \tilde{U} \end{matrix} \bigg) = \bigg( \begin{matrix} I_k & 0 \\ 0 & \tilde{U}^{-1} \end{matrix} \bigg) \bigg( \begin{matrix} T_k & * \\ 0 & A_{n-k} \end{matrix} \bigg) \bigg( \begin{matrix} I_k & 0 \\ 0 & \tilde{U} \end{matrix} \bigg) \\ &= \begin{pmatrix} T_k & * \\ 0 & \tilde{U}^{-1}A_{n-k}\tilde{U} \end{pmatrix} = \begin{pmatrix} T_k & * & * \\ 0 & \tilde{\lambda} & * \\ 0 & 0 & A_{n-k-1} \end{pmatrix} =: \begin{pmatrix} T_{k+1} & * \\ 0 & A_{n-k-1} \end{pmatrix}. \end{align*}$
Therefore the claim follows by induction and the proof is complete. Q.E.D.
Actually, I was convinced by this argument and was unable to find any gap in this proof.
The book says that this non-proof overlooked the importance of $L$-invariant subspaces. So I tried this non-proof with some examples of $A$ where the multiplicity of an eigenvalue $\lambda$ is greater than the dimension of the kernel of $A - \lambda I$ in hopes that these trials would reveal the fault in the argument above. But it ended up only finding that the algorithm above works in those cases. I want to know what I am missing.