# Existence of upper triangular matrix proof

I am reading Linear ALgebra Done Right and Thm $$5.27$$ says:

Suppose $$\textsf V$$ is a finite-dimensional complex vector space. Then a square matrix $$\textsf T$$ has an upper-triangular matrix with respect to some basis of $$\textsf V$$.

The proof given is based on induction and I am not getting much of a feel for it. Is there another proof of this theorem, I cant find any? Hopefully more intuitive.

My understanding so far is that suppose $$\textsf T$$,of $$\dim (\textsf{V})$$, has null space as $$\{0\}$$. Then I can select any linearly independent set of vectors and make that my basis. So I choose vectors that satisfy the upper triangular matrix template such as $$(x,0,0,0,0,.....),(y,z,0,0,0....),\dots$$

Any vectors of this form are linearly independent and thus I select this as my basis.(This would imply upper-triangular matrices are not unique).

But what about the case where null space has dimension greater than zero. How is upper-triangular matrix possible here?

• hmmmmm... not all choice of linearly independent vectors will give you an upper triangular form, even if the null space is zero. Commented Jul 6, 2019 at 19:40
• I have edited to make more clear what i meant Commented Jul 6, 2019 at 19:51
• It is still wrong: for your reasoning you may take the canonical basis vectors, but that returns the original matrix! Commented Jul 6, 2019 at 19:54
• It is not that standard basis, it is of form (x,0,0,0,0,.....),(y,z,0,0,0....)(k,l,m,0,0,0....),,....... If it is still wrong please explain Commented Jul 6, 2019 at 19:56
• well, if you take y,k,l,... much smaller than the diagonal elements, you have approximately taken the standard basis, that does not bring your matrix into triangular form. The fact that your basis is in triangular form and that your matrix is in triangular form are NOT linked in any way Commented Jul 6, 2019 at 20:00

Bonus Theorem. If $$k$$ is a field then the following are equivalent: (i) every square matrix over $$k$$ has an eigenvalue (in $$k$$) (ii) every square matrix is similar to an upper-triangular matrix (iii) the characteristic polynomial of every square matrix splits over $$k$$.

Note: As I suspected when I wrote this, (i) is also equivalent to saying $$k$$ is algebraically closed. See here for that.

Anyway, (ii) implies (iii) is trivial, as is (iii) implies (i). For (i) implies (ii): Assume (i).

First note that if $$B=(b_1,\dots,b_n)$$ is a basis then

Lemma 1. The matrix for $$T$$ wrt the basis $$B$$ is upper triangular if and only if $$Tb_k$$ is a linear combination of $$b_1,\dots,b_k$$ for every $$k$$.

So it's enough to prove this:

Lemma 2. There exists a non--zero $$v\in V$$ such that if $$E$$ is the span of $$v$$ then there is a subspace $$W$$ with $$V=E\oplus W$$ and $$TW\subset W$$.

Proof that Lemma 2 implies the result: By induction on the dimension there is a basis $$b_1,\dots,b_{n-1}$$ for $$W$$ such that $$Tb_k$$ is a linear combination of $$b_1,\dots,b_k$$ for $$1\le k\le n-1$$. Let $$b_n=v$$.

Edit: This is seeming easier. At first I was wondering how to get $$v$$ as in Lemma 2. But no, we just concentrate on $$W$$ and then $$v$$ comes along for free. It's clear that Lemma 2 follows from Lemma 3:

Lemma 3. There is a subspace $$W\subset V$$ of codimension $$1$$ such that $$TW\subset W$$.

(Given $$W$$ as in Lemma 3, let $$v$$ be any non-zero element of $$V\setminus W$$ and Lemma 2 follows.)

And Lemma 3 is finally something we can prove:

Let $$\Lambda$$ be an eigenvector of the adjoint $$T^*:V^*\to V^*$$, and let $$W$$ be the kernel of $$\Lambda$$. Then $$W$$ certainly has codimension $$1$$, and if $$x\in W$$ then $$\Lambda(Tx)=(T^*\Lambda)x=\lambda\Lambda x=0;$$hence $$TW\subset W$$.

I don't quite follow your argument assuming that the nullspace is trivial. But if you can do that case you're done:

Since $$T$$ has only finitely many eigenvalues there exists $$\lambda$$ such that $$T-\lambda I$$ is non-singular. So there is a basis making $$T-\lambda I$$ upper triangular; now $$T$$ is upper triangular in the same basis.

But alas it can't be entirely trivial in the non-singular case. Because the result implies that every $$T$$ has an eigenvalue. Since the argument above works in any infinite field, the proof in the non-singular case has to have some step that doesn't work if the scalar field is $$\Bbb Q$$ or $$\Bbb R$$.