ple, the minimal polynomial of the sequence discussed in Example 19.2 can

be computed using the algorithm described in §18.2. The minimal polyno-

mial of the sequence discussed in Example 19.3 can be computed in a similar

manner. Also, Exercise 19.3 below shows how one can reformulate another

special case of the problem so that it is easily solved by Gaussian elimination.

However, in the following sections, we will present algorithms for computing

minimal polynomials for certain types of linearly generated sequences that

are much more e¬cient than any algorithm based on Gaussian elimination.

Exercise 19.1. Show that the only sequence for which 1 is a generating

polynomial is the “all zero” sequence.

Exercise 19.2. Let S = (±0 , ±1 , . . .) be a sequence of elements of an F -

vector space V . Further, suppose that S has non-zero minimal polynomial

φ.

(a) Show that for any polynomials g, h ∈ F [X], if g ≡ h (mod φ), then

g S = h S.

(b) Let m := deg(φ). Show that if g ∈ F [X] and (Xi g) S = 0 for

i = 0, . . . , m ’ 1, then g is a generating polynomial for S.

19.1 Basic de¬nitions and properties 427

Exercise 19.3. This exercise develops an alternative characterization lin-

early generated sequences. Let S = (z0 , z1 , . . .) be a sequence of elements

of F . Further, suppose that S has minimal polynomial φ = m cj Xj with

j=0

m > 0 and cm = 1. De¬ne the matrix

«

z1 · · · zm’1

z0

z2 · · ·

¬ z1 zm · m—m

. ·∈F

A := ¬ .

¬ ·

. ..

. . .

.

. . .

zm’1 zm · · · z2m’2

and the vector

w := (zm , . . . , z2m’1 ) ∈ F 1—m .

Show that

v = (’c0 , . . . , ’cm’1 ) ∈ F 1—m

is the unique solution to the equation

vA = w.

Hint: show that the rows of A are linearly independent by making use of

Exercise 19.2 and the fact that no polynomial of degree less than m is a

generating polynomial for S.

Exercise 19.4. Suppose that you are given a0 , . . . , ak’1 ∈ F and

z0 , . . . , zk’1 ∈ F . Suppose that for all i ≥ 0, we de¬ne

k’1

zk+i := aj zj+i .

j=0

Given n ≥ 0, show how to compute zn using O(len(n)k 2 ) operations in F .

Exercise 19.5. Let V be a vector space over F , and consider the set V —∞

of all in¬nite sequences (±0 , ±1 , . . .), where the ±i are in V . Let us de¬ne

the scalar product of g ∈ F [X] and S ∈ V —∞ as

g · S = (g S, (Xg) S, (X2 g) S, . . .) ∈ V —∞ .

Show that with this scalar product, V —∞ is an F [X]-module, and that a

polynomial g ∈ F [X] is a generating polynomial for S ∈ V —∞ if and only if

g · S = 0.

428 Linearly generated sequences and applications

19.2 Computing minimal polynomials: a special case

We now tackle the problem of computing the minimal polynomial of a lin-

early generated sequence from a su¬ciently long initial segment.

We shall ¬rst address a special case of this problem, namely, the case

where the vector space V is just the ¬eld F . In this case, we have

S = (z0 , z1 , z2 , . . .),

where zi ∈ F for i = 0, 1, 2, . . . .

Suppose that we do not know the minimal polynomial φ of S, but we

know an upper bound M ≥ 0 on its degree. Then it turns out that the

initial segment z0 , z1 , . . . z2M ’1 completely determines φ, and moreover, we

can very e¬ciently compute φ given the bound M and this initial segment.

The following theorem provides the essential ingredient.

Theorem 19.2. Let S = (z0 , z1 , . . .) be a sequence of elements of F , and

de¬ne the reversed formal Laurent series

∞

zi X’(i+1) ∈ F ((X’1 )),

z :=

i=0

whose coe¬cients are the elements of the sequence S. Then for any g ∈ F [X],

we have g ∈ G(S) if and only if gz ∈ F [X]. In particular, S is linearly

generated if and only if z is a rational function, in which case, its minimal

polynomial is the denominator of z when expressed as a fraction in lowest

terms.

Proof. Observe that for any polynomial g ∈ F [X] and any integer i ≥ 0,

the coe¬cient of X’(i+1) in the product gz is equal to Xi g S ” just look

at the formulas de¬ning these expressions! It follows that g is a generating

polynomial for S if and only if the coe¬cients of the negative powers of X in

gz are all zero, which is the same as saying that gz ∈ F [X]. Further, if g = 0

and h := gz ∈ F [X], then deg(h) < deg(g)”this follows simply from the fact

that deg(z) < 0 (together with the fact that deg(h) = deg(g) + deg(z)). All

the statements in the theorem follow immediately from these observations.

2

By virtue of Theorem 19.2, we can compute the minimal polynomial φ of S

using the algorithm in §18.5.2 for computing the numerator and denominator

of a rational function from its reversed Laurent series expansion. More

precisely, we can compute φ given the bound M on its degree, along with

the ¬rst 2M elements z0 , . . . , z2M ’1 of S, using O(M 2 ) operations in F .

Just for completeness, we write down this algorithm:

19.3 Computing minimal polynomials: a more general case 429

1. Run the extended Euclidean algorithm on inputs

a := X2M and b := z0 X2M ’1 + z1 X2M ’2 + · · · + z2M ’1 ,

and let s , t be as in Theorem 18.7, using r— := M and t— := M .

2. Output φ := t / lc(t ).

The characterization of linearly generated sequences provided by Theo-

rem 19.2 is also very useful in other ways. For example, suppose the ¬eld

F is ¬nite. As we already saw in Example 19.1, any linearly generated se-

quence S := (z0 , z1 , . . .), where the zi are in F , must be ultimately periodic.

However, Theorem 19.2, together with the result of Exercise 18.13, tells us

much more; for example, if the minimal polynomial φ of S is not divisible

by X, then S is purely periodic with period equal to the multiplicative order

of [X]φ ∈ (F [X]/(φ))— .

19.3 Computing minimal polynomials: a more general case

Having dealt with the problem of ¬nding the minimal polynomial of a se-

quence S of elements of F , we address the more general problem, where the

elements of S lie in a vector space V over F . We shall only deal with a

special case of this problem, but it is one which has useful applications:

• First, we shall assume that V has ¬nite dimension > 0 over F .

• Second, we shall assume that the sequence S = (±0 , ±1 , . . .) has full

rank, by which we mean the following: if the minimal polynomial φ

of S over F has degree m, then the vectors ±0 , . . . , ±m’1 are linearly

independent. The sequences considered in Examples 19.2 and 19.3

are of this type.

• Third, we shall assume that F is a ¬nite ¬eld.

The Dual Space. To develop the theory behind the approach we are

going to present, we need to discuss the dual space DF (V ) of V (over F ),

which consists of all F -linear maps from V into F . We may sometimes refer

to elements of DF (V ) as projections. Now, as was discussed in §15.2, if

we ¬x an ordered basis γ1 , . . . , γ for V , the elements of V are in one-to-

one correspondence with the coordinate vectors F 1— , where the element

a1 γ1 + . . . + a γ ∈ V corresponds to the coordinate vector (a1 , . . . , a ) ∈

F 1— . The elements of DF (V ) are in one-to-one correspondence with F —1 ,

where the map π ∈ DF (V ) corresponds to the column vector whose jth

coordinate is π(γj ), for j = 1, . . . , . It is natural to call the column vector

corresponding to π its coordinate vector. A projection π ∈ DF (V ) may

430 Linearly generated sequences and applications

be evaluated at a point δ ∈ V by taking the product of the coordinate vector