# 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? – TZakrevskiy Oct 7 '13 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? – MathMan Oct 7 '13 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? – TZakrevskiy Oct 7 '13 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? – MathMan Oct 7 '13 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. – TZakrevskiy Oct 7 '13 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... – TZakrevskiy Oct 7 '13 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 ;-)). – Vedran Šego Oct 7 '13 at 16:57
• @TZakrevskiy any inputs? – MathMan Oct 7 '13 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? – Vedran Šego Oct 7 '13 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?" – MathMan Oct 7 '13 at 17:24