Linear Algebra/Strings

Linear Algebra Strings Self-Composition Jordan Form 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.1GenRngNullDirSumToSp 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.2note:RestONeToOne Technically we should distinguish the map from the map because the domains or codomains might differ. The second one is said to be the restrictionMore information on map restrictions is in the appendix. 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.3FirstNilMap 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.4NilIndexFourOnCFour 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.5ThirdNilMap 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.6def:nilpotent 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.9ex:NilMatNotCanon 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.10string 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.12le:LongestTowerIsIndex 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. x150px                 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.13th:NilMapHasStrBas 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. x300px 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.14canonical form 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. x150px The canonical form equals , where and the verification of the matrix calculation is routine. Example 2.16ex:FiveByNilStrBas 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 Problem 1exer:IndNilLftShift What is the index of nilpotency of the left-shift operator, here acting on the space of triples of reals? 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. <li> <li> <li> Also give the canonical form of the matrix. Problem 3 Decide which of these matrices are nilpotent. <li> <li> <li> <li> <li> Problem 4 Find the canonical form of this matrix. Problem 5 Consider the matrix from Example 2.16. <li> Use the action of the map on the string basis to give the canonical form. <li> Find the change of basis matrices that bring the matrix to canonical form. <li> Use the answer in the prior item to check the answer in the first item. Problem 6 Each of these matrices is nilpotent. <li> <li> <li> 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? 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? Problem 12invariant Let be a linear transformation and suppose is such that but . Consider the -string . <li> 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. <li> Prove that the restriction is nilpotent. <li> Prove that the -string is linearly independent and so is a basis for its span. <li> Represent the restriction map with respect to the -string basis. Problem 13exer:NilMapWillHaveStrBas Finish the proof of Theorem 2.13. Problem 14exer:MatNilIffMapNil 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. 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? /Solutions/ Linear Algebra Strings Self-Composition Jordan Form References