c ∈ F and „ ∈ LF (V ), de¬ne c„ to be the map that sends ± ∈ V to c„ (±).

Exercise 19.10. (a) Verify that with addition and scalar multiplication

de¬ned as above, LF (V ) is an F -vector space.

(b) Suppose that V has ¬nite dimension > 0. By identifying elements

of LF (V ) with — matrices over F , show that LF (V ) has dimension

2.

As usual, for „, „ ∈ LF (V ), the composed map, „ —¦ „ that sends ± ∈

V to „ („ (±)) is also an element of LF (V ) (verify). As always, function

composition is associative (i.e., for „, „ , „ ∈ LF (V ), we have „ —¦ („ —¦ „ ) =

(„ —¦ „ ) —¦ „ ); however, function composition is not in general commutative

(i.e., we may have „ —¦ „ = „ —¦ „ for some „, „ ∈ LF (V )). For any „ ∈ LF (V )

and an integer i ≥ 0, the map „ i (i.e., the i-fold composition of „ ) is also an

element of LF (V ). Note that for any „ ∈ LF (V ), the map „ 0 is by de¬nition

just the identity map on V .

For any „ ∈ LF (V ), and for any polynomial f ∈ F [X], with f = i ai Xi ,

we denote by f („ ) the linear transformation

ai „ i .

f („ ) :=

i

Exercise 19.11. Verify the following properties of LF (V ). For all „, „ , „ ∈

LF (V ), for all c ∈ F , and all f, g ∈ F [X]:

(a) „ —¦ („ + „ ) = „ —¦ „ + „ —¦ „ ;

(b) („ + „ ) —¦ „ = „ —¦ „ + „ —¦ „ ;

(c) c(„ —¦ „ ) = (c„ ) —¦ „ = „ —¦ (c„ );

(d) f („ ) —¦ g(„ ) = (f g)(„ ) = g(„ ) —¦ f („ );

19.6 The algebra of linear transformations (—) 441

(e) f („ ) + g(„ ) = (f + g)(„ ).

Under the addition operation of the vector space LF (V ), and de¬ning

multiplication on LF (V ) using the “—¦” operation, we get an algebraic struc-

ture that satis¬es all the properties of De¬nition 9.1, with the exception of

property (v) of that de¬nition (commutativity). Thus, we can view LF (V )

as a non-commutative ring with unity (the identity map acts as the multi-

plicative identity).

For a ¬xed „ ∈ LF (V ), we may consider the subset of LF (V ),

F [„ ] := {f („ ) : f ∈ F [X]},

which does in fact satisfy all the properties of De¬nition 9.1. Moreover, we

can view F as a subring of F [„ ] by identifying c ∈ F with c„ 0 ∈ F [„ ]. With

this convention, for f ∈ F [X], the expression f („ ) has its usual meaning as

the value of f evaluated at the point „ in the extension ring F [„ ] of F . Let

φ„ is the minimal polynomial of „ over F , so that F [„ ] is isomorphic as an

F -algebra to F [X]/(φ„ ). We can also characterize φ„ as follows (verify):

if there exists a non-zero polynomial f ∈ F [X] such that f („ ) =

0, then φ„ is the monic polynomial of least degree with this

property; otherwise, φ„ = 0.

Another way to characterize φ is as follows (verify):

φ„ is the minimal polynomial of the sequence (1, „, „ 2 , . . .).

Note that φ„ is never 1 ” this follows from the assumption that V is

non-trivial.

It is easy to see that if V happens to be ¬nite dimensional, with :=

dimF (V ), then by Exercise 19.10, LF (V ) has dimension 2 . Therefore, there

2

must be a linear dependence among 1, „, . . . , „ , which implies that the

minimal polynomial of „ is non-zero with degree at most 2 . We shall show

below that in this case, the minimal polynomial of „ actually has degree at

most .

For a ¬xed „ ∈ LF (V ), we can de¬ne a “scalar multiplication” operation

, that maps f ∈ F [X] and ± ∈ V to

± := f („ )(±) ∈ V ;

f

i

that is, if f = i ai X , then

ai „ i (±).

f ±=

i

442 Linearly generated sequences and applications

Exercise 19.12. Show that the scalar multiplication , together with the

usual addition operation on V , makes V into an F [X]-module; that is, show

that for all f, g ∈ F [X] and ±, β ∈ V , we have

f (g ±) = (f g) ±, (f + g) ±=f ±+g ±,

f (± + β) = f ±+f β, 1 ± = ±.

Note that each choice of „ gives rise to a di¬erent F [X]-module structure,

but all of these structures are extensions of the usual vector space structure,

in the sense that for all c ∈ F and ± ∈ V , we have c ± = c±.

Now, for ¬xed „ ∈ LF (V ) and ± ∈ V , consider the F [X]-linear map

ρ„,± : F [X] ’ V that sends f ∈ F [X] to f ± = f („ )(±). The kernel of this

map must be a submodule, and hence an ideal, of F [X]; since every ideal

of F [X] is principal, it follows that ker(ρ„,± ) is the ideal of F [X] generated

by some polynomial φ„,± , which we can make unique by insisting that it is

monic or zero. We call φ„,± the minimal polynomial of ± under „ .We

can also characterize φ„,± as follows (verify):

if there exists a non-zero polynomial f ∈ F [X] such that

f („ )(±) = 0, then φ„,± the monic polynomial of least degree

with this property; otherwise, φ„,± = 0.

Another way to characterize φ„,± is as follows (verify):

φ„,± is the minimal polynomial of the sequence

(±, „ (±), „ 2 (±), . . .).

Note that since φ„ („ ) is the zero map, we have

φ„ ± = φ„ („ )(±) = 0,

and hence φ„ ∈ ker(ρ„,± ), which means that φ„,± | φ„ .

Now consider the image of ρ„,± , which we shall denote by ± „ . As an F [X]-

module, ± „ is isomorphic to F [X]/(φ„,± ). In particular, if φ„,± is non-zero

and has degree m, then ± „ is a vector space of dimension m over F ; indeed,

the vectors ±, „ (±), . . . , „ m’1 (±) form a basis for ± „ over F ; moreover, m

is the smallest non-negative integer such that ±, „ (±), . . . , „ m (±) are linearly

dependent.

Observe that for any β ∈ ± „ , we have φ„,± β = 0; indeed, if β = f ±,

then

φ„,± (f ±) = (φ„,± f ) ±=f (φ„,± ±) = f 0 = 0.

In the following three exercises, „ is an element of LF (V ), and is the

associated scalar multiplication that makes V into an F [X]-module.

19.6 The algebra of linear transformations (—) 443

Exercise 19.13. Let ± ∈ V have minimal polynomial f ∈ F [X] under „ ,

and let β ∈ V have minimal polynomial g ∈ F [X] under „ . Show that if

gcd(f, g) = 1, then

©β = {0}, and

(a) ± „ „

(b) ± + β has minimal polynomial f · g under „ .

Exercise 19.14. Let ± ∈ V . Let q ∈ F [X] be a monic irreducible polynomial

such that q e ± = 0 but q e’1 ± = 0 for some integer e ≥ 1. Show that q e

is the minimal polynomial of ± under „ .

Exercise 19.15. Let ± ∈ V , and suppose that ± has minimal polynomial

f ∈ F [X] under „ , with f = 0. Let g ∈ F [X]. Show that g ± has minimal

polynomial f / gcd(f, g) under „ .

We are now ready to state the main result of this section, whose statement

and proof are analogous to that of Theorem 8.40:

Theorem 19.7. Let „ ∈ LF (V ), and suppose that „ has non-zero minimal

polynomial φ. Then there exists β ∈ V such that the minimal polynomial of

β under „ is φ.

Proof. Let be the scalar multiplication associated with „ . Let φ =

e1 er be the factorization of φ into monic irreducible polynomials in

p1 · · · p r

F [X].

First, we claim that for each i = 1, . . . , r, there exists ±i ∈ V such that

φ/pi ±i = 0. Suppose the claim were false: then for some i, we would

have φ/pi ± = 0 for all ± ∈ V ; however, this means that (φ/pi )(„ ) =

0, contradicting the minimality property in the de¬nition of the minimal

polynomial φ. That proves the claim.

Let ±1 , . . . , ±r be as in the above claim. Then by Exercise 19.14, each

φ/pei ±i has minimal polynomial pei under „ . Finally, by part (b) of

i i

Exercise 19.13, the vector

β := φ/pe1 ±1 + · · · + φ/per ±r

r