Search for probability and statistics terms on Statlect
StatLect
Index > Matrix algebra

Cyclic subspace

by , PhD

In linear algebra, cycles are strings of linearly independent vectors obtained by applying increasing powers of an operator to a single vector; cyclic subspaces are the subspaces spanned by cycles.

In this lecture we focus on the cycles and cyclic subspaces obtained by applying nilpotent operators.

Table of Contents

Nilpotent operator

Let $S$ be a vector space.

Remember that a linear operator $f:S ightarrow S$ is said to be nilpotent of index k if and only if[eq1]for any $sin S $and [eq2]for at least one vector $sin S$.

Clearly,[eq3]and[eq4] where $QTR{rm}{null}$ denotes the null space of an operator and $subset $ denotes strict inclusion.

Definition

Here is a formal definition of cycle.

Definition Let $S$ be a vector space and $f:S ightarrow S$ a nilpotent linear operator. Let $sin S$ be a non-zero vector. Let $l$ be the largest non-negative integer such that [eq5]. Then, the set[eq6]is called the cycle generated by $s$. The vector $s$ is called the initial vector of the cycle. The subspace spanned by the cycle, that is,[eq7]is called the cyclic subspace generated by $s$.

Note that [eq8] and the cycle has $l$ elements. The number of elements of the cycle is called the length of the cycle.

Also note that the assumption that $f$ is nilpotent guarantees that $l$ exists (because $l$ can at most be equal to the index k of $f$). As a consequence, cycles are well-defined.

In what follows, we call a cycle obtained from a nilpotent operator $f$ an $f $-cycle if we want to emphasize the specific operator $f$ that was used to obtain the cycle.

It suffices to find one zero vector

How do we find the largest integer such that [eq9]?

In other words, how do we determine the length of a cycle?

The answer is simple: we start from $s$ and we compute increasingly larger powers: $fleft( s ight) $, [eq10], .... The first time that we get a zero vector, we stop. In fact, if [eq11]then[eq12]for any integer $jgeq 0$.

In other words, once we encounter the first zero vector, then we know that it will be followed by all zero vectors. This also implies that a cycle contains no zero vectors (proved formally in the next section).

We could also change the definition and say that the length of the cycle $l$ is the smallest non-negative integer such that [eq13].

Example Let $S$ be the space of $3 imes 1$ vectors. Consider the nilpotent mapping defined by [eq14]where [eq15]The mapping is nilpotent because[eq16]Consider the vector [eq17]Then, we have[eq18]Thus, the cycle of length $2$ generated by $s_{1}$ is[eq19]Now, consider another vector [eq20]Then, we have[eq21]Thus, the cycle of length $3$ generated by $s_{2}$ is[eq22]

All the vectors of a cycle are non-zero

As an exercise, we recommend trying to rigorously prove the following simple result (before reading the proof).

Proposition All the vectors of a cycle are non-zero.

Proof

The proof is by contradiction. Suppose that [eq23] for $jleq l$ (where $l$ is the length of the cycle). Then,[eq24]since any linear operator maps the zero vector into itself. This contradicts the assumption that the cycle has length $l$ (hence [eq25]).

Cycles are linearly independent sets

The first important result concerns the linear independence of cycles.

Proposition Let $S$ be a vector space, $f:S ightarrow S$ a nilpotent linear operator, $sin S$ a non-zero vector and $Cleft( s ight) $ a cycle of length $l$ generated by $s$. Then, $Cleft( s ight) $ is a linearly independent set.

Proof

Since the length of the cycle is $l$, then [eq26] and[eq27]for any integer $jgeq 0$. Suppose that there exist scalars [eq28] such that[eq29]By applying $f^{l-1}$ to both sides of the equation, we obtain [eq30]which implies $a_{0}=0$ (since [eq31]). Thus, the equation becomes[eq32]By applying $f^{l-2}$ to both sides of the equation, we obtain[eq33]which implies $a_{1}=0$. Hence, the equation becomes[eq34]We proceed in this way until we have demonstrated that [eq35] which proves that [eq36]is a linearly independent set.

Cycle tableaux

When working with multiple cycles together, it is often convenient to use so-called cycle tableaux.

Suppose that we have three different vectors $s_{1}$, $s_{2}$ and $s_{3}$, which generate three cycles [eq37]having lengths $4$, $2$ and 1 respectively.

A linear combination involving all the vectors of the three cycles is[eq38]where the first subscript of the coefficients is used to index the three different cycles and the second one is used to index the powers of the nilpotent operator.

A cycle tableau is a table that contains all the summands of the linear combination[eq39]where each cycle is written on a different row, always starting from the leftmost column.

When we apply $f^{j}$ to all the elements of the tableau, all the elements in the first $j$ columns on the left become equal to zero.

For example, if we apply $f$ to the elements of the tableau, we get [eq40]

But, by the definition of length of a cycle (see also the proof in the previous section), we have [eq41]

Thus, the tableau becomes[eq42]or, simply,[eq43]

If we instead apply $f^{2}$ to the original tableau, we get[eq44]

Unions of cycles

Another useful result about linear independence follows.

Proposition Let $S$ be a vector space and $f:S ightarrow S$ a nilpotent linear operator. Let [eq45] be non-zero vectors, generating the cycles [eq46] of lengths [eq47]. If the set[eq48]is linearly independent, then also the set[eq49]is linearly independent.

Proof

Suppose that there exist scalars $a_{mu lambda }$ ($mu =1,ldots ,m$ and [eq50]) such that[eq51]Note that the linear combination in (1) includes all the vectors of the set $C$. Arrange all the summands of the linear combination in a cycle tableau. Suppose that there are $l$ columns in the tableau (which implies that the length of the longest chain is equal to $l$). Then, we apply $f^{l-1}$ to equation (1) and all the elements of the tableau, so that we are left with a single non-zero column. By the assumed linear independence, all the scalars in that column must be equal to zero and that column can be dropped from the original tableau. Thus, we have a new tableau with $l-1$ columns (the rightmost one has been dropped). Then, we iteratively apply [eq52]. At each iteration, we obtain that some coefficients of the linear combination are zero and we can drop another column. In the end, we obtain that all the coefficients of the linear combination are zero, which implies that the set $C$ is linearly independent.

The iterations outlined in the proof are fully shown in the next example.

Example Let us continue with the same example shown in the section above on cycle tableaux. We need to show that [eq53]implies that all the coefficients of the linear combination are equal to zero, provided that [eq54], [eq55] and [eq56] are linearly independent. The starting tableau is[eq57]The length of the longest cycle is $l=4$. So, to start with, we apply $f^{l-1}=f^{3}$ to all the summands. As a result, we obtain[eq58]or[eq59]which implies that $a_{1,0}=0$ (because [eq60]). Thus, we can drop the last column and the tableau becomes[eq61]We now apply $f^{l-2}=f^{2}$ to all the summands. As a result, we obtain[eq62]or[eq63]which implies that $a_{1,1}=0$. We can drop another column:[eq64]By applying $f^{l-3}=f^{1}$, we get[eq65]which implies $a_{1,2}=a_{2,0}=0$ by the assumed linear independence. The final tableau is[eq66]We leave it unchanged (or, which is the same, we apply the identity operator $f^{l-4}=f^{0}$). Thus,[eq67]which implies [eq68] by the assumed linear independence. This is the final step and it proves that the union of the cycles is a linearly independent set.

Non-overlapping unions

When the union of two or more cycles forms a linearly independent set, we call it a non-overlapping union of cycles.

Definition Let $S$ be a vector space and $f:S ightarrow S$ a nilpotent linear operator. Let [eq69] be non-zero vectors, generating the cycles [eq70]. The set[eq71]is called a non-overlapping union of cycles if and only if it is linearly independent.

The next proposition is the key reason why the theory of cycles is so important.

Proposition Let $S$ be a finite-dimensional vector space and $f:S ightarrow S$ a nilpotent linear operator. Then, there exists a non-overlapping union of $f$-cycles that is a basis for $S$.

Proof

The proof is by induction on the dimension of $S$, which is equal to the number of elements of any one of its bases. For [eq72], $f$ is the zero mapping (as proved in the lecture on nilpotent matrices). Thus, we can choose any non-zero $sin S$, and $s$ is both a basis for $S$ and a cycle of length one (because [eq73]), which trivially constitutes a union of non-overlapping cycles. Now, suppose that the proposition holds for all the spaces of dimension $n-1$ or less. Let us consider a space $S$ such that [eq74]. There are two possible cases: 1) $QTR{rm}{null}f=S$; 2) [eq75]. In case 1) $f$ is the zero operator (which maps every vector to zero) and any basis $B$ of $S$ is a non-overlapping union of cycles because [eq76] for any $sin S$, so that any $bin B$ constitutes a cycle by itself. In case 2), the restriction of $f$ to $QTR{rm}{range}f$ is a nilpotent operator (remember that ranges are invariant; thus, the restriction [eq77] is indeed an operator). Moreover, [eq78] because a nilpotent operator cannot have full rank. As a consequence, there is a non-overlapping union of [eq79]-cycles that spans $QTR{rm}{range}f$. Suppose that the union is[eq80]where [eq81]. By the definition of $QTR{rm}{range}f$, there exist vectors [eq82] such that[eq83]We can use the vectors [eq84] to lengthen the cycles and define a new union of cycles [eq85]which is non-overlapping by the previous proposition on the linear independence of unions of cycles. Suppose that the lengths of the cycles [eq86] are [eq87]. The vectors [eq88]are linearly independent and belong to $QTR{rm}{null}f$ (being the final vectors in their respective cycles). If they do not form a basis for $QTR{rm}{null}f$, we can find linearly independent vectors[eq89]belonging to $QTR{rm}{null}f$ that complete the basis. Moreover, [eq90] for [eq91]. As a consequence, the newly found vectors form, by themselves, cycles of length 1. They are also linearly independent from the final vectors of the cycles found previously. Therefore,[eq92]is a union of non-overlapping cycles. The number of vectors belonging to $C$ is[eq93]by the rank-nullity theorem. Therefore, $C$ contains [eq94] linearly independent vectors belonging to $S$. As a consequence, $C$ is a basis for $S$.

Minimal polynomials and matrix indices again

Now that we know about cycles, we can further hone our understanding of minimal polynomials.

Remember that the minimal polynomial of a nilpotent matrix A of index k is[eq95]where k is the nilpotency index of the matrix, as well as the smallest power after which the null spaces of the powers of A stop growing.

We can now provide another characterization.

Proposition Let $S$ be the space of Kx1 vectors. Let A be a $K imes K$ nilpotent matrix of index k. Then, k is the length of the longest cycle generated by the nilpotent operator defined by A.

Proof

Since $A^{k}=0$, no cycle can be longer than k. However, there must be at least one cycle of length k. To prove it, suppose to the contrary that all cycles have length less than k. Then, it must be that $A^{k-1}s=0$ for any $s$. But this implies that A cannot be nilpotent of index k.

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

Let $S$ be a vector space and $f:S ightarrow S$ a nilpotent linear operator.

Suppose that four different vectors $s_{1}$, $s_{2}$, $s_{3}$ and $s_{4}$ generate four cycles [eq96]having lengths $4$, $2$, $2$ and 1 respectively.

Consider a linear combination of all the vectors belonging to the four cycles (where the coefficient of a generic summand [eq97] is $a_{mu .lambda }$).

Use the cycle tableau to represent the linear combination. What happens to the tableau when we apply $f$ to the linear combination?

Solution

A linear combination involving all the vectors of the four cycles is[eq98]Written in a cycle tableau, the combination is[eq99]By applying $f$ to all the elements of the tableau, we get [eq100]By considering the length of the various cycles represented in the tableau, we obtain [eq101]Hence, the tableau becomes[eq102]or, by pruning the zero column,[eq103]

Exercise 2

Let $S$ be the space of $3 imes 1$ vectors. Consider the nilpotent mapping defined by [eq104]where [eq105]Find the length of the cycle generated by[eq106]

Solution

The first vector of the cycle is $s$ itself. The second vector is[eq107]The third vector is[eq108]The next one is[eq109]Therefore, the length of the cycle is $3$.

How to cite

Please cite as:

Taboga, Marco (2021). "Cyclic subspace", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/cyclic-subspace.

The books

Most of the learning materials found on this website are now available in a traditional textbook format.

Featured pages
Explore
Main sections
About
Glossary entries
Share
  • To enhance your privacy,
  • we removed the social buttons,
  • but don't forget to share.