# Proof for Upper triangular Matrix of a linear transformation without an Induction hypothesis

Axler's Linear Algebra Done Right which says that if T is a linear operator on a complex finite dimensional vector space V, then there exists a basis B for V such that the matrix of T with respect to the basis B is upper triangular.

I want to prove the theorem without the induction hypothesis . But, i am a little confused how to go about it. The book probably uses the fact that every invariant subspace has at least one eigenvector, i don't understand the importance and basis of this assumption.

The proof of this theorem in the book is by induction on the dimension of V. For dim V=1 the result clearly holds, so suppose that the result holds for vector spaces of dimension less than V. Let λ be an eigenvalue of T, which we know exists for V is a complex vector space.

Consider U= Im (T−λI). It is not hard to show that Im (T−λI) is an invariant subspace under T of dimension less than V.

So by the induction hypothesis, T|U is an upper triangular matrix. So let u1…un be a basis for U. Extending this to a basis u1…un,v1…vm of V, the proof is complete by noting that for each k such that 1≤k≤m, T(vk)∈ span {u1…un,v1…vk}.

So, how do i prove this without this hypothesis that there already exists a basis with a smaller upper triangular matrix which seems unconvincing? Thank you.

• Hm, what's your motivation to abandon the hypothesys of induction? Oct 7, 2013 at 15:58
• @TZakrevskiy The Proof claims that there already exists a basis (u1, ..., um) with respect to which T|U has an upper triangular matrix. I find induction unconvincing because that's the thing which we actually intend to prove? Oct 7, 2013 at 16:06
• Are you familiar with induction method? For example, when you apply it to find, say $\sum_{j=1}^n j^2$, do you have problems with induction hypothesis? Oct 7, 2013 at 16:09
• yeah, since induction proof uses methods to prove a statement, using the same statement, it makes it a little odd. However, it's just a personal opinion though many books use induction. What do you think? Oct 7, 2013 at 16:29
• I think the understanding how induction works is crucial for learning maths. Without it many proofs become very hard (and, I dare suggest, impossible), because it's one of the rare methods that allows to prove the statements of the sort $\forall n\in\Bbb N\,Predicate(n)$. I'd start with reading the wiki article on induction and then asking your teachers/professors to further explain it. Oct 7, 2013 at 16:35

While I prefer the original proof, here is an attempt by (ab)using the Jordan normal form.

Let $A = S J S^{-1}$ be a Jordan decomposition of $A$. Denote generalized eigenvectors (columns of $S$) as $s_i$ and orthonormalize them in that order, i.e., write them as

$$s_j = \sum_{i=1}^j \xi_{ij} u_i,$$

where $u_1,\dots,u_n$ are orthonormal. Let $U = \begin{bmatrix} u_1 \dots u_n \end{bmatrix}$ be a matrix with columns $u_i$, and let $X = \begin{bmatrix} \xi_{ij} \end{bmatrix}$ be a matrix with elements $\xi_{ij}$ (we define $\xi_{ij} = 0$ for $i > j$, so $X$ is upper triangular). Then

$$S = UX,$$

so

$$A = S J S^{-1} = U X J X^{-1} U^{-1} = U T U^*,$$

where $T = X J X^{-1}$ is upper triangular, because the inverse $X^{-1}$ of an upper triangular matrix is upper triangular, and the product of upper triangular matrices $X$, $J$, and $X^{-1}$ is upper triangular.

• The problem is that proof of existence Jordan decomposition uses induction... Oct 7, 2013 at 16:31
• @TZakrevskiy Of course, there is a question of what is one allowed to just use without proof (assuming we're not trying to prove everything from some system of axioms to the above statement ;-)). Oct 7, 2013 at 16:57
• @TZakrevskiy any inputs? Oct 7, 2013 at 17:12
• @Vish.Math I don't see how is that different from the inductive proof (in Wikipedia article, it's called constructive). Or I misunderstood your comment? Oct 7, 2013 at 17:14
• @VedranŠego edited. this is what i meant. Does this seem different now? " we already know an eigen value and corresponding eigen vector exists . Then, if we extend this vector to get a second linearly independent vector , then the Transformed vector of the second vector must be in the span of the previous two vectors and so on. how do we prove this?" Oct 7, 2013 at 17:24