7.4* The Rational Canonical Form – Linear Algebra, 5th Edition

7.4* The Rational Canonical Form

Until now we have used eigenvalues, eigenvectors, and generalized eigenvectors in our analysis of linear operators with characteristic polynomials that split. In general, characteristic polynomials need not split, and indeed, operators need not have eigenvalues! However, the unique factorization theorem for polynomials (see page 562) guarantees that the characteristic polynomial f(t) of any linear operator T on an n-dimensional vector space factors uniquely as

f ( t ) = ( 1 ) n ( ϕ 1 ( t ) ) n 1 ( ϕ 2 ( t ) ) n 2 ( ϕ k ( t ) ) n k ,

where the ϕi(t)’s (1ik) are distinct irreducible monic polynomials and the ni’s are positive integers. In the case that f(t) splits, each irreducible monic polynomial factor is of the form ϕi(t)=tλi, where λi is an eigenvalue of T, and there is a one-to-one correspondence between eigenvalues of T and the irreducible monic factors of the characteristic polynomial. In general, eigenvalues need not exist, but the irreducible monic factors always exist. In this section, we establish structure theorems based on the irreducible monic factors of the characteristic polynomial instead of eigenvalues.

In this context, the following definition is the appropriate replacement for eigenspace and generalized eigenspace.

Definition.

Let T be a linear operator on a finite-dimensional vector space V with characteristic polynomial

f ( t ) = ( 1 ) n ( ϕ 1 ( t ) ) n 1 ( ϕ 2 ( t ) ) n 2 ( ϕ k ( t ) ) n k ,

where the ϕi(t)’s (1ik) are distinct irreducible monic polynomials and the ni’s are positive integers. For 1ik, we define the subset Kϕi of V by

K ϕ i = { x V :   ( ϕ i ( T ) ) p ( x ) = 0 for some positive integer  p } .

We show that each Kϕi is a nonzero T-invariant subspace of V. Note that if ϕi(t)=tλ is of degree one, then Kϕi is the generalized eigenspace of T corresponding to the eigenvalue λ.

Having obtained suitable generalizations of the related concepts of eigenvalue and eigenspace, our next task is to describe a canonical form of a linear operator suitable to this context. The one that we study is called the rational canonical form. Since a canonical form is a description of a matrix representation of a linear operator, it can be defined by specifying the form of the ordered bases allowed for these representations.

Here the bases of interest naturally arise from the generators of certain cyclic subspaces. For this reason, the reader should recall the definition of a T-cyclic subspace generated by a vector and Theorem 5.21 (p. 314). We briefly review this concept and introduce some new notation and terminology.

Let T be a linear operator on a finite-dimensional vector space V, and let x be a nonzero vector in V. We use the notation Cx for the T-cyclic subspace generated by x. Recall (Theorem 5.21) that if dim(Cx)=k, then the set

{ x ,  T ( x ) ,  T 2 ( x ) ,   ,  T k 1 ( x ) }

is an ordered basis for Cx. To distinguish this basis from all other ordered bases for Cx, we call it the T-cyclic basis generated by x and denote it by βx. Let A be the matrix representation of the restriction of T to Cx in the ordered basis βx. Recall from the proof of Theorem 5.21 that

A = ( 0 0 0 a 0 1 0 0 a 1 0 1 0 a 2 0 0 1 a k 1 ) ,

where

a 0 x + a 1 T ( x ) + + a k 1 T k 1 ( x ) + T k ( x ) = 0.

Furthermore, the characteristic polynomial of A is given by

det ( A t I ) = ( 1 ) k ( a 0 + a 1 t + + a k 1 t k 1 + t k ) .

The matrix A is called the companion matrix of the monic polynomial h(t)=a0+a1t++ak1tk1+tk. Every monic polynomial has a companion matrix, and the characteristic polynomial of the companion matrix of a monic polynomial g(t) of degree k is equal to (1)kg(t). (See Exercise 19 of Section 5.4.) By Theorem 7.15 (p. 512), the monic polynomial h(t) is also the minimal polynomial of A. Since A is the matrix representation of the restriction of T to Cx, h(t) is also the minimal polynomial of this restriction. By Exercise 15 of Section 7.3, h(t) is also the T-annihilator of x.

It is the object of this section to prove that for every linear operator T on a finite-dimensional vector space V, there exists an ordered basis β for V such that the matrix representation [T]β is of the form

( C 1 O O O C 2 O O O C r ) ,

where each Ci is the companion matrix of a polynomial (ϕ(t))m such that ϕ(t) is a monic irreducible divisor of the characteristic polynomial of T and m is a positive integer. A matrix representation of this kind is called a rational canonical form of T. We call the accompanying basis a rational canonical basis for T.

The next theorem is a simple consequence of the following lemma, which relies on the concept of T-annihilator, introduced in the Exercises of Section 7.3.

Lemma.

Let T be a linear operator on a finite-dimensional vector space V, let x be a nonzero vector in V, and suppose that the T-annihilator of x is of the form (ϕ(t))p for some irreducible monic polynomial ϕ(t). Then ϕ(t) divides the minimal polynomial of T, and xKϕ.

Proof.

By Exercise 15(b) of Section 7.3, (ϕ(t))p divides the minimal polynomial of T. Therefore ϕ(t) divides the minimal polynomial of T. Furthermore, xKϕ by the definition of Kϕ.

Theorem 7.17.

Let T be a linear operator on a finite-dimensional vector space V, and let β be an ordered basis for V. Then β is a rational canonical basis for T if and only if β is the disjoint union of T-cyclic bases βvi, where each vi lies in Kϕ for some irreducible monic divisor ϕ(t) of the characteristic polynomial of T.

Proof.

Exercise.

Example 1

Suppose that T is a linear operator on R8 and

β = { v 1 ,   v 2 ,   v 3 ,   v 4 ,   v 5 ,   v 6 ,   v 7 ,   v 8 }

is a rational canonical basis for T such that

is a rational canonical form of T. In this case, the submatrices C1, C2, and C3 are the companion matrices of the polynomials ϕ1(t), (ϕ2(t))2, and ϕ2(t), respectively, where

ϕ 1 ( t ) = t 3 t + 3 and ϕ 2 ( t ) = t 2 + 1.

In the context of Theorem 7.17, β is the disjoint union of the T-cyclic bases; that is,

β = β v 1 β v 3 β v 7 = { v 1 ,   v 2 } { v 3 ,   v 4 ,   v 5 ,   v 6 } { v 7 ,   v 8 } .

By Exercise 39 of Section 5.4, the characteristic polynomial f(t) of T is the product of the characteristic polynomials of the companion matrices:

f ( t ) = ϕ 1 ( t ) ( ϕ 2 ( t ) ) 2 ϕ 2 ( t ) = ϕ 1 ( t ) ( ϕ 2 ( t ) ) 3 .

The rational canonical form C of the operator T in Example 1 is constructed from matrices of the form Ci, each of which is the companion matrix of some power of a monic irreducible divisor of the characteristic polynomial of T. Furthermore, each such divisor is used in this way at least once.

In the course of showing that every linear operator T on a finite dimensional vector space has a rational canonical form C, we show that the companion matrices Ci that constitute C are always constructed from powers of the monic irreducible divisors of the characteristic polynomial of T. A key role in our analysis is played by the subspaces Kϕ, where ϕ(t) is an irreducible monic divisor of the minimal polynomial of T. Since the minimal polynomial of an operator divides the characteristic polynomial of the operator, every irreducible divisor of the former is also an irreducible divisor of the latter. We eventually show that the converse is also true; that is, the minimal polynomial and the characteristic polynomial have the same irreducible divisors.

We begin with a result that lists several properties of irreducible divisors of the minimal polynomial. The reader is advised to review the definition of T-annihilator and the accompanying Exercises 15 of Section 7.3.

Theorem 7.18.

Let T be a linear operator on a finite-dimensional vector space V, and suppose that

p ( t ) = ( ϕ 1 ( t ) ) m 1 ( ϕ 2 ( t ) ) m 2 ( ϕ k ( t ) ) m k

is the minimal polynomial of T, where the ϕi(t)‘s (1ik) are the distinct irreducible monic factors of p(t) and the mi’s are positive integers. Then the following statements are true.

  1. (a) Kϕi is a nonzero T-invariant subspace of V for each i.

  2. (b) If x is a nonzero vector in some Kϕi, then the T-annihilator of x is of the form (ϕi(t))p for some integer p.

  3. (c) Kϕi Kϕj={0} for ij.

  4. (d) Kϕi is invariant under ϕj(T) for ij, and the restriction of ϕj(T) to Kϕi is one-to-one and onto.

  5. (e) Kϕi=N((ϕi(T))mi) for each i.

Proof.

If k=1, then (a), (b), and (e) are obvious, while (c) and (d) are vacuously true. Now suppose that k>1.

  1. (a) The proof that Kϕi is a T-invariant subspace of V is left as an exercise. Let fi(t) be the polynomial obtained from p(t) by omitting the factor (ϕi(t))mi. To prove that Kϕi is nonzero, first observe that fi(t) is a proper divisor of p(t); therefore there exists a vector zV such that x=fi(T)(z)0. Then x Kϕi because

    ( ϕ i ( T ) ) m i ( x ) = ( ϕ i ( T ) ) m i f i ( T ) ( z ) = p ( T ) ( z ) = 0.
  2. (b) Assume the hypothesis. Then (ϕi(T))q(x)=0 for some positive integer q. Hence the T-annihilator of x divides (ϕi(t))q by Exercise 15(b) of Section 7.3, and the result follows.

  3. (c) Assume ij. Let x Kϕi Kϕj, and suppose that x0. By (b), the T-annihilator of x is a power of both ϕi(t) and ϕj(t). But this is impossible because ϕi(t) and ϕj(t) are relatively prime (see Appendix E). We conclude that x=0.

  4. (d) Assume ij. Since Kϕi is T-invariant, it is also ϕj(T)-invariant. Suppose that ϕj(T)(x)=0 for some x Kϕi. Then x Kϕi Kϕj={0} by (c). Therefore the restriction of ϕj(T) to Kϕi is one-to-one. Since V is finite-dimensional, this restriction is also onto.

  5. (e) Suppose that 1ik. Clearly, N((ϕi(T))mi) Kϕi. Let fi(t) be the polynomial defined in (a). Since fi(t) is a product of polynomials of the form ϕj(t) for ji, we have by (d) that the restriction of fi(T) to Kϕi is onto. Let x Kϕi. Then there exists y Kϕi such that fi(T)(y)=x. Therefore

    ( ( ϕ i ( T ) ) m i ) ( x ) = ( ( ϕ i ( T ) ) m i ) f i ( T ) ( y ) = p ( T ) ( y ) = 0 ,

and hence xN((ϕi(T))mi). Thus Kϕi=N((ϕi(T))mi).

Since a rational canonical basis for an operator T is obtained from a union of T-cyclic bases, we need to know when such a union is linearly independent. The next major result, Theorem 7.19, reduces this problem to the study of T-cyclic bases within Kϕ, where ϕ(t) is an irreducible monic divisor of the minimal polynomial of T. We begin with the following lemma.

Lemma.

Let T be a linear operator on a finite-dimensional vector space V, and suppose that

p ( t ) = ( ϕ 1 ( t ) ) m 1 ( ϕ 2 ( t ) ) m 2 ( ϕ k ( t ) ) m k

is the minimal polynomial of T, where the ϕi’s (1ik) are the distinct irreducible monic factors of p(t) and the mi’s are positive integers. For 1ik, let vi Kϕi be such that

v 1 + v 2 + + v k = 0. (2)

Then vi=0 for all i.

Proof.

The result is trivial if k=1, so suppose that k>1. Consider any i. Let fi(t) be the polynomial obtained from p(t) by omitting the factor (ϕi(t))mi. As a consequence of Theorem 7.18, fi(T) is one-to-one on Kϕi, and fi(T)(vj)=0 for ij. Thus, applying fi(T) to (2), we obtain fi(T)(vi)=0, from which it follows that vi=0.

Theorem 7.19.

Let T be a linear operator on a finite-dimensional vector space V, and suppose that

p ( t ) = ( ϕ 1 ( t ) ) m 1 ( ϕ 2 ( t ) ) m 2 ( ϕ k ( t ) ) m k

is the minimal polynomial of T, where the ϕi‘s (1ik) are the distinct irreducible monic factors of p(t) and the mi’s are positive integers. For 1ik, let Si be a linearly independent subset of Kϕi. Then

  1. SiSj= for ij

  2. S 1S 2Sk is linearly independent.

Proof.

If k=1, then (a) is vacuously true and (b) is obvious. Now suppose that k>1. Then (a) follows immediately from Theorem 7.18(c). Furthermore, the proof of (b) is identical to the proof of Theorem 5.5 (p. 261) with the eigenvectors replaced by the generalized eigenvectors.

In view of Theorem 7.19, we can focus on bases of individual spaces of the form Kϕ, where ϕ(t) is an irreducible monic divisor of the minimal polynomial of T. The next several results give us ways to construct bases for these spaces that are unions of T-cyclic bases. These results serve the dual purposes of leading to the existence theorem for the rational canonical form and of providing methods for constructing rational canonical bases.

For Theorems 7.20 and 7.21 and the latter’s corollary, we fix a linear operator T on a finite-dimensional vector space V and an irreducible monic divisor ϕ(t) of the minimal polynomial of T.

Theorem 7.20.

Let v 1, v 2, , vk be distinct vectors in Kϕ such that

S 1 = β v 1 β v 2 β v k

is linearly independent. For each i, suppose there exists wiV such that ϕ(T)(wi)=vi. Then

S 2 = β w 1 β w 2 β w k

is also linearly independent.

Proof.

Consider any linear combination of vectors in S 2 that sums to zero, say,

i = 1 k j = 0 n i a i j T j ( w i ) = 0. (3)

For each i, let fi(t) be the polynomial defined by

f i ( t ) = j = 0 n i a i j t j .

Then (3) can be rewritten as

i = 1 k f i ( T ) ( w i ) = 0. (4)

Apply ϕ(T) to both sides of (4) to obtain

i = 1 k ϕ ( T ) f i ( T ) ( w i ) = i = 1 k f i ( T ) ϕ ( T ) ( w i ) = i = 1 k f i ( T ) ( v i ) = 0.

This last sum can be rewritten as a linear combination of the vectors in S 1 so that each fi(T)(vi) is a linear combination of the vectors in βvi. Since S 1 is linearly independent, it follows that

f i ( T ) ( v i ) = 0 for all  i .

Therefore the T-annihilator of vi divides fi(t) for all i. (See Exercise 15 of Section 7.3.) By Theorem 7.18(b), ϕ(t) divides the T-annihilator of vi, and hence ϕ(t) divides fi(t) for all i. Thus, for each i, there exists a polynomial gi(t) such that fi(t)=gi(t)ϕ(t). So (4) becomes

i = 1 k g i ( T ) ϕ ( T ) ( w i ) = i = 1 k g i ( T ) ( v i ) = 0.

Again, linear independence of S 1 requires that

f i ( T ) ( w i ) = g i ( T ) ( v i ) = 0 for all  i .

But fi(T)(wi) is the result of grouping the terms of the linear combination in (3) that arise from the linearly independent set βwi. We conclude that for each i, aij=0 for all j. Therefore S 2 is linearly independent.

We now show that Kϕ has a basis consisting of a union of T-cycles.

Lemma.

Let W be a T-invariant subspace of Kϕ, and let β be a basis for W. Then the following statements are true.

  1. (a) Suppose that xN(ϕ(T)), but xW. Then ββx is linearly independent.

  2. (b) For some w 1, w 2, , ws in N(ϕ(T)), β can be extended to the linearly independent set

    β = β β w 1 β w 2 β w s ,  

    whose span contains N(ϕ(T)).

Proof.

(a) Let β={v 1, v 2, , vk}, and suppose that

i = 1 k a i v i + z = 0 and z = j = 0 d 1 b j T j ( x ) ,  

where d is the degree of ϕ(t). Then z CxW, and hence Cz CxW. Suppose that z0. Then z has ϕ(t) as its T-annihilator, and therefore

d = dim ( C z ) dim ( C x W ) dim ( C x ) = d .

It follows that CxW= Cx, and consequently xW, contrary to hypothesis. Therefore z=0, from which it follows that bj=0 for all j. Since β is linearly independent, it follows that ai=0 for all i. Thus ββx is linearly independent.

(b) Suppose that W does not contain N(ϕ(T)). Choose a vector w 1N(ϕ(T)) that is not in W. By (a), β 1=ββw1 is linearly independent. Let W 1=span(β 1). If W 1 does not contain N(ϕ(T)), choose a vector w 2 in N(ϕ(T)), but not in W 1, so that β 2=β 1βw2=ββw1βw2 is linearly independent. Continuing this process, we eventually obtain vectors w 1, w 2, , ws in N(ϕ(T)) such that the union

β = β β w 1 β w 2 β w s

is a linearly independent set whose span contains N(ϕ(T)).

Theorem 7.21.

If the minimal polynomial of T is of the form p(t)=(ϕ(t))m, then there exists a rational canonical basis for T.

Proof.

The proof is by mathematical induction on m. Suppose that m=1. Apply (b) of the lemma to W={0} to obtain a linearly independent subset of V of the form βv1βv2βvk, whose span contains N(ϕ(T)). Since V=N(ϕ(T)), this set is a rational canonical basis for V.

Now suppose that, for some integer m>1, the result is valid whenever the minimal polynomial of T is of the form (ϕ(t))k, where k<m, and assume that the minimal polynomial of T is p(t)=(ϕ(t))m. Let r=rank(ϕ(T)). Then R(ϕ(T)) is a T-invariant subspace of V, and the restriction of T to this subspace has (ϕ(t))m1 as its minimal polynomial. Therefore we may apply the induction hypothesis to obtain a rational canonical basis for the restriction of T to R(T). Suppose that v 1, v 2, , vk are the generating vectors of the T-cyclic bases that constitute this rational canonical basis. For each i, choose wi in V such that vi=ϕ(T)(wi). By Theorem 7.20, the union β of the sets βwi is linearly independent. Let W=span(β). Then W contains R(ϕ(T)). Apply (b) of the lemma and adjoin additional T-cyclic bases βwk+1, βwk+2, , βws to β, if necessary, where wi is in N(ϕ(T)) for ik, to obtain a linearly independent set

β = β w 1 β w 2 β w k β w s

whose span W contains both W and N(ϕ(T)).

We show that W=V. Let U denote the restriction of ϕ(T) to W, which is ϕ(T)-invariant. By the way in which W was obtained from R(ϕ(T)), it follows that R(U)=R(ϕ(T)) and N(U)=N(ϕ(T)). Therefore

dim ( W ) = rank ( U ) + nullity ( U ) = rank ( ϕ ( T ) ) + nullity ( ϕ ( T ) ) = dim ( V ) .

Thus W=V, and β is a rational canonical basis for T.

Corollary.

Kϕ has a basis consisting of the union of T-cyclic bases.

Proof.

Apply Theorem 7.21 to the restriction of T to Kϕ.

We are now ready to study the general case.

Theorem 7.22.

Every linear operator on a finite-dimensional vector space has a rational canonical basis and, hence, a rational canonical form.

Proof.

Let T be a linear operator on a finite-dimensional vector space V, and let p(t)=(ϕ1(t))m1(ϕ2(t))m2(ϕk(t))mk be the minimal polynomial of T, where the ϕi(t)’s are the distinct irreducible monic factors of p(t) and mi>0 for all i. The proof is by mathematical induction on k. The case k=1 is proved in Theorem 7.21.

Suppose that the result is valid whenever the minimal polynomial contains fewer than k distinct irreducible factors for some k>1, and suppose that p(t) contains k distinct factors. Let U be the restriction of T to the T-invariant subspace W=R((ϕk(T))mk), and let q(t) be the minimal polynomial of U. Then q(t) divides p(t) by Exercise 10 of Section 7.3. Furthermore, ϕk(t) does not divide q(t). For otherwise, there would exist a nonzero vector xW such that ϕk(U)(x)=0 and a vector yV such that x=(ϕk(T))mk(y). It follows that (ϕk(T))mk+1(y)=0, and hence y Kϕk and x=(ϕk(T))mk(y)=0 by Theorem 7.18(e), a contradiction. Thus q(t) contains fewer than k distinct irreducible divisors. So by the induction hypothesis, U has a rational canonical basis β 1 consisting of a union of U-cyclic bases (and hence T-cyclic bases) of vectors from some of the subspaces Kϕi, 1ik1. By the corollary to Theorem 7.21, Kϕk has a basis β 2 consisting of a union of T-cyclic bases. By Theorem 7.19, β 1 and β 2 are disjoint, and β=β 1β 2 is linearly independent. Let s denote the number of vectors in β.Then

s = dim ( R ( ( ϕ k ( T ) ) m k ) ) + dim ( K ϕ k ) = rank ( ( ϕ k ( T ) ) m k ) + nullity ( ( ϕ k ( T ) ) m k ) = n .

We conclude that β is a basis for V. Therefore β is a rational canonical basis, and T has a rational canonical form.

In our study of the rational canonical form, we relied on the minimal polynomial. We are now able to relate the rational canonical form to the characteristic polynomial.

Theorem 7.23.

Let T be a linear operator on an n-dimensional vector space V with characteristic polynomial

f ( t ) = ( 1 ) n ( ϕ 1 ( t ) ) n 1 ( ϕ 2 ( t ) ) n 2 ( ϕ k ( t ) ) n k ,  

where the ϕi(t)s (1ik) are distinct irreducible monic polynomials and the ni’s are positive integers. Then the following statements are true.

  1. (a) ϕ1(t), ϕ2(t), , ϕk(t) are the irreducible monic factors of the minimal polynomial.

  2. (b) For each i, dim(Kϕi)=dini, where di is the degree of ϕi(t).

  3. (c) If β is a rational canonical basis for T, then βi=βKϕi is a basis for Kϕi for each i.

  4. (d) If γi is a basis for Kϕi for each i, then γ=γ1γ2γk is a basis for V. In particular, if each γi is a disjoint union of T-cyclic bases, then γ is a rational canonical basis for T.

Proof.

(a) By Theorem 7.22, T has a rational canonical form C. By Exercise 39 of Section 5.4, the characteristic polynomial of C, and hence of T, is the product of the characteristic polynomials of the companion matrices that compose C. Therefore each irreducible monic divisor ϕi(t) of f(t) divides the characteristic polynomial of at least one of the companion matrices, and hence for some integer p, (ϕi(t))p is the T-annihilator of a nonzero vector of V. We conclude that (ϕi(t))p, and so ϕi(t), divides the minimal polynomial of T. Conversely, if ϕ(t) is an irreducible monic polynomial that divides the minimal polynomial of T, then ϕ(t) divides the characteristic polynomial of T because the minimal polynomial divides the characteristic polynomial.

(b), (c), and (d) Let C=[T]β, which is a rational canonical form of T. Consider any i i(1ik). Since f(t) is the product of the characteristic polynomials of the companion matrices that compose C, we may multiply those characteristic polynomials that arise from the T-cyclic bases in βi to obtain the factor (ϕi(t))ni of f(t). Since this polynomial has degree nidi, and the union of these bases is a linearly independent subset βi of Kϕi, we have

n i d i dim ( K ϕ i ) .

Furthermore, n=i=1kdini,  because this sum is equal to the degree of f(t).

Now let s denote the number of vectors in γ. By Theorem 7.19, γ is linearly independent, and therefore

n = i = 1 k d i n i i = 1 k dim ( K ϕ i ) = s n .

Hence n=s, and dini=dim(Kϕi) for all i. It follows that γ is a basis for V and βi is a basis for Kϕi for each i.

Uniqueness of the Rational Canonical Form

Having shown that a rational canonical form exists, we are now in a position to ask about the extent to which it is unique. Certainly, the rational canonical form of a linear operator T can be modified by permuting the T-cyclic bases that constitute the corresponding rational canonical basis. This has the effect of permuting the companion matrices that make up the rational canonical form. As in the case of the Jordan canonical form, we show that except for these permutations, the rational canonical form is unique, although the rational canonical bases are not.

To simplify this task, we adopt the convention of ordering every rational canonical basis so that all the T-cyclic bases associated with the same irreducible monic divisor of the characteristic polynomial are grouped together. Furthermore, within each such grouping, we arrange the T-cyclic bases in decreasing order of size. Our task is to show that, subject to this order, the rational canonical form of a linear operator is unique up to the arrangement of the irreducible monic divisors.

As in the case of the Jordan canonical form, we introduce arrays of dots from which we can reconstruct the rational canonical form. For the Jordan canonical form, we devised a dot diagram for each eigenvalue of the given operator. In the case of the rational canonical form, we define a dot diagram for each irreducible monic divisor of the characteristic polynomial of the given operator. A proof that the resulting dot diagrams are completely determined by the operator is also a proof that the rational canonical form is unique.

In what follows, T is a linear operator on a finite-dimensional vector space with rational canonical basis β, ϕ(t) is an irreducible monic divisor of the characteristic polynomial of βv1, βv2, , βvk are the T-cyclic bases of β that are contained in Kϕ; and d is the degree of ϕ(t). For each j, let (ϕ(t))pj be the annihilator of vj. This polynomial has degree dpj; therefore, by Exercise 15 of Section 7.3, βvj contains dpj vectors. Furthermore, p1p2pk since the T-cyclic bases are arranged in decreasing order of size. We define the dot diagram of ϕ(t) to be the array consisting of k columns of dots with pj dots in the jth column, arranged so that the jth column begins at the top and terminates after pj dots. For example, if k=3, p1=4, p2=2, and p3=2, then the dot diagram is

Although each column of a dot diagram corresponds to a T-cyclic basis βvi in Kϕ, there are fewer dots in the column than there are vectors in the basis.

Example 2

Recall the linear operator T of Example 1 with the rational canonical basis β and the rational canonical form C=[T]β. Since there are two irreducible monic divisors of the characteristic polynomial of T, ϕ1(t)=t2t+3 and ϕ2(t)=t2+1, there are two dot diagrams to consider. Because ϕ1(t) is the T-annihilator of v1 and βv1 is a basis for Kϕ1, the dot diagram for ϕ1(t) consists of a single dot. The other two T-cyclic bases, βv3 and βv7, lie in Kϕ2. Since v3 has T-annihilator (ϕ2(t))2 and v7 has T-annihilator ϕ2(t), in the dot diagram of ϕ2(t) we have p1=2 and p2=1. These diagrams are as follows:

In practice, we obtain the rational canonical form of a linear operator from the information provided by dot diagrams. This is illustrated in the next example.

Example 3

Let T be a linear operator on a finite-dimensional vector space over R, and suppose that the irreducible monic divisors of the characteristic polynomial of T are

ϕ 1 ( t ) = t 1 ,   ϕ 2 ( t ) = t 2 + 2 ,   and ϕ 3 ( t ) = t 2 + t + 1.

Suppose, furthermore, that the dot diagrams associated with these divisors are as follows:

Since the dot diagram for ϕ1(t) has two columns, it contributes two companion matrices to the rational canonical form. The first column has two dots, and therefore corresponds to the 2×2 companion matrix of (ϕ1(t))2=(t1)2. The second column, with only one dot, corresponds to the 1×1 companion matrix of ϕ1(t)=t1. These two companion matrices are given by

C 1 = ( 0 1 1 2 ) and C 2 = ( 1 ) .

The dot diagram for ϕ2(t)=t2+2 consists of two columns. each containing a single dot; hence this diagram contributes two copies of the 2×2 companion matrix for ϕ2(t), namely,

C 3 = C 4 = ( 0 2 1 0 ) .

The dot diagram for ϕ 3(t)=t 2+t+1 consists of a single column with a single dot contributing the single 2×2 companion matrix

C 5 = ( 0 1 1 1 ) .

Therefore the rational canonical form of T is the 9×9 matrix

We return to the general problem of finding dot diagrams. As we did before, we fix a linear operator T on a finite-dimensional vector space and an irreducible monic divisor ϕ(t) of the characteristic polynomial of T. Let U denote the restriction of the linear operator ϕ(T) to Kϕ. By Theorem 7.18(d), Uq= T 0 for some positive integer q. Consequently, by Exercise 12 of Section 7.2, the characteristic polynomial of U is (1)mtm, where m=dim( Kϕ). Therefore Kϕ is the generalized eigenspace of U corresponding to λ=0, and U has a Jordan canonical form. The dot diagram associated with the Jordan canonical form of U gives us a key to understanding the dot diagram of T that is associated with ϕ(t). We now relate the two diagrams.

Let β be a rational canonical basis for T, and βv1, βv2, , βvk be the T-cyclic bases of β that are contained in Kϕ. Consider one of these T-cyclic bases βvj, and suppose again that the T-annihilator of vj is (ϕ(t))pj. Then βvj consists of dpj vectors in β. For 0i<d, let γi be the cycle of generalized eigenvectors of U corresponding to λ=0 with end vector Ti(vj), where T 0(vj)=bj. Then

γ i = { ( ϕ ( T ) ) p j 1 T i ( v j ) ,   ( ϕ ( T ) ) p j 2 T i ( v j ) ,   ,   ( ϕ ( T ) ) T i ( v j ) ,   T i ( v j ) } .

By Theorem 7.1 (p. 478), γi is a linearly independent subset of Cvi. Now let

α j = γ 0 γ 1 γ d 1 .

Notice that αj contains dpj vectors.

Lemma 1.

αj is an ordered basis for Cvj.

Proof. The key to this proof is Theorem 7.4 (p. 480). Since αj is the union of cycles of generalized eigenvectors of U corresponding to λ=0, it suffices to show that the set of initial vectors of these cycles

{ ( ϕ ( T ) ) p j 1 ( v j ) ,   ( ϕ ( T ) ) p j 1 T ( v j ) ,   ,   ( ϕ ( T ) ) p j 1 T d 1 ( v j ) }

is linearly independent. Consider any linear combination of these vectors

a 0 ( ϕ ( T ) ) p j 1 ( v j ) + a 1 ( ϕ ( T ) ) p j 1 T ( v j ) + + a d 1 ( ϕ ( T ) ) p j 1 T d 1 ( v j ) ,  

where not all of the coefficients are zero. Let g(t) be the polynomial defined by g(t)=a 0+a 1t++ad1td1. Then g(t) is a nonzero polynomial of degree less than d, and hence (ϕ(t))pj1g(t) is a nonzero polynomial with degree less than dpj. Since (ϕ(t))pj is the T-annihilator of vj, it follows that (ϕ(T))pj1g(T)(vj)0. Therefore the set of initial vectors is linearly independent. So by Theorem 7.4, αj is linearly independent, and the γi’s are disjoint. Consequently, αj consists of dpj linearly independent vectors in Cvj, which has dimension dpj. We conclude that αj is a basis for Cvj.

Thus we may replace βvj by αj as a basis for Cvj. We do this for each j to obtain a subset α=α 1α 2αk of Kϕ.

Lemma 2.

α is a Jordan canonical basis for Kϕ.

Proof. Since βv1βv2βvk is a basis for Kϕ, and since span(αi)=span(βvi)= Cvi, Exercise 9 implies that α is a basis for Kϕ. Because α is a union of cycles of generalized eigenvectors of U, we conclude that α is a Jordan canonical basis.

We are now in a position to relate the dot diagram of T corresponding to ϕ(t) to the dot diagram of U, bearing in mind that in the first case we are considering a rational canonical form and in the second case we are considering a Jordan canonical form. For convenience, we designate the first diagram D 1, and the second diagram D 2. For each j, the presence of the T-cyclic basis βxj results in a column of pj dots in D 1. By Lemma 1, this basis is replaced by the union αj of d cycles of generalized eigenvectors of U, each of length pj, which becomes part of the Jordan canonical basis for U. In effect, αj determines d columns each containing pj dots in D 2. So each column in D 1 determines d columns in D 2 of the same length, and all columns in D 2 are obtained in this way. Alternatively, each row in D 2 has d times as many dots as the corresponding row in D 1. Since Theorem 7.10 (p. 493) gives us the number of dots in any row of D 2, we may divide the appropriate expression in this theorem by d to obtain the number of dots in the corresponding row of D 1. Thus we have the following result.

Theorem 7.24.

Let T be a linear operator on a finite-dimensional vector space V, let ϕ(t) be an irreducible monic divisor of the characteristic polynomial of T of degree d, and let ri denote the number of dots in the ith row of the dot diagram for ϕ(t) with respect to a rational canonical basis for T. Then

  1. (a) r 1= 1d[dim(V)rank(ϕ(T))];

  2. (b) ri= 1d[rank((ϕ(T))i1)rank((ϕ(T))i)] for i>1.

Thus the dot diagrams associated with a rational canonical form of an operator are completely determined by the operator. Since the rational canonical form is completely determined by its dot diagrams, we have the following uniqueness condition.

Corollary.

Under the conventions described earlier, the rational canonical form of a linear operator is unique up to the arrangement of the irreducible monic divisors of the characteristic polynomial.

Since the rational canonical form of a linear operator is unique, the polynomials corresponding to the companion matrices that determine this form are also unique. These polynomials, which are powers of the irreducible monic divisors, are called the elementary divisors of the linear operator. Since a companion matrix may occur more than once in a rational canonical form, the same is true for the elementary divisors. We call the number of such occurrences the multiplicity of the elementary divisor.

Conversely, the elementary divisors and their multiplicities determine the companion matrices and, therefore, the rational canonical form of a linear operator.

Example 4

Let

β = { e x cos   2 x ,   e x sin 2 x ,   x e x cos   2 x ,   x e x sin 2 x }

be viewed as a subset of F(R, R), the space of all real-valued functions defined on R, and let V=span(β). Then V is a four-dimensional subspace of F(R, R), and β is an ordered basis for V. Let D be the linear operator on V defined by D(y)=y , the derivative of y, and let A=[D]β. Then

A = ( 1 2 1 0 2 1 0 1 0 0 1 2 0 0 2 1 ) ,  

and the characteristic polynomial of D, and hence of A, is

f ( t ) = ( t 2 2 t + 5 ) 2 .

Thus ϕ(t)=t 22t+5 is the only irreducible monic divisor of f(t). Since ϕ(t) has degree 2 and V is four-dimensional, the dot diagram for ϕ(t) contains only two dots. Therefore the dot diagram is determined by r 1, the number of dots in the first row. Because ranks are preserved under matrix representations, we can use A in place of D in the formula given in Theorem 7.24. Now

ϕ ( A ) = ( 0 0 0 4 0 0 4 0 0 0 0 0 0 0 0 0 ) ,  

and so

r 1 = 1 2 [ 4 rank ( ϕ ( A ) ) ] = 1 2 [ 4 2 ] = 1.

It follows that the second dot lies in the second row, and the dot diagram is as follows:

Hence V is a D-cyclic space generated by a single function with D-annihilator (ϕ(t)) 2. Furthermore, its rational canonical form is given by the companion matrix of (ϕ(t)) 2=t 44t 3+14t 220t+25, which is

( 0 0 0 25 1 0 0 20 0 1 0 14 0 0 1 4 ) .

Thus (ϕ(t)) 2 is the only elementary divisor of D, and it has multiplicity 1. For the cyclic generator, it suffices to find a function g in V for which ϕ(D)(g)0. Since ϕ(A)(e 3)0, it follows that ϕ(D)(xexcos 2x)0; therefore g(x)=xexcos 2x can be chosen as the cyclic generator. Hence

β g = { x e x cos   2 x ,   D ( x e x cos   2 x ) ,   D 2 ( x e x cos   2 x ) ,   D 3 ( x e x cos   2 x ) }

is a rational canonical basis for D. Notice that the function h defined by h(x)=xexsin2x can be chosen in place of g. This shows that the rational canonical basis is not unique.

It is convenient to refer to the rational canonical form and elementary divisors of a matrix, which are defined in the obvious way.

Definitions.

Let A Mn×n(F). The rational canonical form of A is defined to be the rational canonical form of LA. Likewise, for A, the elementary divisors and their multiplicities are the same as those of LA.

Let A be an n×n matrix, let C be a rational canonical form of A, and let β be the appropriate rational canonical basis for LA. Then C=[LA]β, and therefore A is similar to C. In fact, if Q is the matrix whose columns are the vectors of β in the same order, then Q1AQ=C.

Example 5

For the following real matrix A, we find the rational canonical form C of A and a matrix Q such that Q1AQ=C.

A = ( 0 2 0 6 2 1 2 0 0 2 1 0 1 3 2 1 2 1 1 2 1 4 3 3 4 )

The characteristic polynomial of A is f(t)=(t2+2) 2(t2); therefore ϕ 1(t)=t 2+2 and ϕ 2(t)=t2 are the distinct irreducible monic divisors of f(t). By Theorem 7.23, dim( Kϕ1)=4 and dim( Kϕ2)=1. Since the degree of ϕ 1(t) is 2, the total number of dots in the dot diagram of ϕ 1(t) is 4/2=2, and the number of dots r 1 in the first row is given by

r 1 = 1 2 [ dim ( R 5 ) rank ( ϕ 1 ( A ) ) ] = 1 2 [ 5 rank ( A 2 + 2 I ) ] = 1 2 [ 5 1 ] = 2.

Thus the dot diagram of ϕ 1(t) is

and each column contributes the companion matrix

( 0 2 1 0 )

for ϕ 1(t)=t 2+2 to the rational canonical form C. Consequently ϕ 1(t) is an elementary divisor with multiplicity 2. Since dim( Kϕ2)=1, the dot diagram of ϕ 2(t)=t2 consists of a single dot, which contributes the 1×1 matrix (2). Hence ϕ 2(t) is an elementary divisor with multiplicity 1. Therefore the rational canonical form C is

We can infer from the dot diagram of ϕ 1(t) that if β is a rational canonical basis for LA, then β Kϕ1 is the union of two cyclic bases βv1 and βv2, where v 1 and v 2 each have annihilator ϕ 1(t). It follows that both v 1 and v 2 lie in N(ϕ 1( LA)). It can be shown that

{ ( 1 0 0 0 0 ) ,   ( 0 1 0 0 0 ) ,   ( 0 0 2 1 0 ) ,   ( 0 0 1 0 1 ) }

is a basis for N(ϕ 1( LA)). Setting v 1=e 1, we see that

A v 1 = ( 0 1 1 1 1 ) .

Next choose v 2 in Kϕ1=N(ϕ( LA)), but not in the span of βv1={v 1, Av 1}. For example, v 2=e 2. Then it can be seen that

A v 2 = ( 2 2 0 2 4 ) ,  

and βv1βv2 is a basis for Kϕ1.

Since the dot diagram of ϕ 2(t)=t2 consists of a single dot, any nonzero vector in Kϕ2 is an eigenvector of A corresponding to the eigenvalue λ=2. For example, choose

v 3 = ( 0 1 1 1 2 ) .

By Theorem 7.23, β={v 1, Av 1, v 2, Av 2, v 3} is a rational canonical basis for LA. So setting

Q = ( 1 0 0 2 0 0 1 1 2 1 0 1 0 0 1 0 1 0 2 1 0 1 0 4 2 ) ,  

we have Q1AQ=C.

Example 6

For the following matrix A, we find the rational canonical form C and a matrix Q such that Q1AQ=C.

A = ( 2 1 0 0 0 2 1 0 0 0 2 0 0 0 0 2 )

Since the characteristic polynomial of A is f(t)=(t2) 4, the only irreducible monic divisor of f(t) is ϕ(t)=t2, and so Kϕ= R 4. In this case, ϕ(t) has degree 1; hence in applying Theorem 7.24 to compute the dot diagram for ϕ(t), we obtain

r 1 = 4 rank ( ϕ ( A ) ) = 4 2 = 2 ,   r 2 = rank ( ϕ ( A ) ) rank ( ( ϕ ( A ) ) 2 ) = 2 1 = 1 ,  

and

r 3 = rank ( ( ϕ ( A ) ) 2 ) rank ( ( ϕ ( A ) ) 3 ) = 1 0 = 1 ,  

where ri is the number of dots in the ith row of the dot diagram. Since there are dim( R 4)=4 dots in the diagram, we may terminate these computations with r 3. Thus the dot diagram for A is

Since (t2) 3 has the companion matrix

( 0 0 8 1 0 12 0 1 6 )

and (t2) has the companion matrix (2), the rational canonical form of A is given by

C = ( 0 0 8 0 1 0 12 0 0 1 6 0 0 0 0 2 ) .

Next we find a rational canonical basis for LA. The preceding dot diagram indicates that there are two vectors v 1 and v 2 in R 4 with annihilators (ϕ(t)) 3 and ϕ(t), respectively, and such that

β = β v 1 β v 2 = { v 1 ,   A v 1 ,   A 2 v 1 ,   v 2 }

is a rational canonical basis for LA. Furthermore, v 1N((LA2I) 2), and v 2N( LA2I). It can easily be shown that

N ( L A 2 I ) = span ( { e 1 ,   e 4 } )

and

N ( ( L A 2 I ) 2 ) = span ( { e 1 ,   e 2 ,   e 4 } ) .

The standard vector e 3 meets the criteria for v 1; so we set v 1=e 3. It follows that

A v 1 = ( 0 1 2 0 ) and A 2 v 1 = ( 1 4 4 0 ) .

Next we choose a vector v 2N( LA2I) that is not in the span of βv1. Clearly, v 2=e 4 satisfies this condition. Thus

{ ( 0 0 1 0 ) ,   ( 0 1 2 0 ) ,   ( 1 4 4 0 ) ,   ( 0 0 0 1 ) }

is a rational canonical basis for LA.

Finally, let Q be the matrix whose columns are the vectors of β in the same order:

Q = ( 0 0 1 0 0 1 4 0 1 2 4 0 0 0 0 1 ) .

Then C=Q1AQ.

Direct Sums*

The next theorem is a simple consequence of Theorem 7.23.

Theorem 7.25. (Primary Decomposition Theorem)

Let T be a linear operator on an n-dimensional vector space V with characteristic polynomial

f ( t ) = ( 1 ) n ( ϕ 1 ( t ) ) n 1 ( ϕ 2 ( t ) ) n 2 ( ϕ k ( t ) ) n k ,  

where the ϕi(t)'s(1ik) are distinct irreducible monic polynomials and the ni’s are positive integers. Then the following statements are true.

  1. V= Kϕ1 Kϕ2 Kϕk.

  2. If Ti(1ik) is the restriction of T to Kϕi and Ci is the rational canonical form of Ti, then C 1C 2Ck is the rational canonical form of T.

Proof.

Exercise.

The next theorem is a simple consequence of Theorem 7.17.

Theorem 7.26.

Let T be a linear operator on a finite-dimensional vector space V. Then V is a direct sum of T-cyclic subspaces Cvi, where each vi lies in Kϕ for some irreducible monic divisor ϕ(t) of the characteristic polynomial of T.

Proof.

Exercise.

Exercises

  1. Label the following statements as true or false.

    1. (a) Every rational canonical basis for a linear operator T is the union of T-cyclic bases.

    2. (b) If a basis is the union of T-cyclic bases for a linear operator T, then it is a rational canonical basis for T.

    3. (c) There exist square matrices having no rational canonical form.

    4. (d) A square matrix is similar to its rational canonical form.

    5. (e) For any linear operator T on a finite-dimensional vector space, any irreducible factor of the characteristic polynomial of T divides the minimal polynomial of T.

    6. (f) Let ϕ(t) be an irreducible monic divisor of the characteristic polynomial of a linear operator T. The dots in the diagram used to compute the rational canonical form of the restriction of T to Kϕ are in one-to-one correspondence with the vectors in a basis for Kϕ.

    7. (g) If a matrix has a Jordan canonical form, then its Jordan canonical form and rational canonical form are similar.

  2. For each of the following matrices A Mn×n(F), find the rational canonical form C of A and a matrix Q Mn×n(F) such that Q1AQ=C.

    1. (a) A=( 3 1 0 0 3 1 0 0 3)F=R

    2. (b) A=( 0 1 1 1)F=R

    3. (c) A=( 0 1 1 1)F=C

    4. (d) A=( 0 7 14 6 1 4 6 3 0 4 9 4 0 4 11 5)F=R

    5. (e) A=( 0 4 12 7 1 1 3 3 0 1 6 4 0 1 8 5)F=R

  3. For each of the following linear operators T, find the elementary divisors, the rational canonical form C, and a rational canonical basis β.

    1. (a) T is the linear operator on P 3(R) defined by

      T ( f ( x ) ) = f ( 0 ) x f ( 1 ) .
    2. (b) Let S={sinx, cosx, xsinx, xcosx}, a subset of F(R, R), and let V=span(S). Define T to be the linear operator on V such that

      T ( f ) = f .
    3. (c) T is the linear operator on M2×2(R) defined by

      T ( A ) = ( 0 1 1 1 ) · A .
    4. (d) Let S={sinxsiny, sinxcosy, cosxsiny, cosxcosy}, a subset of F(R×R, R), and let V=span(S). Define T to be the linear operator on V such that

      T ( f ) ( x ,   y ) = f ( x ,   y ) x + f ( x ,   y ) y .
  4. Let T be a linear operator on a finite-dimensional vector space V with minimal polynomial (ϕ(t))m for some positive integer m.

    1. (a) Prove that R(ϕ(T))N((ϕ(T))m1).

    2. (b) Give an example to show that the subspaces in (a) need not be equal.

    3. (c) Prove that the minimal polynomial of the restriction of T to R(ϕ(T)) equals (ϕ(t))m1.

  5. Let T be a linear operator on a finite-dimensional vector space. Prove that the rational canonical form of T is a diagonal matrix if and only if T is diagonalizable. Visit goo.gl/tK8pru for a solution.

  6. Let T be a linear operator on a finite-dimensional vector space V with characteristic polynomial f(t)=(1)nϕ 1(t)ϕ 2(t), where ϕ 1(t) and ϕ 2(t) are distinct irreducible monic polynomials and n=dim(V).

    1. (a) Prove that there exist v 1, v 2V such that v 1 has T-annihilator ϕ 1(t), v 2 has T-annihilator ϕ 2(t), and βv1βv2 is a basis for V.

    2. (b) Prove that there is a vector v 3V with T-annihilator ϕ 1(t)ϕ 2(t) such that βv3 is a basis for V.

    3. (c) Describe the difference between the matrix representation of T with respect to βv1βv2 and the matrix representation of T with respect to βv3.

    Thus, to assure the uniqueness of the rational canonical form, we require that the generators of the T-cyclic bases that constitute a rational canonical basis have T-annihilators equal to powers of irreducible monic factors of the characteristic polynomial of T.

  7. Let T be a linear operator on a finite-dimensional vector space with minimal polynomial

    f ( t ) = ( ϕ 1 ( t ) ) m 1 ( ϕ 2 ( t ) ) m 2 ( ϕ k ( t ) ) m k ,  

    where the ϕi(t)’s are distinct irreducible monic factors of f(t). Prove that for each i, mi is the number of entries in the first column of the dot diagram for ϕi(t).

  8. Let T be a linear operator on a finite-dimensional vector space V. Prove that for any irreducible polynomial ϕ(t), if ϕ(T) is not one-to-one, then ϕ(t) divides the characteristic polynomial of T. Hint: Apply Exercise 15 of Section 7.3.

  9. Let V be a vector space and β 1, β 2, , βk be disjoint subsets of V whose union is a basis for V. Now suppose that γ 1, γ 2, , γk are linearly independent subsets of V such that span(γi)=span(βi) for all i. Prove that γ 1γ 2γk is also a basis for V.

  10. Let T be a linear operator on a finite-dimensional vector space, and suppose that ϕ(t) is an irreducible monic factor of the characteristic polynomial of T. Prove that if ϕ(t) is the T-annihilator of vectors x and y, then x Cy if and only if Cx= Cy.

Exercises 11 and 12 are concerned with direct sums.

  1. Prove Theorem 7.25.

  2. Prove Theorem 7.26.