# Linear Algebra/Strings

*This subsection is optional, and requires material from the optional Direct Sum subsection.*

The prior subsection shows that as increases, the dimensions of the 's fall while the dimensions of the 's rise, in such a way that this rank and nullity split the dimension of . Can we say more; do the two split a basis— is ?

The answer is yes for the smallest power since . The answer is also yes at the other extreme.

- Lemma 2.1

Where is a linear transformation, the space is the direct sum . That is, both and .

- Proof

We will verify the second sentence, which is equivalent to the first. The first clause, that the dimension of the domain of equals the rank of plus the nullity of , holds for any transformation and so we need only verify the second clause.

Assume that , to prove that is . Because is in the nullspace, . On the other hand, because , the map is a dimension-preserving homomorphism and therefore is one-to-one. A composition of one-to-one maps is one-to-one, and so is one-to-one. But now— because only is sent by a one-to-one linear map to — the fact that implies that .

- Note 2.2

Technically we should distinguish the map from the map because the domains or codomains might differ. The second one is said to be the **restriction**^{[1]} of to . We shall use later a point from that proof about the restriction map, namely that it is nonsingular.

In contrast to the and cases, for intermediate powers the space might not be the direct sum of and . The next example shows that the two can have a nontrivial intersection.

- Example 2.3

Consider the transformation of defined by this action on the elements of the standard basis.

The vector

is in both the rangespace and nullspace. Another way to depict this map's action is with a **string**.

- Example 2.4

A map whose action on is given by the string

has equal to the span , has , and has . The matrix representation is all zeros except for some subdiagonal ones.

- Example 2.5

Transformations can act via more than one string. A transformation acting on a basis by

is represented by a matrix that is all zeros except for blocks of subdiagonal ones

(the lines just visually organize the blocks).

In those three examples all vectors are eventually transformed to zero.

- Definition 2.6

A **nilpotent** transformation is one with a power that is the zero map. A **nilpotent matrix** is one with a power that is the zero matrix. In either case, the least such power is the **index of nilpotency**.

- Example 2.7

In Example 2.3 the index of nilpotency is two. In Example 2.4 it is four. In Example 2.5 it is three.

- Example 2.8

The differentiation map is nilpotent of index three since the third derivative of any quadratic polynomial is zero. This map's action is described by the string and taking the basis gives this representation.

Not all nilpotent matrices are all zeros except for blocks of subdiagonal ones.

- Example 2.9

With the matrix from Example 2.4, and this four-vector basis

a change of basis operation produces this representation with respect to .

The new matrix is nilpotent; it's fourth power is the zero matrix since

and is the zero matrix.

The goal of this subsection is Theorem 2.13, which shows that the prior example is prototypical in that every nilpotent matrix is similar to one that is all zeros except for blocks of subdiagonal ones.

- Definition 2.10

Let be a nilpotent transformation on . A **-string generated by** is a sequence . This sequence has **length** . A **-string basis** is a basis that is a concatenation of -strings.

- Example 2.11

In Example 2.5, the -strings and , of length three and two, can be concatenated to make a basis for the domain of .

- Lemma 2.12

If a space has a -string basis then the longest string in it has length equal to the index of nilpotency of .

- Proof

Suppose not. Those strings cannot be longer; if the index is then sends any vector— including those starting the string— to . So suppose instead that there is a transformation of index on some space, such that the space has a -string basis where all of the strings are shorter than length . Because has index , there is a vector such that . Represent as a linear combination of basis elements and apply . We are supposing that sends each basis element to but that it does not send to . That is impossible.

We shall show that every nilpotent map has an associated string basis. Then our goal theorem, that every nilpotent matrix is similar to one that is all zeros except for blocks of subdiagonal ones, is immediate, as in Example 2.5.

Looking for a counterexample, a nilpotent map without an associated string basis that is disjoint, will suggest the idea for the proof. Consider the map with this action.

Even after omitting the zero vector, these three strings aren't disjoint, but that doesn't end hope of finding a -string basis. It only means that will not do for the string basis.

To find a basis that will do, we first find the number and lengths of its strings. Since 's index of nilpotency is two, Lemma 2.12 says that at least one string in the basis has length two. Thus the map must act on a string basis in one of these two ways.

Now, the key point. A transformation with the left-hand action has a nullspace of dimension three since that's how many basis vectors are sent to zero. A transformation with the right-hand action has a nullspace of dimension four. Using the matrix representation above, calculation of 's nullspace

shows that it is three-dimensional, meaning that we want the left-hand action.

To produce a string basis, first pick and from

(other choices are possible, just be sure that is linearly independent). For pick a vector from that is not in the span of .

Finally, take and such that and .

Now, with respect to , the matrix of is as desired.

- Theorem 2.13

Any nilpotent transformation is associated with a -string basis. While the basis is not unique, the number and the length of the strings is determined by .

This illustrates the proof. Basis vectors are categorized into kind , kind , and kind . They are also shown as squares or circles, according to whether they are in the nullspace or not.

- Proof

Fix a vector space ; we will argue by induction on the index of nilpotency of . If that index is then is the zero map and any basis is a string basis , ..., . For the inductive step, assume that the theorem holds for any transformation with an index of nilpotency between and and consider the index case.

First observe that the restriction to the rangespace is also nilpotent, of index . Apply the inductive hypothesis to get a string basis for , where the number and length of the strings is determined by .

(In the illustration these are the basis vectors of kind , so there are strings shown with this kind of basis vector.)

Second, note that taking the final nonzero vector in each string gives a basis for . (These are illustrated with 's in squares.) For, a member of is mapped to zero if and only if it is a linear combination of those basis vectors that are mapped to zero. Extend to a basis for all of .

(The 's are the vectors of kind so that is the set of squares.) While many choices are possible for the 's, their number is determined by the map as it is the dimension of minus the dimension of .

Finally, is a basis for because any sum of something in the rangespace with something in the nullspace can be represented using elements of for the rangespace part and elements of for the part from the nullspace. Note that

and so can be extended to a basis for all of by the addition of more vectors. Specifically, remember that each of is in , and extend with vectors such that . (In the illustration, these are the 's.) The check that linear independence is preserved by this extension is Problem 13.

- Corollary 2.14

Every nilpotent matrix is similar to a matrix that is all zeros except for blocks of subdiagonal ones. That is, every nilpotent map is represented with respect to some basis by such a matrix.

This form is unique in the sense that if a nilpotent matrix is similar to two such matrices then those two simply have their blocks ordered differently. Thus this is a canonical form for the similarity classes of nilpotent matrices provided that we order the blocks, say, from longest to shortest.

- Example 2.15

The matrix

has an index of nilpotency of two, as this calculation shows.

The calculation also describes how a map represented by must act on any string basis. With one map application the nullspace has dimension one and so one vector of the basis is sent to zero. On a second application, the nullspace has dimension two and so the other basis vector is sent to zero. Thus, the action of the map is and the canonical form of the matrix is this.

We can exhibit such a -string basis and the change of basis matrices witnessing the matrix similarity. For the basis, take to represent with respect to the standard bases, pick a and also pick a so that .

(If we take to be a representative with respect to some nonstandard bases then this picking step is just more messy.) Recall the similarity diagram.

The canonical form equals , where

and the verification of the matrix calculation is routine.

- Example 2.16

The matrix

is nilpotent. These calculations show the nullspaces growing.

That table shows that any string basis must satisfy: the nullspace after one map application has dimension two so two basis vectors are sent directly to zero, the nullspace after the second application has dimension four so two additional basis vectors are sent to zero by the second iteration, and the nullspace after three applications is of dimension five so the final basis vector is sent to zero in three hops.

To produce such a basis, first pick two independent vectors from

then add such that and

and finish by adding ) such that .

## Exercises

edit*This exercise is recommended for all readers.*

- Problem 1

What is the index of nilpotency of the **left-shift** operator,
here acting on the space of triples of reals?

*This exercise is recommended for all readers.*

- Problem 2

For each string basis state the index of nilpotency and give the dimension of the rangespace and nullspace of each iteration of the nilpotent map.

Also give the canonical form of the matrix.

- Problem 3

Decide which of these matrices are nilpotent.

*This exercise is recommended for all readers.*

- Problem 4

Find the canonical form of this matrix.

*This exercise is recommended for all readers.*

- Problem 5

Consider the matrix from Example 2.16.

- Use the action of the map on the string basis to give the canonical form.
- Find the change of basis matrices that bring the matrix to canonical form.
- Use the answer in the prior item to check the answer in the first item.

*This exercise is recommended for all readers.*

- Problem 6

Each of these matrices is nilpotent.

Put each in canonical form.

- Problem 7

Describe the effect of left or right multiplication by a matrix that is in the canonical form for nilpotent matrices.

- Problem 8

Is nilpotence invariant under similarity? That is, must a matrix similar to a nilpotent matrix also be nilpotent? If so, with the same index?

*This exercise is recommended for all readers.*

- Problem 9

Show that the only eigenvalue of a nilpotent matrix is zero.

- Problem 10

Is there a nilpotent transformation of index three on a two-dimensional space?

- Problem 11

In the proof of Theorem 2.13, why isn't the proof's base case that the index of nilpotency is zero?

*This exercise is recommended for all readers.*

- Problem 12

Let be a linear transformation and suppose is such that but . Consider the -string .

- Prove that is a transformation on the span of the set
of vectors in the string,
that is, prove that restricted to the span has a range
that is a subset of the span.
We say that the span is a
**-invariant**subspace. - Prove that the restriction is nilpotent.
- Prove that the -string is linearly independent and so is a basis for its span.
- Represent the restriction map with respect to the -string basis.

- Problem 13

Finish the proof of Theorem 2.13.

- Problem 14

Show that the terms "nilpotent transformation" and "nilpotent matrix", as given in Definition 2.6, fit with each other: a map is nilpotent if and only if it is represented by a nilpotent matrix. (Is it that a transformation is nilpotent if an only if there is a basis such that the map's representation with respect to that basis is a nilpotent matrix, or that any representation is a nilpotent matrix?)

- Problem 15

Let be nilpotent of index four. How big can the rangespace of be?

- Problem 16

Recall that similar matrices have the same eigenvalues. Show that the converse does not hold.

- Problem 17

Prove a nilpotent matrix is similar to one that is all zeros except for blocks of super-diagonal ones.

*This exercise is recommended for all readers.*

- Problem 18

Prove that if a transformation has the same rangespace as nullspace. then the dimension of its domain is even.

- Problem 19

Prove that if two nilpotent matrices commute then their product and sum are also nilpotent.

- Problem 20

Consider the transformation of given by where is an matrix. Prove that if is nilpotent then so is .

- Problem 21

Show that if is nilpotent then is invertible. Is that "only if" also?

## References

edit- ↑ More information on map restrictions is in the appendix.