has minimal polynomial φ under „ . 2

Theorem 19.7 says that if „ has minimal polynomial φ of degree m ≥ 0,

then there exists β ∈ V such that

β, „ (β), . . . , „ m’1 (β)

are linearly independent. From this, it immediately follows that:

444 Linearly generated sequences and applications

Theorem 19.8. If V has ¬nite dimension > 0, then for any „ ∈ LF (V ),

the minimal polynomial of „ is non-zero of degree at most .

We close this section a simple observation. Let V be an arbitrary, non-

trivial F [X]-module with scalar multiplication . Restricting the scalar mul-

tiplication from F [X] to F , we can naturally view V as an F -vector space.

Let „ : V ’ V be the map that sends ± ∈ V to X ±. It is easy to see that

„ ∈ LF (V ), and that for all polynomials f ∈ F [X], and all ± ∈ V , we have

f ± = f („ )(±). Thus, instead of starting with a vector space and de¬ning

an F [X]-module structure in terms of a given linear map, we can go the other

direction, starting from an F [X]-module and obtaining a corresponding lin-

ear map. Furthermore, using the language introduced in Examples 14.14

and 14.15, we see that the F [X]-exponent of V is the ideal of F [X] generated

by the minimal polynomial of „ , and the F [X]-order of any element ± ∈ V is

the ideal of F [X] generated by the minimal polynomial of ± under „ . The-

orem 19.7 says that there exists an element in V whose F [X]-order is equal

to the F [X]-exponent of V , assuming the latter is non-zero.

So depending on one™s mood, one can place emphasis either on the linear

map „ , or just talk about F [X]-modules without mentioning any linear maps.

Exercise 19.16. Let „ ∈ LF (V ) have non-zero minimal polynomial φ of

degree m, and let φ = pe1 · · · per be the factorization of φ into monic irre-

r

1

ducible polynomials in F [X]. Let be the scalar multiplication associated

with „ . Show that β ∈ V has minimal polynomial φ under „ if and only if

φ/pi β = 0 for i = 1, . . . , r.

Exercise 19.17. Let „ ∈ LF (V ) have non-zero minimal polynomial φ. Show

that „ is an invertible map if and only if X φ.

Exercise 19.18. Let F be a ¬nite ¬eld, and let V have ¬nite dimension

> 0 over F . Let „ ∈ LF (V ) have minimal polynomial φ, with deg(φ) = m

(and of course, by Theorem 19.8, we have m ¤ ). Suppose that ±1 , . . . , ±s

are randomly chosen elements of V . Let gj be the minimal polynomial of ±j

under „ , for j = 1, . . . , s. Let Q be the probability that lcm(g1 , . . . , gs ) = φ.

The goal of this exercise is to show that Q ≥ Λφ (s), where Λφ (s) is as

F F

de¬ned in §19.3.

(a) Using Theorem 19.7 and Exercise 19.15, show that if m = , then

Q = Λφ (s).

F

(b) Without the assumption that m = , things are a bit more challeng-

ing. Adopting the matrix-oriented point of view discussed at the end

of §19.3, and transposing everything, show that

19.6 The algebra of linear transformations (—) 445

“ there exists π ∈ DF (V ) such that the sequence (π —¦ „ i )∞ has

i=0

minimal polynomial φ, and

“ if, for j = 1, . . . , s, we de¬ne hj to be the minimal polyno-

mial of the sequence (π(„ i (±j )))∞ , then the probability that

i=0

lcm(h1 , . . . , hs ) = φ is equal to Λφ (s).

F

(c) Show that hj | gj , for j = 1, . . . , s, and conclude that Q ≥ Λφ (s).

F

Exercise 19.19. Let f, g ∈ F [X] with f = 0, and let h := f / gcd(f, g).

Show that g · F [X]/(f ) and F [X]/(h) are isomorphic as F [X]-modules.

Exercise 19.20. In this exercise, you are to derive the fundamental theo-

rem of ¬nite dimensional F [X]-modules, which is completely analogous

to the fundamental theorem of ¬nite abelian groups. Both of these results

are really special cases of a more general decomposition theorem for mod-

ules over a principal ideal domain. Let V be an F [X]-module. Assume that

as an F -vector space, V has ¬nite dimension > 0, and that the F [X]-

exponent of V is generated by the monic polynomial φ ∈ F [X] (note that

1 ¤ deg(φ) ¤ ). Show that there exist monic, non-constant polynomials

φ1 , . . . , φt ∈ F [X] such that

• φi | φi+1 for i = 1, . . . , t ’ 1, and

• V is isomorphic, as an F [X]-module, to the direct product of F [X]-

modules

V := F [X]/(φ1 ) — · · · — F [X]/(φt ).

Moreover, show that the polynomials φ1 , . . . , φt satisfying these conditions

are uniquely determined, and that φt = φ. Hint: one can just mimic the

proof of Theorem 8.44, where the exponent of a group corresponds to the

F [X]-exponent of an F [X]-module, and the order of a group element cor-

responds to the F [X]-order of an element of an F [X]-module ” everything

translates rather directly, with just a few minor, technical di¬erences, and

the previous exercise is useful in proving the uniqueness part of the theorem.

Exercise 19.21. Let us adopt the same assumptions and notation as in

Exercise 19.20, and let „ ∈ LF (V ) be the map that sends ± ∈ V to X ±.

Further, let σ : V ’ V be the isomorphism of that exercise, and let „ ∈

LF (V ) be the X-multiplication map on V .

(a) Show that σ —¦ „ = „ —¦ σ.

(b) From part (a), derive the following: there exists an ordered basis for

V over F , with respect to which the matrix representing „ is the

446 Linearly generated sequences and applications

“block diagonal” matrix

«

C1

C2

¬ ·

T =¬ ·,

¬ ·

..

.

Ct

where each Ci is the companion matrix of φi (see Example 15.1).

Exercise 19.22. Let us adopt the same assumptions and notation as in

Exercise 19.20.

(a) Using the result of that exercise, show that V is isomorphic, as an

F [X]-module, to a direct product of F [X]-modules

F [X]/(pe1 ) — · · · — F [X]/(per ),

r

1

where the pi are monic irreducible polynomials (not necessarily dis-

tinct) and the ei are positive integers, and this direct product is

unique up to the order of the factors.

(b) Using part (a), show that there exists an ordered basis for V over

F , with respect to which the matrix representing „ is the “block

diagonal” matrix

«

C1

C2

¬ ·

T =¬ ·,

¬ ·

..

.

Cr

where each Ci is the companion matrix of pei .

i

Exercise 19.23. Let us adopt the same assumptions and notation as in

Exercise 19.20.

(a) Suppose ± ∈ V corresponds to ([f1 ]φ1 , . . . , [ft ]φt ) ∈ V under the iso-

morphism of that exercise. Show that the F [X]-order of ± is generated

by the polynomial

lcm(φ1 / gcd(f1 , φ1 ), . . . , φt / gcd(ft , φt )).

(b) Using part (a), give a short and simple proof of the result of Exer-

cise 19.18.

19.7 Notes 447