The Full Wiki

More info on Linear Algebra/Strings

Linear Algebra/Strings: Wikis

Advertisements

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Wikibooks

Up to date as of January 23, 2010

From Wikibooks, the open-content textbooks collection

< Linear Algebra

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

The prior subsection shows that as j increases, the dimensions of the \mathcal{R}(t^j)'s fall while the dimensions of the \mathcal{N}(t^j)'s rise, in such a way that this rank and nullity split the dimension of V. Can we say more; do the two split a basis— is  V=\mathcal{R}(t^j)\oplus\mathcal{N}(t^j) ?

The answer is yes for the smallest power j = 0 since  V=\mathcal{R}(t^0)\oplus\mathcal{N}(t^0)=V\oplus\{\vec{0}\} . The answer is also yes at the other extreme.

Lemma 2.1

Where  t:V\to V is a linear transformation, the space is the direct sum  V=\mathcal{R}_\infty(t)\oplus\mathcal{N}_\infty(t) . That is, both  \dim(V)=\dim(\mathcal{R}_\infty(t))+\dim(\mathcal{N}_\infty(t)) and  \mathcal{R}_\infty(t)\cap\mathcal{N}_\infty(t)=\{\vec{0}\,\} .

Proof

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

Assume that  \vec{v}\in\mathcal{R}_\infty(t)\cap\mathcal{N}_\infty(t) =\mathcal{R}(t^n)\cap\mathcal{N}(t^n) , to prove that \vec{v} is  \vec{0} . Because  \vec{v} is in the nullspace,  t^n(\vec{v})=\vec{0} . On the other hand, because  \mathcal{R}(t^n)=\mathcal{R}(t^{n+1}) , the map  t:\mathcal{R}_\infty(t)\to \mathcal{R}_\infty(t) is a dimension-preserving homomorphism and therefore is one-to-one. A composition of one-to-one maps is one-to-one, and so  t^n:\mathcal{R}_\infty(t)\to \mathcal{R}_\infty(t) is one-to-one. But now— because only  \vec{0} is sent by a one-to-one linear map to  \vec{0} — the fact that  t^n(\vec{v})=\vec{0} implies that  \vec{v}=\vec{0} .

Note 2.2

Technically we should distinguish the map t:V\to V from the map  t:\mathcal{R}_\infty(t)\to \mathcal{R}_\infty(t) because the domains or codomains might differ. The second one is said to be the restriction[1] of t to \mathcal{R}(t^k). We shall use later a point from that proof about the restriction map, namely that it is nonsingular.

In contrast to the j = 0 and j = n cases, for intermediate powers the space V might not be the direct sum of \mathcal{R}(t^j) and \mathcal{N}(t^j). The next example shows that the two can have a nontrivial intersection.

Example 2.3

Consider the transformation of  \mathbb{C}^2 defined by this action on the elements of the standard basis.

 \begin{pmatrix} 1 \\ 0 \end{pmatrix} \stackrel{n}{\longmapsto} \begin{pmatrix} 0 \\ 1 \end{pmatrix} \quad \begin{pmatrix} 0 \\ 1 \end{pmatrix} \stackrel{n}{\longmapsto} \begin{pmatrix} 0 \\ 0 \end{pmatrix} \qquad N={\rm Rep}_{\mathcal{E}_2,\mathcal{E}_2}(n)=\begin{pmatrix} 0 &0 \ 1 &0 \end{pmatrix}

The vector

 \vec{e}_2=\begin{pmatrix} 0 \\ 1 \end{pmatrix}

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

 \begin{array}{ccccc} \vec{e}_1 &\mapsto &\vec{e}_2 &\mapsto &\vec{0} \end{array}
Example 2.4

A map  \hat{n}:\mathbb{C}^4\to \mathbb{C}^4 whose action on  \mathcal{E}_4 is given by the string

 \begin{array}{ccccccccc} \vec{e}_1 &\mapsto &\vec{e}_2 &\mapsto &\vec{e}_3 &\mapsto &\vec{e}_4 &\mapsto &\vec{0} \end{array}

has  \mathcal{R}(\hat{n})\cap\mathcal{N}(\hat{n}) equal to the span  [\{\vec{e}_4\}] , has  \mathcal{R}(\hat{n}^2)\cap\mathcal{N}(\hat{n}^2)= [\{\vec{e}_3,\vec{e}_4\}] , and has  \mathcal{R}(\hat{n}^3)\cap\mathcal{N}(\hat{n}^3)= [\{\vec{e}_4\}] . The matrix representation is all zeros except for some subdiagonal ones.

 \hat{N}={\rm Rep}_{\mathcal{E}_4,\mathcal{E}_4}(\hat{n}) =\begin{pmatrix} 0 &0 &0 &0 \ 1 &0 &0 &0 \ 0 &1 &0 &0 \ 0 &0 &1 &0 \end{pmatrix}
Example 2.5

Transformations can act via more than one string. A transformation t acting on a basis  B=\langle \vec{\beta}_1,\dots,\vec{\beta}_5 \rangle by

 \begin{array}{ccccccc} \vec{\beta}_1 &\mapsto &\vec{\beta}_2 &\mapsto &\vec{\beta}_3 &\mapsto &\vec{0} \ \vec{\beta}_4 &\mapsto &\vec{\beta}_5 &\mapsto &\vec{0} \end{array}

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

 {\rm Rep}_{B,B}(t)= \left(\begin{array}{ccc|cc} 0 &0 &0 &0 &0 \ 1 &0 &0 &0 &0 \ 0 &1 &0 &0 &0 \\ \hline 0 &0 &0 &0 &0 \ 0 &0 &0 &1 &0 \end{array}\right)

(the lines just visually organize the blocks).

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

Definition 2.6

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

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  d/dx:\mathcal{P}_2\to \mathcal{P}_2 is nilpotent of index three since the third derivative of any quadratic polynomial is zero. This map's action is described by the string x^2\mapsto 2x\mapsto 2\mapsto 0 and taking the basis  B=\langle x^2,2x,2 \rangle gives this representation.

 {\rm Rep}_{B,B}(d/dx)= \begin{pmatrix} 0 &0 &0 \ 1 &0 &0 \ 0 &1 &0 \end{pmatrix}

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

Example 2.9

With the matrix \hat{N} from Example 2.4, and this four-vector basis

 D=\langle \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 2 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 1 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} \rangle

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

 \begin{pmatrix} 1 &0 &1 &0 \ 0 &2 &1 &0 \ 1 &1 &1 &0 \ 0 &0 &0 &1 \end{pmatrix} \begin{pmatrix} 0 &0 &0 &0 \ 1 &0 &0 &0 \ 0 &1 &0 &0 \ 0 &0 &1 &0 \end{pmatrix} \begin{pmatrix} 1 &0 &1 &0 \ 0 &2 &1 &0 \ 1 &1 &1 &0 \ 0 &0 &0 &1 \end{pmatrix}^{-1}\!\! = \begin{pmatrix} -1 &0 &1 &0 \ -3 &-2 &5 &0 \ -2 &-1 &3 &0 \ 2 &1 &-2 &0 \end{pmatrix}

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

 (P\hat{N}P^{-1})^4 =P\hat{N}P^{-1}\cdot P\hat{N}P^{-1}\cdot P\hat{N}P^{-1}\cdot P\hat{N}P^{-1} =P\hat{N}^4P^{-1}

and  \hat{N}^4 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 t be a nilpotent transformation on V. A t-string generated by[Index]  \vec{v}\in V is a sequence  \langle \vec{v},t(\vec{v}),\ldots,t^{k-1}(\vec{v}) \rangle . This sequence has length k. A t-string basis[Index][Index] is a basis that is a concatenation of t-strings.

Example 2.11

In Example 2.5, the t-strings \langle \vec{\beta}_1,\vec{\beta}_2,\vec{\beta}_3 \rangle and \langle \vec{\beta}_4,\vec{\beta}_5 \rangle , of length three and two, can be concatenated to make a basis for the domain of t.

Lemma 2.12

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

Proof

Suppose not. Those strings cannot be longer; if the index is k then tk sends any vector— including those starting the string— to  \vec{0} . So suppose instead that there is a transformation t of index k on some space, such that the space has a t-string basis where all of the strings are shorter than length k. Because t has index k, there is a vector  \vec{v} such that  t^{k-1}(\vec{v})\neq\vec{0} . Represent \vec{v} as a linear combination of basis elements and apply tk − 1. We are supposing that tk − 1 sends each basis element to  \vec{0} but that it does not send  \vec{v} to  \vec{0} . 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  t:\mathbb{C}^5\to \mathbb{C}^5 with this action.

Linalg nilpotent transformation.png                 {\rm Rep}_{\mathcal{E}_5,\mathcal{E}_5}(t)= \begin{pmatrix} 0 &0 &0 &0 &0 \ 0 &0 &0 &0 &0 \ 1 &1 &0 &0 &0 \ 0 &0 &0 &0 &0 \ 0 &0 &0 &1 &0 \end{pmatrix}

Even after ommitting the zero vector, these three strings aren't disjoint, but that doesn't end hope of finding a t-string basis. It only means that  \mathcal{E}_5 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 t'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.

 \begin{array}{ccccc} \vec{\beta}_1 &\mapsto &\vec{\beta}_2 &\mapsto &\vec{0} \ \vec{\beta}_3 &\mapsto &\vec{\beta}_4 &\mapsto &\vec{0} \ \vec{\beta}_5 &\mapsto &\vec{0} \end{array}                
\begin{array}{ccccc} \vec{\beta}_1 &\mapsto &\vec{\beta}_2 &\mapsto &\vec{0} \ \vec{\beta}_3 &\mapsto &\vec{0} \ \vec{\beta}_4 &\mapsto &\vec{0} \ \vec{\beta}_5 &\mapsto &\vec{0} \end{array}

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 t's nullspace

 \mathcal{N}(t)= \{\begin{pmatrix} x \\ -x \\ z \\ 0 \\ r \end{pmatrix}\,\big|\, x,z,r\in\mathbb{C} \}

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

To produce a string basis, first pick  \vec{\beta}_2 and  \vec{\beta}_4 from  \mathcal{R}(t)\cap\mathcal{N}(t)

 \vec{\beta}_2=\begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}\qquad \vec{\beta}_4=\begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}

(other choices are possible, just be sure that  \{\vec{\beta}_2,\vec{\beta}_4\} is linearly independent). For  \vec{\beta}_5 pick a vector from  \mathcal{N}(t) that is not in the span of  \{ \vec{\beta}_2,\vec{\beta}_4 \} .

 \vec{\beta}_5=\begin{pmatrix} 1 \\ -1 \\ 0 \\ 0 \\ 0 \end{pmatrix}

Finally, take  \vec{\beta}_1 and  \vec{\beta}_3 such that  t(\vec{\beta}_1)=\vec{\beta}_2 and  t(\vec{\beta}_3)=\vec{\beta}_4 .

 \vec{\beta}_1=\begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}\qquad \vec{\beta}_3=\begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 0 \end{pmatrix}

Now, with respect to  B=\langle \vec{\beta}_1,\ldots,\vec{\beta}_5 \rangle , the matrix of t is as desired.

 {\rm Rep}_{B,B}(t)= \left(\begin{array}{cc|cc|c} 0 &0 &0 &0 &0 \ 1 &0 &0 &0 &0 \\ \hline 0 &0 &0 &0 &0 \ 0 &0 &1 &0 &0 \\ \hline 0 &0 &0 &0 &0 \end{array}\right)
Theorem 2.13

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

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

Linalg nilpotent has string basis.png
Proof

Fix a vector space V; we will argue by induction on the index of nilpotency of t:V\to V. If that index is 1 then t is the zero map and any basis is a string basis \vec{\beta}_1\mapsto\vec{0}, ..., \vec{\beta}_n\mapsto\vec{0}. For the inductive step, assume that the theorem holds for any transformation with an index of nilpotency between 1 and k − 1 and consider the index k case.

First observe that the restriction to the rangespace  t:\mathcal{R}(t)\to \mathcal{R}(t) is also nilpotent, of index k − 1. Apply the inductive hypothesis to get a string basis for  \mathcal{R}(t) , where the number and length of the strings is determined by t.

 B=\langle \vec{\beta}_1,t(\vec{\beta}_1),\dots, t^{h_1}(\vec{\beta}_1) \rangle \!\mathbin{{}^\frown}\! \langle \vec{\beta}_2,\ldots,t^{h_2}(\vec{\beta}_2) \rangle \!\mathbin{{}^\frown}\!\cdots\!\mathbin{{}^\frown}\! \langle \vec{\beta}_i,\ldots,t^{h_i}(\vec{\beta}_i) \rangle

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

Second, note that taking the final nonzero vector in each string gives a basis  C=\langle t^{h_1}(\vec{\beta}_1),\dots,t^{h_i}(\vec{\beta}_i) \rangle for  \mathcal{R}(t)\cap\mathcal{N}(t) . (These are illustrated with 1's in squares.) For, a member of  \mathcal{R}(t) is mapped to zero if and only if it is a linear combination of those basis vectors that are mapped to zero. Extend C to a basis for all of  \mathcal{N}(t) .

 \hat{C}=C\!\mathbin{{}^\frown}\!\langle \vec{\xi}_1,\dots,\vec{\xi}_p \rangle

(The \vec{\xi}'s are the vectors of kind 2 so that  \hat{C} is the set of squares.) While many choices are possible for the  \vec{\xi} 's, their number p is determined by the map t as it is the dimension of  \mathcal{N}(t) minus the dimension of  \mathcal{R}(t)\cap\mathcal{N}(t) .

Finally,  B\!\mathbin{{}^\frown}\!\hat{C} is a basis for  \mathcal{R}(t)+\mathcal{N}(t) because any sum of something in the rangespace with something in the nullspace can be represented using elements of B for the rangespace part and elements of  \hat{C} for the part from the nullspace. Note that

\begin{array}{rl} \dim\big(\mathcal{R}(t)+\mathcal{N}(t)\big) &= \dim (\mathcal{R}(t))+\dim (\mathcal{N}(t)) -\dim(\mathcal{R}(t)\cap\mathcal{N}(t)) \ &= \mathop{\mbox{rank}} (t)+\text{nullity}\, (t)-i \ &= \dim (V)-i \end{array}

and so  B\!\mathbin{{}^\frown}\!\hat{C} can be extended to a basis for all of V by the addition of i more vectors. Specifically, remember that each of  \vec{\beta}_1,\dots,\vec{\beta}_i is in  \mathcal{R}(t) , and extend  B\!\mathbin{{}^\frown}\!\hat{C} with vectors  \vec{v}_1,\dots,\vec{v}_i such that  t(\vec{v}_1)=\vec{\beta}_1,\dots,t(\vec{v}_i)=\vec{\beta}_i . (In the illustration, these are the 3's.) The check that linear independence is preserved by this extension is Problem 13.

Corollary 2.14

[Index][Index][Index] 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

 M=\begin{pmatrix} 1 &-1 \ 1 &-1 \end{pmatrix}

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

 \begin{array}{c|cc} p & M^p & \mathcal{N}(M^p) \\ \hline 1 & M=\begin{pmatrix} 1 &-1 \ 1 &-1 \end{pmatrix} & \{\begin{pmatrix} x \\ x \end{pmatrix}\,\big|\, x\in\mathbb{C}\} \ 2 & M^2=\begin{pmatrix} 0 &0 \ 0 &0 \end{pmatrix} & \mathbb{C}^2 \end{array}

The calculation also describes how a map m represented by M 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 \vec{\beta}_1\mapsto\vec{\beta}_2\mapsto\vec{0} and the canonical form of the matrix is this.

 \begin{pmatrix} 0 &0 \ 1 &0 \end{pmatrix}

We can exhibit such a m-string basis and the change of basis matrices witnessing the matrix similarity. For the basis, take M to represent m with respect to the standard bases, pick a  \vec{\beta}_2\in\mathcal{N}(m) and also pick a  \vec{\beta}_1 so that  m(\vec{\beta}_1)=\vec{\beta}_2 .

 \vec{\beta}_2=\begin{pmatrix} 1 \\ 1 \end{pmatrix} \qquad \vec{\beta}_1=\begin{pmatrix} 1 \\ 0 \end{pmatrix}

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

Linalg similarity cd 1.png

The canonical form equals RepB,B(m) = PMP − 1, where

 P^{-1} ={\rm Rep}_{B,\mathcal{E}_2}(\mbox{id}) =\begin{pmatrix} 1 &1 \ 0 &1 \end{pmatrix} \qquad P=(P^{-1})^{-1} =\begin{pmatrix} 1 &-1 \ 0 &1 \end{pmatrix}

and the verification of the matrix calculation is routine.

 \begin{pmatrix} 1 &-1 \ 0 &1 \end{pmatrix} \begin{pmatrix} 1 &-1 \ 1 &-1 \end{pmatrix} \begin{pmatrix} 1 &1 \ 0 &1 \end{pmatrix}= \begin{pmatrix} 0 &0 \ 1 &0 \end{pmatrix}
Example 2.16

The matrix

 \begin{pmatrix} 0 &0 &0 &0 &0 \ 1 &0 &0 &0 &0 \ -1 &1 &1 &-1 &1 \ 0 &1 &0 &0 &0 \ 1 &0 &-1 &1 &-1 \end{pmatrix}

is nilpotent. These calculations show the nullspaces growing.

 \begin{array}{c|cc} p & N^p & \mathcal{N}(N^p) \\ \hline 1 &\begin{pmatrix} 0 &0 &0 &0 &0 \ 1 &0 &0 &0 &0 \ -1 &1 &1 &-1 &1 \ 0 &1 &0 &0 &0 \ 1 &0 &-1 &1 &-1 \end{pmatrix} & \{\begin{pmatrix} 0 \\ 0 \\ u-v \\ u \\ v \end{pmatrix} \,\big|\, u,v\in\mathbb{C}\} \ 2 &\begin{pmatrix} 0 &0 &0 &0 &0 \ 0 &0 &0 &0 &0 \ 1 &0 &0 &0 &0 \ 1 &0 &0 &0 &0 \ 0 &0 &0 &0 &0 \end{pmatrix} & \{\begin{pmatrix} 0 \\ y \\ z \\ u \\ v \end{pmatrix} \,\big|\, y,z,u,v\in\mathbb{C}\} \ 3 &\textit{--zero matrix--} & \mathbb{C}^5 \end{array}

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.

 \begin{array}{ccccccc} \vec{\beta}_1 &\mapsto &\vec{\beta}_2 &\mapsto &\vec{\beta}_3 &\mapsto &\vec{0} \ \vec{\beta}_4 &\mapsto &\vec{\beta}_5 &\mapsto &\vec{0} \end{array}

To produce such a basis, first pick two independent vectors from  \mathcal{N}(n)

 \vec{\beta}_3=\begin{pmatrix} 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{pmatrix} \quad \vec{\beta}_5=\begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix}

then add  \vec{\beta}_2,\vec{\beta}_4\in\mathcal{N}(n^2) such that  n(\vec{\beta}_2)=\vec{\beta}_3 and  n(\vec{\beta}_4)=\vec{\beta}_5

 \vec{\beta}_2=\begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \quad \vec{\beta}_4=\begin{pmatrix} 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix}

and finish by adding  \vec{\beta}_1\in\mathcal{N}(n^3)=\mathbb{C}^5 ) such that  n(\vec{\beta}_1)=\vec{\beta}_2 .

 \vec{\beta}_1=\begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}

Exercises

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?

 (x,y,z)\mapsto(0,x,y)
Answer

Three. It is at least three because \ell^2(\,(1,1,1)\,)=(0,0,1)\neq \vec{0}. It is at most three because (x,y,z)\mapsto (0,x,y)\mapsto (0,0,x)\mapsto (0,0,0).

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.

  1.  \begin{array}{ccccccc} \vec{\beta}_1 &\mapsto &\vec{\beta}_2 &\mapsto &\vec{0} \ \vec{\beta}_3 &\mapsto &\vec{\beta}_4 &\mapsto &\vec{0} \end{array}
  2.  \begin{array}{ccccccc} \vec{\beta}_1 &\mapsto &\vec{\beta}_2 &\mapsto &\vec{\beta}_3 &\mapsto &\vec{0} \ \vec{\beta}_4 &\mapsto &\vec{0} \ \vec{\beta}_5 &\mapsto &\vec{0} \ \vec{\beta}_6 &\mapsto &\vec{0} \end{array}
  3.  \begin{array}{ccccccccc} \vec{\beta}_1 &\mapsto &\vec{\beta}_2 &\mapsto &\vec{\beta}_3 &\mapsto &\vec{0} \end{array}

Also give the canonical form of the matrix.

Answer
  1. The domain has dimension four. The map's action is that any vector in the space c_1\cdot \vec{\beta}_1+c_2\cdot \vec{\beta}_2 +c_3\cdot \vec{\beta}_3+c_4\cdot \vec{\beta}_4 is sent to c_1\cdot \vec{\beta}_2+c_2\cdot \vec{0} +c_3\cdot \vec{\beta}_4+c_4\cdot \vec{0} =c_1\cdot \vec{\beta}_3+c_3\cdot\vec{\beta}_4. The first application of the map sends two basis vectors \vec{\beta}_2 and \vec{\beta}_4 to zero, and therefore the nullspace has dimension two and the rangespace has dimension two. With a second application, all four basis vectors are sent to zero and so the nullspace of the second power has dimension four while the rangespace of the second power has dimension zero. Thus the index of nilpotency is two. This is the canonical form.
     \begin{pmatrix} 0 &0 &0 &0 \ 1 &0 &0 &0 \ 0 &0 &0 &0 \ 0 &0 &1 &0 \end{pmatrix}
  2. The dimension of the domain of this map is six. For the first power the dimension of the nullspace is four and the dimension of the rangespace is two. For the second power the dimension of the nullspace is five and the dimension of the rangespace is one. Then the third iteration results in a nullspace of dimension six and a rangespace of dimension zero. The index of nilpotency is three, and this is the canonical form.
     \begin{pmatrix} 0 &0 &0 &0 &0 &0 \ 1 &0 &0 &0 &0 &0 \ 0 &1 &0 &0 &0 &0 \ 0 &0 &0 &0 &0 &0 \ 0 &0 &0 &0 &0 &0 \ 0 &0 &0 &0 &0 &0 \end{pmatrix}
  3. The dimension of the domain is three, and the index of nilpotency is three. The first power's null space has dimension one and its range space has dimension two. The second power's null space has dimension two and its range space has dimension one. Finally, the third power's null space has dimension three and its range space has dimension zero. Here is the canonical form matrix.
     \begin{pmatrix} 0 &0 &0 \ 1 &0 &0 \ 0 &1 &0 \end{pmatrix}
Problem 3

Decide which of these matrices are nilpotent.

  1. \begin{pmatrix} -2 &4 \ -1 &2 \end{pmatrix}
  2. \begin{pmatrix} 3 &1 \ 1 &3 \end{pmatrix}
  3. \begin{pmatrix} -3 &2 &1 \ -3 &2 &1 \ -3 &2 &1 \end{pmatrix}
  4. \begin{pmatrix} 1 &1 &4 \ 3 &0 &-1 \ 5 &2 &7 \end{pmatrix}
  5. \begin{pmatrix} 45 &-22 &-19 \ 33 &-16 &-14 \ 69 &-34 &-29 \end{pmatrix}
Answer

By Lemma 1.3 the nullity has grown as large as possible by the n-th iteration where n is the dimension of the domain. Thus, for the 2 \! \times \! 2 matrices, we need only check whether the square is the zero matrix. For the 3 \! \times \! 3 matrices, we need only check the cube.

  1. Yes, this matrix is nilpotent because its square is the zero matrix.
  2. No, the square is not the zero matrix.
     \begin{pmatrix} 3 &1 \ 1 &3 \end{pmatrix}^2 =\begin{pmatrix} 10 &6 \ 6 &10 \end{pmatrix}
  3. Yes, the cube is the zero matrix. In fact, the square is zero.
  4. No, the third power is not the zero matrix.
     \begin{pmatrix} 1 &1 &4 \ 3 &0 &-1 \ 5 &2 &7 \end{pmatrix}^3 =\begin{pmatrix} 206 &86 &304 \ 26 &8 &26 \ 438 &180 &634 \end{pmatrix}
  5. Yes, the cube of this matrix is the zero matrix.

Another way to see that the second and fourth matrices are not nilpotent is to note that they are nonsingular.

This exercise is recommended for all readers.
Problem 4

Find the canonical form of this matrix.

 \begin{pmatrix} 0 &1 &1 &0 &1 \ 0 &0 &1 &1 &1 \ 0 &0 &0 &0 &0 \ 0 &0 &0 &0 &0 \ 0 &0 &0 &0 &0 \end{pmatrix}
Answer

The table os calculations

 \begin{array}{c|cc} p & N^p & \mathcal{N}(N^p) \\ \hline 1 &\begin{pmatrix} 0 &1 &1 &0 &1 \ 0 &0 &1 &1 &1 \ 0 &0 &0 &0 &0 \ 0 &0 &0 &0 &0 \ 0 &0 &0 &0 &0 \end{pmatrix} & \{\begin{pmatrix} r \\ u \\ -u-v \\ u \\ v \end{pmatrix} \,\big|\, r,u,v\in\mathbb{C}\} \ 2 &\begin{pmatrix} 0 &0 &1 &1 &1 \ 0 &0 &0 &0 &0 \ 0 &0 &0 &0 &0 \ 0 &0 &0 &0 &0 \ 0 &0 &0 &0 &0 \end{pmatrix} & \{\begin{pmatrix} r \\ s \\ -u-v \\ u \\ v \end{pmatrix} \,\big|\, r,s,u,v\in\mathbb{C}\} \ 2 &\textit{--zero matrix--} & \mathbb{C}^5 \end{array}

gives these requirements of the string basis: three basis vectors are sent directly to zero, one more basis vector is sent to zero by a second application, and the final basis vector is sent to zero by a third application. Thus, the string basis has this form.

 \begin{array}{ccccccc} \vec{\beta}_1 &\mapsto &\vec{\beta}_2 &\mapsto &\vec{\beta}_3 &\mapsto &\vec{0} \ \vec{\beta}_4 &\mapsto &\vec{0} \ \vec{\beta}_5 &\mapsto &\vec{0} \end{array}

From that the canonical form is immediate.

 \begin{pmatrix} 0 &0 &0 &0 &0 \ 1 &0 &0 &0 &0 \ 0 &1 &0 &0 &0 \ 0 &0 &0 &0 &0 \ 0 &0 &0 &0 &0 \end{pmatrix}
This exercise is recommended for all readers.
Problem 5

Consider the matrix from Example 2.16.

  1. Use the action of the map on the string basis to give the canonical form.
  2. Find the change of basis matrices that bring the matrix to canonical form.
  3. Use the answer in the prior item to check the answer in the first item.
Answer
  1. The canonical form has a 3 \! \times \! 3 block and a 2 \! \times \! 2 block
     \left(\begin{array}{ccc|cc} 0 &0 &0 &0 &0 \ 1 &0 &0 &0 &0 \ 0 &1 &0 &0 &0 \\ \hline 0 &0 &0 &0 &0 \ 0 &0 &0 &1 &0 \ \end{array}\right)
    corresponding to the length three string and the length two string in the basis.
  2. Assume that N is the representation of the underlying map with respect to the standard basis. Let B be the basis to which we will change. By the similarity diagram
    Linalg similarity cd 2.png
    we have that the canonical form matrix is PNP − 1 where
     P^{-1} ={\rm Rep}_{B,\mathcal{E}_5}(\mbox{id}) =\begin{pmatrix} 1 &0 &0 &0 &0 \ 0 &1 &0 &1 &0 \ 1 &0 &1 &0 &0 \ 0 &0 &1 &1 &1 \ 0 &0 &0 &0 &1 \end{pmatrix}
    and P is the inverse of that.
     P={\rm Rep}_{\mathcal{E}_5,B}(\mbox{id}) =(P^{-1})^{-1} =\begin{pmatrix} 1 &0 &0 &0 &0 \ -1 &1 &1 &-1&1 \ -1 &0 &1 &0 &0 \ 1 &0 &-1&1 &-1\ 0 &0 &0 &0 &1 \end{pmatrix}
  3. The calculation to check this is routine.
This exercise is recommended for all readers.
Problem 6

Each of these matrices is nilpotent.

  1.  \begin{pmatrix} 1/2 &-1/2 \ 1/2 &-1/2 \end{pmatrix}
  2.  \begin{pmatrix} 0 &0 &0 \ 0 &-1 &1 \ 0 &-1 &1 \end{pmatrix}
  3.  \begin{pmatrix} -1 &1 &-1 \ 1 &0 &1 \ 1 &-1 &1 \end{pmatrix}

Put each in canonical form.

Answer
  1. The calculation
     \begin{array}{c|cc} p & N^p & \mathcal{N}(N^p) \\ \hline 1 &\begin{pmatrix} 1/2 &-1/2 \ 1/2 &-1/2 \end{pmatrix} & \{\begin{pmatrix} u \\ u \end{pmatrix} \,\big|\, u\in\mathbb{C}\} \ 2 &\textit{--zero matrix--} & \mathbb{C}^2 \end{array}

    shows that any map represented by the matrix must act on the string basis in this way

     \begin{array}{ccccccc} \vec{\beta}_1 &\mapsto &\vec{\beta}_2 &\mapsto &\vec{0} \end{array}

    because the nullspace after one application has dimension one and exactly one basis vector, \vec{\beta}_2, is sent to zero. Therefore, this representation with respect to \langle \vec{\beta}_1,\vec{\beta}_2 \rangle is the canonical form.

     \begin{pmatrix} 0 &0 \ 1 &0 \end{pmatrix}
  2. The calculation here is similar to the prior one.
     \begin{array}{c|cc} p & N^p & \mathcal{N}(N^p) \\ \hline 1 &\begin{pmatrix} 0 &0 &0 \ 0 &-1 &1 \ 0 &-1 &1 \end{pmatrix} & \{\begin{pmatrix} u \\ v \\ v \end{pmatrix} \,\big|\, u,v\in\mathbb{C}\} \ 2 &\textit{--zero matrix--} & \mathbb{C}^3 \end{array}

    The table shows that the string basis is of the form

     \begin{array}{ccccccc} \vec{\beta}_1 &\mapsto &\vec{\beta}_2 &\mapsto &\vec{0} \ \vec{\beta}_3 &\mapsto &\vec{0} \end{array}

    because the nullspace after one application of the map has dimension two— \vec{\beta}_2 and \vec{\beta}_3 are both sent to zero— and one more iteration results in the additional vector being brought to zero.

  3. The calculation
     \begin{array}{c|cc} p & N^p & \mathcal{N}(N^p) \\ \hline 1 &\begin{pmatrix} -1 &1 &-1 \ 1 &0 &1 \ 1 &-1 &1 \end{pmatrix} & \{\begin{pmatrix} u \\ 0 \\ -u \end{pmatrix} \,\big|\, u\in\mathbb{C}\} \ 2 &\begin{pmatrix} 1 &0 &1 \ 0 &0 &0 \ -1 &0 &-1 \end{pmatrix} & \{\begin{pmatrix} u \\ v \\ -u \end{pmatrix} \,\big|\, u,v\in\mathbb{C}\} \ 3 &\textit{--zero matrix--} & \mathbb{C}^3 \end{array}

    shows that any map represented by this basis must act on a string basis in this way.

     \begin{array}{ccccccc} \vec{\beta}_1 &\mapsto &\vec{\beta}_2 &\mapsto &\vec{\beta}_3 &\mapsto &\vec{0} \end{array}

    Therefore, this is the canonical form.

     \begin{pmatrix} 0 &0 &0 \ 1 &0 &0 \ 0 &1 &0 \end{pmatrix}
Problem 7

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

Answer

A couple of examples

 \begin{pmatrix} 0 &0 \ 1 &0 \end{pmatrix} \begin{pmatrix} a &b \ c &d \end{pmatrix} = \begin{pmatrix} 0 &0 \ a &b \end{pmatrix} \qquad \begin{pmatrix} 0 &0 &0 \ 1 &0 &0 \ 0 &1 &0 \end{pmatrix} \begin{pmatrix} a &b &c \ d &e &f \ g &h &i \end{pmatrix} = \begin{pmatrix} 0 &0 &0 \ a &b &c \ d &e &f \end{pmatrix}

suggest that left multiplication by a block of subdiagonal ones shifts the rows of a matrix downward. Distinct blocks

 \begin{pmatrix} 0 &0 &0 &0 \ 1 &0 &0 &0 \ 0 &0 &0 &0 \ 0 &0 &1 &0 \end{pmatrix} \begin{pmatrix} a &b &c &d \ e &f &g &h \ i &j &k &l \ m &n &o &p \end{pmatrix} = \begin{pmatrix} 0 &0 &0 &0 \ a &b &c &d \ 0 &0 &0 &0 \ i &j &k &l \end{pmatrix}

act to shift down distinct parts of the matrix.

Right multiplication does an analgous thing to columns. See Problem 1.

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?

Answer

Yes. Generalize the last sentence in Example 2.9. As to the index, that same last sentence shows that the index of the new matrix is less than or equal to the index of \hat{N}, and reversing the roles of the two matrices gives inequality in the other direction.

Another answer to this question is to show that a matrix is nilpotent if and only if any associated map is nilpotent, and with the same index. Then, because similar matrices represent the same map, the conclusion follows. This is Exercise 14 below.

This exercise is recommended for all readers.
Problem 9

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

Answer

Observe that a canonical form nilpotent matrix has only zero eigenvalues; e.g., the determinant of this lower-triangular matrix

 \begin{pmatrix} -x &0 &0 \ 1 &-x &0 \ 0 &1 &-x \end{pmatrix}

is ( − x)3, the only root of which is zero. But similar matrices have the same eigenvalues and every nilpotent matrix is similar to one in canonical form.

Another way to see this is to observe that a nilpotent matrix sends all vectors to zero after some number of iterations, but that conflicts with an action on an eigenspace \vec{v}\mapsto \lambda\vec{v} unless λ is zero.

Problem 10

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

Answer

No, by Lemma 1.3 for a map on a two-dimensional space, the nullity has grown as large as possible by the second iteration.

Problem 11

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

Answer

The index of nilpotency of a transformation can be zero only when the vector starting the string must be \vec{0}, that is, only when V is a trivial space.

This exercise is recommended for all readers.
Problem 12

Let  t:V\to V be a linear transformation and suppose  \vec{v}\in V is such that  t^k(\vec{v})=\vec{0} but  t^{k-1}(\vec{v})\neq\vec{0} . Consider the t-string \langle \vec{v},t(\vec{v}),\dots,t^{k-1}(\vec{v}) \rangle .

  1. Prove that t is a transformation on the span of the set of vectors in the string, that is, prove that t restricted to the span has a range that is a subset of the span. We say that the span is a t-invariant subspace.[Index]
  2. Prove that the restriction is nilpotent.
  3. Prove that the t-string is linearly independent and so is a basis for its span.
  4. Represent the restriction map with respect to the t-string basis.
Answer
  1. Any member \vec{w} of the span can be written as a linear combination \vec{w}=c_0\cdot \vec{v}+c_1\cdot t(\vec{v})+\dots +c_{k-1}\cdot t^{k-1}(\vec{v}). But then, by the linearity of the map, t(\vec{w})=c_0\cdot t(\vec{v})+c_1\cdot t^2(\vec{v})+\dots +c_{k-2}\cdot t^{k-1}(\vec{v})+c_{k-1}\cdot \vec{0} is also in the span.
  2. The operation in the prior item, when iterated k times, will result in a linear combination of zeros.
  3. If  \vec{v}=\vec{0} then the set is empty and so is linearly independent by definition. Otherwise write  c_1\vec{v}+\dots+c_{k-1}t^{k-1}(\vec{v})=\vec{0} and apply tk − 1 to both sides. The right side gives  \vec{0} while the left side gives  c_1t^{k-1}(\vec{v}) ; conclude that c1 = 0. Continue in this way by applying tk − 2 to both sides, etc.
  4. Of course, t acts on the span by acting on this basis as a single, k-long, t-string.
     \begin{pmatrix} 0 &0 &0 &0 &\ldots &0 &0 \ 1 &0 &0 &0 &\ldots &0 &0 \ 0 &1 &0 &0 &\ldots &0 &0 \ 0 &0 &1 &0 & &0 &0 \ & & &\ddots \ 0 &0 &0 &0 & &1 &0 \ \end{pmatrix}
Problem 13

Finish the proof of Theorem 2.13.

Answer

We must check that  B\cup\hat{C}\cup\{\vec{v}_1,\dots,\vec{v}_j\} is linearly independent where B is a t-string basis for  \mathcal{R}(t) , where  \hat{C} is a basis for  \mathcal{N}(t) , and where  t(\vec{v}_1)=\vec{\beta}_1,\dots,t(\vec{v}_i=\vec{\beta}_i . Write

 \vec{0}=c_{1,-1}\vec{v}_1+c_{1,0}\vec{\beta}_1 +c_{1,1}t(\vec{\beta}_1)+\dots+ c_{1,{h_1}}t^{h_1}(\vec{\vec{\beta}}_1) +c_{2,-1}\vec{v}_2+\dots+c_{j,h_i}t^{h_i}(\vec{\beta_i})

and apply t.

 \vec{0}=c_{1,-1}\vec{\beta}_1+c_{1,0}t(\vec{\beta}_1) +\dots+ c_{1,h_1-1}t^{h_1}(\vec{\vec{\beta}}_1)+c_{1,h_1}\vec{0} +c_{2,-1}\vec{\beta}_2+\cdots+c_{i,h_i-1}t^{h_i}(\vec{\beta_i}) +c_{i,h_i}\vec{0}

Conclude that the coefficients  c_{1,-1},\dots,c_{1,h_i-1}, c_{2,-1},\dots,c_{i,h_i-1} are all zero as  B\cup\hat{C} is a basis. Substitute back into the first displayed equation to conclude that the remaining coefficients are zero also.

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?)

Answer

For any basis B, a transformation n is nilpotent if and only if N = RepB,B(n) is a nilpotent matrix. This is because only the zero matrix represents the zero map and so nj is the zero map if and only if Nj is the zero matrix.

Problem 15

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

Answer

It can be of any size greater than or equal to one. To have a transformation that is nilpotent of index four, whose cube has rangespace of dimension k, take a vector space, a basis for that space, and a transformation that acts on that basis in this way.

 \begin{array}{ccccccccc} \vec{\beta}_1 &\mapsto &\vec{\beta}_2 &\mapsto &\vec{\beta}_3 &\mapsto &\vec{\beta}_4 &\mapsto &\vec{0} \ \vec{\beta}_5 &\mapsto &\vec{\beta}_6 &\mapsto &\vec{\beta}_7 &\mapsto &\vec{\beta}_8 &\mapsto &\vec{0} \ &\vdots \ \vec{\beta}_{4k-3} &\mapsto &\vec{\beta}_{4k-2} &\mapsto &\vec{\beta}_{4k-1} &\mapsto &\vec{\beta}_{4k} &\mapsto &\vec{0} \ &\vdots \end{array}


--possibly other, shorter, strings--

So the dimension of the rangespace of T3 can be as large as desired. The smallest that it can be is one— there must be at least one string or else the map's index of nilpotency would not be four.

Problem 16

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

Answer

These two have only zero for eigenvalues

 \begin{pmatrix} 0 &0 \ 0 &0 \end{pmatrix} \qquad \begin{pmatrix} 0 &0 \ 1 &0 \end{pmatrix}

but are not similar (they have different canonical representatives, namely, themselves).

Problem 17

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

Answer

A simple reordering of the string basis will do. For instance, a map that is assoicated with this string basis

 \begin{array}{ccccccc} \vec{\beta}_1 &\mapsto &\vec{\beta}_2 &\mapsto &\vec{0} \end{array}

is represented with respect to B=\langle \vec{\beta}_1,\vec{\beta}_2 \rangle by this matrix

 \begin{pmatrix} 0 &0 \ 1 &0 \end{pmatrix}

but is represented with respect to B=\langle \vec{\beta}_2,\vec{\beta}_1 \rangle in this way.

 \begin{pmatrix} 0 &1 \ 0 &0 \end{pmatrix}
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.

Answer

Let t:V\to V be the transformation. If  \mathop{\mbox{rank}} (t)=\text{nullity}\, (t) then the equation  \mathop{\mbox{rank}}(t)+\text{nullity}\,(t)=\dim (V) shows that dim(V) is even.

Problem 19

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

Answer

For the matrices to be nilpotent they must be square. For them to commute they must be the same size. Thus their product and sum are defined.

Call the matrices A and B. To see that AB is nilpotent, multiply (AB)2 = ABAB = AABB = A2B2, and (AB)3 = A3B3, etc., and, as A is nilpotent, that product is eventually zero.

The sum is similar; use the Binomial Theorem.

Problem 20

Consider the transformation of  \mathcal{M}_{n \! \times \! n} given by tS(T) = STTS where S is an  n \! \times \! n matrix. Prove that if S is nilpotent then so is tS.

Answer

Some experimentation gives the idea for the proof. Expansion of the second power

 t^2_S(T)=S(ST-TS)-(ST-TS)S=S^2-2STS+TS^2

the third power

\begin{array}{rl} t^3_S(T) &=S(S^2-2STS+TS^2)-(S^2-2STS+TS^2)S \ &=S^3T-3S^2TS+3STS^2-TS^3 \end{array}

and the fourth power

\begin{array}{rl} t^4_S(T) &=S(S^3T-3S^2TS+3STS^2-TS^3)-(S^3T-3S^2TS+3STS^2-TS^3)S \ &=S^4T-4S^3TS+6S^2TS^2-4STS^3+TS^4 \end{array}

suggest that the expansions follow the Binomial Theorem. Verifying this by induction on the power of tS is routine. This answers the question because, where the index of nilpotency of S is k, in the expansion of t^{2k}_S

 t^{2k}_S(T)=\sum_{0\leq i\leq 2k}(-1)^i\binom{2k}{i} S^iTS^{2k-i}

for any i at least one of the Si and S2ki has a power higher than k, and so the term gives the zero matrix.

Problem 21

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

Answer

Use the geometric series:  I-N^{k+1}=(I-N)(N^k+N^{k-1}+\cdots+I) . If Nk + 1 is the zero matrix then we have a right inverse for IN. It is also a left inverse.

This statement is not "only if" since

 \begin{pmatrix} 1 &0 \ 0 &1 \end{pmatrix} -\begin{pmatrix} -1 &0 \ 0 &-1 \end{pmatrix}

is invertible.

[Index]


 

Advertisements

Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message