7.5: Upper Triangular Matrices
( \newcommand{\kernel}{\mathrm{null}\,}\)
As before, let V be a complex vector space.
Let T∈L(V,V) and (v1,…,vn) be a basis for V. Recall that we can associate a matrix M(T) ∈Cn×n to the operator T. By Theorem 7.4.1, we know that T has at least one eigenvalue, say λ∈C. Let v1≠0 be an eigenvector corresponding to λ. By the Basis Extension Theorem, we can extend the list (v1) to a basis of V. Since Tv1=λv1, the first column of M(T) with respect to this basis is
[λ0⋮0].
What we will show next is that we can find a basis of Vsuch that the matrix M(T) is upper triangular.
Definition 7.5.1: Upper Trianglar Matrix
A matrix A=(aij)∈Fn×n is called upper triangular if aij=0 for i>j.
Schematically, an upper triangular matrix has the form
[∗∗⋱0∗],
where the entries ∗ can be anything and every entry below the main diagonal is zero.
Here are two reasons why having an operator T represented by an upper triangular matrix can be quite convenient:
- the eigenvalues are on the diagonal (as we will see later);
- it is easy to solve the corresponding system of linear equations by back substitution (as discussed in Section A.3).
The next proposition tells us what upper triangularity means in terms of linear operators and invariant subspaces.
Proposition 7.5.2
Suppose T∈L(V,V) and that (v1,…,vn) is a basis of V. Then the following statements are equivalent:
- the matrix M(T) with respect to the basis (v1,…,vn) is upper triangular;
- Tvk∈span(v1,…,vk) for each k=1,2,…,n;
- span(v1,…,vk) is invariant under T for each k=1,2,…,n.
Proof
The equivalence of Condition~1 and Condition~2 follows easily from the definition since Condition~2 implies that the matrix elements below the diagonal are zero.
Obviously, Condition~3 implies Condition~2. To show that Condition~2 implies Condition~3, note that any vector v∈span(v1,…,vk) can be written as v=a1v1+⋯+akvk. Applying T, we obtain
Tv=a1Tv1+⋯+akTvk∈span(v1,…,vk)
since, by Condition~2, each Tvj∈span(v1,…,vj)⊂span(v1,…,vk) for j=1,2,…,k and since the span is a subspace of V.
◻
The next theorem shows that complex vector spaces indeed have some basis for which the matrix of a given operator is upper triangular.
Theorem 7.5.3
Let V be a finite-dimensional vector space over C and T∈L(V,V). Then there exists a basis B for V such that M(T) is upper triangular with respect to B.
Proof
We proceed by induction on dim(V). If dim(V)=1, then there is nothing to prove.
Hence, assume that dim(V)=n>1and that we have proven the result of the theorem for all T∈L(W,W), where W is a complex vector space with dim(W)≤n−1. By Theorem7.4.1, T has at least one eigenvalue λ.
Define
U=range(T−λI),
and note that
- dim(U)<dim(V)=nsince λis an eigenvalue of T and hence T−λI is not surjective;
- U is an invariant subspace of Tsince, for all u∈U, we have
Tu=(T−λI)u+λu,
which implies that Tu∈U since (T−λI)u∈range(T−λI)=U and λu∈U.
Therefore, we may consider the operator S=T|U, which is the operator obtained by restricting T to the subspace U. By the induction hypothesis, there exists a basis (u1,…,um) of U with m≤n−1 such that M(S) is upper triangular with respect to (u1,…,um). This means that
Tuj=Suj∈span(u1,…,uj),for all j=1,2,…,m.
Extend this to a basis (u1,…,um,v1,…,vk)of V. Then
Tvj=(T−λI)vj+λvj,for all j=1,2,…,k.
Since (T−λI)vj∈range(T−λI)=U=span(u1,…,um), we have that
Tvj∈span(u1,…,um,v1,…,vj),for all j=1,2,…,k.
Hence, T is upper triangular with respect to the basis (u1,…,um,v1,…,vk).
◻
The following are two very important facts about upper triangular matrices and their associated operators.
Proposition 7.5.4
Suppose T∈L(V,V) is a linear operator and that M(T) is upper triangular with respect to some basis of V.
- T is invertible if and only if all entries on the diagonal of M(T) are nonzero.
- The eigenvalues of T are precisely the diagonal elements of M(T).
Proof of Proposition 7.5.4, Part 1
Let (v1,…,vn)be a basis of V such that
M(T)=[λ1∗⋱0λn]
is upper triangular. The claim is that T is invertible if and only if λk≠0 for all k=1,2,…,n. Equivalently, this can be reformulated as follows: T is not invertible if and only if λk=0 for at least one k∈{1,2,…,n}.
Suppose λk=0. We will show that this implies the non-invertibility of T. If k=1, this is obvious since then Tv1=0, which implies that v1∈null(T) so that T is not injective and hence not invertible. So assume that k>1. Then
Tvj∈span(v1,…,vk−1), for all j≤k,
since T is upper triangular and λk=0. Hence, we may define S=T|span(v1,…,vk) to be the restriction of T to the subspace span(v1,…,vk) so that
S:span(v1,…,vk)→span(v1,…,vk−1).
The linear map S is not injective since the dimension of the domain is larger than the dimension of its codomain, i.e.,
dim(span(v1,…,vk))=k>k−1=dim(span(v1,…,vk−1)).
Hence, there exists a vector 0≠v∈span(v1,…,vk) such that Sv=Tv=0. This implies that Tis also not injective and therefore also not invertible.
Now suppose that T is not invertible. We need to show that at least one λk=0. The linear map T not being invertible implies that T is not injective. Hence, there exists a vector 0≠v∈V such that Tv=0, and we can write
v=a1v1+⋯+akvk
for some k, where ak≠0. Then
\boldsymbol{\begin{equation}\label{eq:expansion}
0 = Tv = (a_1 Tv_1 + \cdots + a_{k-1} Tv_{k-1}) + a_k Tv_k. \label{7.5.1}
\end{equation}}
Since T is upper triangular with respect to the basis (v1,…,vn), we know that a1Tv1+⋯+ak−1Tvk−1∈span(v1,…,vk−1). Hence, Equation ??? shows that Tvk∈span(v1,…,vk−1), which implies that λk=0.
◻
Proof of Proposition 7.5.4, Part 2.
Recall that λ∈F is an eigenvalue of T if and only if the operator T−λI is not invertible. Let (v1,…,vn) be a basis such that M(T) is upper triangular. Then
M(T−λI)=[λ1−λ∗⋱0λn−λ].
Hence, by Proposition 7.5.4(1), T−λI is not invertible if and only if λ=λk for some k.
◻
Contributors
- Isaiah Lankham, Mathematics Department at UC Davis
- Bruno Nachtergaele, Mathematics Department at UC Davis
- Anne Schilling, Mathematics Department at UC Davis
Both hardbound and softbound versions of this textbook are available online at WorldScientific.com.