A Second Course in Linear Algebra

The proof is constructive, as we will explicitly manufacture the basis, and so can be used in practice. As we begin, the basis vectors will not be in the proper order, but we will rearrange them at the end of the proof. For convenience, define \(n_i=\nullity{T^i}\text{,}\) so for example, \(n_0=0\text{,}\) \(n_1=\nullity{T}\) and \(n_p=\nullity{T^p}=\dimension{V}\text{.}\) Define \(s_i=n_i-n_{i-1}\text{,}\) for \(1\leq i\leq p\text{,}\) so we can think of \(s_i\) as “how much bigger” \(\krn{T^i}\) is than \(\krn{T^{i-1}}\text{.}\) In particular, Theorem Theorem 3.2.6 implies that \(s_i\gt 0\) for \(1\leq i\leq p\text{.}\)

We build a set of vectors \(\vect{z}_{i,j}\text{,}\) \(1\leq i\leq p\text{,}\) \(1\leq j\leq s_i\text{.}\) Each \(\vect{z}_{i,j}\) will be an element of \(\krn{T^i}\) and not an element of \(\krn{T^{i-1}}\text{.}\) In total, we will obtain a linearly independent set of \(\sum_{i=1}^{p}s_i=\sum_{i=1}^{p}n_i-n_{i-1}=n_p-n_0=\dimension{V}\) vectors that form a basis of \(V\text{.}\) We construct this set in pieces, starting at the “wrong” end. Our procedure will build a series of subspaces, \(Z_i\text{,}\) each lying in between \(\krn{T^{i-1}}\) and \(\krn{T^i}\text{,}\) having bases \(\vect{z}_{i,j}\text{,}\) \(1\leq j\leq s_i\text{,}\) and which together equal \(V\) as a direct sum. Now would be a good time to review the results on direct sums collected in Section Section 1.2.

We build the subspace \(Z_p\) first (this is what we meant by “starting at the wrong end”). \(\krn{T^{p-1}}\) is a proper subspace of \(\krn{T^p}=V\) (Theorem Theorem 3.2.6). Theorem Theorem 1.2.4 says that there is a subspace of \(V\) that will pair with the subspace \(\krn{T^{p-1}}\) to form a direct sum of \(V\text{.}\) Call this subspace \(Z_p\text{,}\) and choose vectors \(\vect{z}_{p,j}\text{,}\) \(1\leq j\leq s_p\) as a basis of \(Z_p\text{,}\) which we will denote as \(B_p\text{.}\) Note that we have a fair amount of freedom in how to choose these first basis vectors. Several observations will be useful in the next step. First \(V=\krn{T^{p-1}}\ds Z_p\text{.}\) The basis \(B_p=\set{\vect{z}_{p,1},\,\vect{z}_{p,2},\,\vect{z}_{p,3},\,\dots,\,\vect{z}_{p,s_p}}\) is linearly independent. For \(1\leq j\leq s_p\text{,}\) \(\vect{z}_{p,j}\in\krn{T^p}=V\text{.}\) Since the two subspaces of a direct sum have no nonzero vectors in common, for \(1\leq j\leq s_p\text{,}\) \(\vect{z}_{p,j}\not\in\krn{T^{p-1}}\text{.}\) That was comparably easy.

If obtaining \(Z_p\) was easy, getting \(Z_{p-1}\) will be harder. We will repeat the next step \(p-1\) times, and so will do it carefully the first time. Eventually, \(Z_{p-1}\) will have dimension \(s_{p-1}\text{.}\) However, obtaining the first \(s_p\) vectors of a basis for \(Z_{p-1}\) are straightforward. Define \(\vect{z}_{p-1,j}=\lteval{T}{\vect{z}_{p,j}}\text{,}\) \(1\leq j\leq s_p\text{.}\) Notice that we have no choice in creating these vectors, they are a consequence of our choices for \(\vect{z}_{p,j}\text{.}\) In retrospect (i.e. on a second reading of this proof), you will recognize this as the key step in realizing a matrix representation of a nilpotent linear transformation with Jordan blocks. We need to know that this set of vectors is linearly independent. We consider a relation of linear dependence on \(\vect{z}_{p-1,j}\text{,}\) \(1\leq j\leq s_p\text{,}\) and massage it,

Define

The statement just above means that \(\vect{x}\in\krn{T}\subseteq\krn{T^{p-1}}\) (Theorem Theorem 3.2.6). As defined, \(\vect{x}\) is a linear combination of the basis vectors \(B_p\text{,}\) and therefore \(\vect{x}\in Z_p\text{.}\) Thus \(\vect{x}\in\krn{T^{p-1}}\cap Z_p\text{.}\) Because \(V=\krn{T^{p-1}}\ds Z_p\text{,}\) Theorem Theorem 1.2.6 tells us that \(\vect{x}=\zerovector\text{.}\) Now we recognize the definition of \(\vect{x}\) as a relation of linear dependence on the linearly independent set \(B_p\text{,}\) and therefore conclude that \(a_1=a_2=\cdots=a_{s_p}=0\text{.}\) This establishes the linear independence of \(\vect{z}_{p-1,j}\text{,}\) \(1\leq j\leq s_p\text{.}\)

We also need to know where the vectors \(\vect{z}_{p-1,j}\text{,}\) \(1\leq j\leq s_p\) live. First we demonstrate that they are members of \(\krn{T^{p-1}}\text{.}\)

So \(\vect{z}_{p-1,j}\in\krn{T^{p-1}}\text{,}\) \(1\leq j\leq s_p\text{.}\)

Moreover, these vectors are not elements of \(\krn{T^{p-2}}\text{.}\) Suppose to the contrary that \(\vect{z}_{p-1,j}\in\krn{T^{p-2}}\text{.}\) Then

which contradicts the earlier statement that \(\vect{z}_{p,j}\not\in\krn{T^{p-1}}\text{.}\) So \(\vect{z}_{p-1,j}\not\in\krn{T^{p-2}}\text{,}\) \(1\leq j\leq s_p\text{.}\)

Now choose any basis \(C_{p-2}=\set{\vectorlist{u}{n_{p-2}}}\) for \(\krn{T^{p-2}}\text{.}\) We want to extend this basis by adding in the \(\vect{z}_{p-1,j}\) to span a subspace of \(\krn{T^{p-1}}\text{.}\) But first we establish that this set is linearly independent. Let \(a_k\text{,}\) \(1\leq k\leq n_{p-2}\) and \(b_j\text{,}\) \(1\leq j\leq s_p\) be the scalars in a relation of linear dependence,

Then,

Define

The statement just above means that \(\vect{y}\in\krn{T^{p-1}}\text{.}\) As defined, \(\vect{y}\) is a linear combination of the basis vectors \(B_p\text{,}\) and therefore \(\vect{y}\in Z_p\text{.}\) Thus \(\vect{y}\in\krn{T^{p-1}}\cap Z_p\text{.}\) Because \(V=\krn{T^{p-1}}\ds Z_p\text{,}\) Theorem Theorem 1.2.6 tells us that \(\vect{y}=\zerovector\text{.}\) Now we recognize the definition of \(\vect{y}\) as a relation of linear dependence on the linearly independent set \(B_p\text{,}\) and therefore \(b_1=b_2=\cdots=b_{s_p}=0\text{.}\) Return to the full relation of linear dependence with both sets of scalars (the \(a_i\) and \(b_j\)). Now that we know that \(b_j=0\) for \(1\leq j\leq s_p\text{,}\) this relation of linear dependence simplifies to a relation of linear dependence on just the basis \(C_{p-1}\text{.}\) Therefore, \(a_i=0\text{,}\) \(1\leq a_i\leq n_{p-1}\) and we have the desired linear independence.

Define a new subspace of \(\krn{T^{p-1}}\) by

By Theorem Theorem 1.2.4 there exists a subspace of \(\krn{T^{p-1}}\) which will pair with \(Q_{p-1}\) to form a direct sum. Call this subspace \(R_{p-1}\text{,}\) so by definition, \(\krn{T^{p-1}}=Q_{p-1}\ds R_{p-1}\text{.}\) We are interested in the dimension of \(R_{p-1}\text{.}\) Note first, that since the spanning set of \(Q_{p-1}\) is linearly independent, \(\dimension{Q_{p-1}}=n_{p-2}+s_p\text{.}\) Then

Notice that if \(s_{p-1}=s_p\text{,}\) then \(R_{p-1}\) is trivial. Now choose a basis of \(R_{p-1}\text{,}\) and denote these \(s_{p-1}-s_p\) vectors as \(\vect{z}_{p-1,s_p+1}\text{,}\) \(\vect{z}_{p-1,s_p+2}\text{,}\) \(\vect{z}_{p-1,s_p+3}\text{,}\) \dots, \(\vect{z}_{p-1,s_{p-1}}\text{.}\) This is another occassion to notice that we have some freedom in this choice.

We now have \(\krn{T^{p-1}}=Q_{p-1}\ds R_{p-1}\text{,}\) and we have bases for each of the two subspaces. The union of these two bases will therefore be a linearly independent set in \(\krn{T^{p-1}}\) with size

So with the proper size the following set is a basis of \(\krn{T^{p-1}}\text{,}\)

We built up this basis in three parts, we will now split it in half. Define the subspace \(Z_{p-1}\) by

where we have implicitly denoted the basis as \(B_{p-1}\text{.}\) Then Theorem 1.2.3 allows us to split up the basis for \(\krn{T^{p-1}}\) as \(C_{p-1}\cup B_{p-1}\) and write

Whew! This is a good place to recap what we have achieved. The vectors \(\vect{z}_{i,j}\) form bases for the subspaces \(Z_i\) and right now

The key feature of this decomposition of \(V\) is that the first \(s_p\) vectors in the basis for \(Z_{p-1}\) are outputs of the linear transformation \(T\) using the basis vectors of \(Z_p\) as inputs.

Now we want to further decompose \(\krn{T^{p-2}}\text{,}\) into \(\krn{T^{p-3}}\) and \(Z_{p-2}\text{.}\) The procedure is the same as above, so we will only sketch the key steps. Checking the details proceeds in the same manner as above. Technically, we could have set up the preceding as the induction step in a proof by induction (Proof Technique I), but this probably would make the proof harder to understand.

Apply \(T\) to each element of \(B_{p-1}\text{,}\) to create vectors \(\vect{z}_{p-2,j}\text{,}\) \(1\leq j\leq s_{p-1}\text{.}\) These vectors form a linearly independent set, and each is an element of \(\krn{T^{p-2}}\text{,}\) but not an element of \(\krn{T^{p-3}}\text{.}\) Grab a basis \(C_{p-3}\) of \(\krn{T^{p-3}}\) and add on the newly-created vectors \(\vect{z}_{p-2,j}\text{,}\) \(1\leq j\leq s_{p-1}\text{.}\) This expanded set is linearly independent, and we can define a subspace \(Q_{p-2}\) with this set as its basis. Theorem Theorem 1.2.4 gives us a subspace \(R_{p-2}\) such that \(\krn{T^{p-2}}=Q_{p-2}\ds R_{p-2}\text{.}\) Vectors \(\vect{z}_{p-2,j}\text{,}\) \(s_{p-1}+1\leq j\leq s_{p-2}\) are chosen as a basis for \(R_{p-2}\) once the relevant dimensions have been verified. The union of \(C_{p-3}\) and \(\vect{z}_{p-2,j}\text{,}\) \(1\leq j\leq s_{p-2}\) then form a basis of \(\krn{T^{p-2}}\text{,}\) which can be split into two parts to yield the decomposition

Here \(Z_{p-2}\) is the subspace of \(\krn{T^{p-2}}\) with basis \(B_{p-2}=\setparts{\vect{z}_{p-2,j}}{1\leq j\leq s_{p-2}}\text{.}\) Finally,

Again, the key feature of this decomposition is that the first vectors in the basis of \(Z_{p-2}\) are outputs of \(T\) using vectors from the basis \(Z_{p-1}\) as inputs (and in turn, some of these inputs are outputs of \(T\) derived from inputs in \(Z_p\)).

Now assume we repeat this procedure until we decompose \(\krn{T^{2}}\) into subspaces \(\krn{T}\) and \(Z_2\text{.}\) Finally, decompose \(\krn{T}\) into subspaces \(\krn{T^0}=\krn{I_n}=\set{\zerovector}\) and \(Z_1\text{,}\) so that we recognize the vectors \(\vect{z}_{1,j}\text{,}\) \(1\leq j\leq s_1=n_1\) as elements of \(\krn{T}\text{.}\) The set

is linearly independent by Theorem Theorem 1.2.7 and has size

So \(B\) is a basis of \(V\text{.}\)

We desire a matrix representation of \(T\) relative to \(B\text{,}\) but first we will reorder the elements of \(B\text{.}\) The following display lists the elements of \(B\) in the desired order, when read across the rows left-to-right in the usual way. Notice that we established the existence of these vectors column-by-column, and beginning on the right.

It is difficult to layout this table with the notation we have been using, but it would not be especially useful to invent some notation to overcome the difficulty. (One approach would be to define something like the inverse of the nonincreasing function, \(i\rightarrow s_i\text{.}\)) Do notice that there are \(s_1=n_1\) rows, and \(p\) columns. Column \(i\) is the basis \(B_i\text{.}\) The vectors in the first column are elements of \(\krn{T}\text{.}\) Each row is the same length, or shorter, than the one above it. If we apply \(T\) to any vector in the table, other than those in the first column, the output is the preceding vector in the row.

Now contemplate the matrix representation of \(T\) relative to \(B\) as we read across the rows of the table above. In the first row, \(\lteval{T}{\vect{z}_{1,1}}=\zerovector\text{,}\) so the first column of the representation is the zero column. Next, \(\lteval{T}{\vect{z}_{2,1}}=\vect{z}_{1,1}\text{,}\) so the second column of the representation is a vector with a single one in the first entry, and zeros elsewhere. Next, \(\lteval{T}{\vect{z}_{3,1}}=\vect{z}_{2,1}\text{,}\) so column 3 of the representation is a zero, then a one, then all zeros. Continuing in this vein, we obtain the first \(p\) columns of the representation, which is the Jordan block \(\jordan{p}{0}\) followed by rows of zeros.

When we apply \(T\) to the basis vectors of the second row, what happens? Applying \(T\) to the first vector, the result is the zero vector, so the representation gets a zero column. Applying \(T\) to the second vector in the row, the output is simply the first vector in that row, making the next column of the representation all zeros plus a lone one, sitting just above the diagonal. Continuing, we create a Jordan block, sitting on the diagonal of the matrix representation. It is not possible in general to state the size of this block, but since the second row is no longer than the first, it cannot have size larger than \(p\text{.}\)

Since there are as many rows as the dimension of \(\krn{T}\text{,}\) the representation contains as many Jordan blocks as the nullity of \(T\text{,}\) \(\nullity{T}\text{.}\) Each successive block is smaller than the preceding one, with the first, and largest, having size \(p\text{.}\) The blocks are Jordan blocks since the basis vectors \(\vect{z}_{i,j}\) were often defined as the result of applying \(T\) to other elements of the basis already determined, and then we rearranged the basis into an order that placed outputs of \(T\) just before their inputs, excepting the start of each row, which was an element of \(\krn{T}\text{.}\)

Theorem Theorem 3.2.8 tells us that \(\restrict{T}{\geneigenspace{T}{\lambda}}-\lambda I_{\geneigenspace{T}{\lambda}}\) is a nilpotent linear transformation. Theorem Theorem 3.3.1 tells us that a nilpotent linear transformation has a basis for its domain that yields a matrix representation that is block diagonal where the blocks are Jordan blocks of the form \(\jordan{k}{0}\text{.}\) So let \(B\) be a basis of \(\geneigenspace{T}{\lambda}\) that yields such a matrix representation for \(\restrict{T}{\geneigenspace{T}{\lambda}}-\lambda I_{\geneigenspace{T}{\lambda}}\text{.}\)

We can write

Then the matrix representation of \(\lambda I_{\geneigenspace{T}{\lambda}}\) relative to the basis \(B\) is then simply the diagonal matrix \(\lambda I_m\text{,}\) where \(m=\dimension{\geneigenspace{T}{\lambda}}\text{.}\) So we have the rather unwieldy expression,

The first representation in the final experssion has Jordan blocks with zero in every diagonal entry by Theorem Theorem 3.3.1, while the second representation has \(\lambda\) in every diagonal entry of the matrix. The result of adding the two representations is to convert the Jordan blocks from the form \(\jordan{k}{0}\) to the form \(\jordan{k}{\lambda}\text{.}\)

This theorem is really just the consequence of applying to \(T\text{,}\) consecutively, Theorem Theorem 3.1.10, Theorem Theorem 3.3.3 and Theorem Theorem 3.3.1.

Theorem Theorem 3.1.10 gives us a decomposition of \(V\) into generalized eigenspaces, one for each distinct eigenvalue. Since these generalized eigenspaces are invariant relative to \(T\text{,}\) this provides a block diagonal matrix representation where each block is the matrix representation of the restriction of \(T\) to the generalized eigenspace.

Restricting \(T\) to a generalized eigenspace results in a “nearly nilpotent” linear transformation, as stated more precisely in Theorem Theorem 3.2.8. We unravel Theorem Theorem 3.2.8 in the proof of Theorem Theorem 3.3.3 so that we can apply Theorem Theorem 3.3.1 about representations of nilpotent linear transformation.

We know the dimension of a generalized eigenspace is the algebraic multiplicity of the eigenvalue (Corollary Corollary 3.1.11), so the blocks associated with the generalized eigenspaces are square with a size equal to the algebraic multiplicity. In refining the basis for a block associatred with a single eigenvalue, and producing Jordan blocks, the results of Theorem Theorem 3.3.1 apply. The total number of blocks will be the nullity of \(\restrict{T}{\geneigenspace{T}{\lambda}}-\lambda I_{\geneigenspace{T}{\lambda}}\text{,}\) which is the geometric multiplicity of \(\lambda\) as an eigenvalue of \(T\) (Definition GME). The largest of the Jordan blocks will have size equal to the index of the nilpotent linear transformation \(\restrict{T}{\geneigenspace{T}{\lambda}}-\lambda I_{\geneigenspace{T}{\lambda}}\text{,}\) which is exactly the definition of the index of the eigenvalue \(\lambda\) (Definition Definition 3.2.9).