1. There exists a tower of sub¬elds k ⊆ Ki,H ⊆ KH such that Ki,H /k is the Picard-Vessiot

˜ ˜

extension for the system Y = Ai Y .

2. VH has a νi -dimensional GH -invariant subspace Vi,H consisting of vectors of the form

(0, . . . , 0, Yi , 0, . . . , 0), where Yi satis¬es Yi = Ai Yi .

˜ ˜ ˜

3. Let Vi,H ⊆ Ki,H be the full solution space of Y = Ai Y . Then there is an isomorphism

νi

s

˜ ˜

’ Vi,H . Moreover, we have VH

Ξ : Vi,H Vi,H .

i=1

Proof. De¬ne ξi : VH ’ KHi by ξ((Y1T , . . . , YsT )T ) = Yi . We see that ξ is a GH -invariant

ν

¯ ˜ ˜

ν

surjection of VH onto Vi , a full solution space in KHi of Y = Ai Y . The ¬rst statement of

the conclusion of the lemma follows after de¬ning Ki,H /k to be the extension generated by

¯

components of vectors in Vi . The second and third statements then follow easily.

Lemma 3.4.6 Suppose Y = AY + B is of the form (3.33), and let Ki,H /k and Vi,H be as

in Lemma 3.4.5. Write · = (·1 , . . . , ·s )T , ·i ∈ KI i , so that ·i is a particular solution of

ν

T T

the system

˜

˜

Y = Ai Y + Bi . (3.34)

44

Then, for each i, there is a tower of sub¬elds Ki,H ⊆ Ki,I ⊆ KI with Ki,I /k a Picard-Vessiot

extension for the system (3.34), with Ki,I /Ki,H generated by the coordinates of ·i .

Proof. This result is clear from de¬nitions.

s

Lemma 3.4.7 Suppose Y = AY +B is of the form (3.33). Then U Ui (direct sum of

i=1

˜ ˜

GH -modules), where Ui is the unipotent radical of the group of Y = Ai Y + Bi for 1 ¤ i ¤ s.

Proof. Applying Proposition 3.3.1 to Y = AY + B, we see that there is an embedding

¦ : U ’ VH . Let W = ¦(U ) ⊆ VH .

Let Ki,H /k and Vi,H be as in Lemma 3.4.5. Lemma 3.4.5 and basic Galois theory yield

s

˜ ˜ ˜ ˜

VH Vi,H (direct sum of GH -modules), where Vi,H is the solution space of Y = Ai Y .

i=1

s

˜

πi (W ), where πi : VH ’ Vi,H is projection from VH onto

Lemma 3.4.2 implies that W

i=1

˜

Vi,H . We need to show that πi (W ) Ui .

˜ ˜ ˜

Fix i, 1 ¤ i ¤ s. Consider Y = Ai Y + Bi as an equation over KH and let Ki /KH be

˜ ˜

the Picard-Vessiot extension. We have that Gal(Ki /KH ) is a quotient of U and Ki /KH is

generated by the coordinates of ·i . By considering the map Ξ given in Lemma 3.4.5, one

˜

checks that Gal(Ki /KH ) πi (W ).

Now consider the following diagram:

˜

Ki

&

&

KH Ki,I

KH © Ki,I

Ki,H

By de¬nition we have Ui = Gal(Ki,I /Ki,H ). Thus, to show that πi (W ) Ui , it su¬ces

˜

to show that Gal(Ki /KH ) Gal(Ki,I /Ki,H ). In turn, to do this it su¬ces to show that

KH © Ki,I = Ki,H (see Lemma 5.10 of [Kap76]).

Ui is a vector group and in particular an abelian group. It follows that (KH © Ki,I )/Ki,H

is a Picard-Vessiot extension with unipotent Galois group. At the same time, Gal((KH ©

Ki,I )/Ki,H ) is a quotient of Gal(KH /Ki,H ), which is a subgroup of the reductive group GH

and therefore reductive. This implies that Gal((KH ©Ki,I )/Ki,H ) is also reductive. It follows

that Gal((KH © Ki,I )/Ki,H ) = {1} , and we conclude that KH © Ki,I = Ki,H as desired.

45

Lemma 3.4.8 Assume that A = diag (M, M, . . . , M ) , where M ∈ k m—m and there are

ν ≥ 1 copies of M along the diagonal. Assume moreover that Z = M Z is an irreducible

system. Let VM ⊆ KH be the solution space of Z = M Z, so that VH = VM . Write B =

m ν

(B1 , B2 , . . . , Bν )T , Bi ∈ k m . Let · = (·1 , ·2 , . . . , ·ν )T , ·i ∈ KI , be a ¬xed particular

T T T T T T m

solution of Y = AY + B. Let ¦· : U ’ VH be the map de¬ned in Proposition 3.3.1 and let

W = ¦· (U ) ⊆ VH . Let S ⊆ C ν be the vector space de¬ned in the second statement of the

conclusion of Proposition 3.4.2 (assuming V = VH ). De¬ne T ⊆ C ν by

ν

T = {(c1 , . . . , cν ) ∈ C ν

: the system Z = M Z + cj Bj

j=1

has a k-rational solution} .

Then, the following statements hold:

1. T is a C-vector space.

2. T = S.

ν’dimC T

as GH -modules.

3. U VM

Proof. The ¬rst statement of the conclusion is easily veri¬ed, and the third statement follows

directly from the second statement. We prove the second statement as follows:

We see that there is an injection U ’ •j Uj , where Uj is the unipotent radical of

the group of Z = M Z + Bj . For 1 ¤ j ¤ ν, we have that ·j is a particular solution of

Z = M Z + Bj , and we may de¬ne ¦·j : Uj ’ VM by ¦·j („ ) = „.·j ’ ·j or, equivalently,

by writing

¦(„ ) = (¦·1 (π1 („ )), . . . , ¦·ν (πν („ ))) ∈ VM = VH ,

ν

where πj : U ’ Uj is projection onto the jth factor. Also observe that, given c1 , . . . , cν ∈ C,

we have that j cj ·j is a particular solution of the system Z = M Z + j cj Bj . We now

make the following calculation:

(c1 , . . . , cν ) ∈ S ” cj ¦·j („ ) = 0 for all „ ∈ U

j

” cj („.·j ’ ·j ) = 0 for all „ ∈ U

j

” cj ·j for all „ ∈ U

cj „.·j =

j j

46

” cj ·j for all „ ∈ U

„.( cj ·j ) =

j j

” cj ·j ∈ KH (since KH is the ¬xed ¬eld of U )

m

j

” The system Z = M Z + j cj Bj has

a k-rational solution (by Lemma 3.4.3)

” (c1 , . . . , cν ) ∈ T .

This gives us the desired result.

For the remainder of this section, assume k = C(x).

Lemma 3.4.9 There exists an algorithm that takes as input a matrix M ∈ km—m and a

set of vectors B1 , . . . , Bν ∈ k m and computes dimC (T ), where T ⊆ C ν is the vector space

de¬ned in Lemma 3.4.8.

Proof. Let A = diag(M, . . . , M ) with ν copies of M on the diagonal, and let B =

(B1 , . . . , Bν )T . Consider the following conceptually simple algorithm:

T T

1. Compute a cyclic vector for the system Z = M Z; obtain a system of the form (3.18),

and use this system to de¬ne an operator L such that L(y) = 0 is equivalent to

Z = M Z.

2. For each i, use (3.18) and (3.21) to compute an element bi ∈ k such that Z = M Z +Bi

is equivalent to L(y) = bi .

ˆ

3. De¬ne a new operator L by

b b

ˆ

L = LCLM D ’ 1 , . . . , D ’ ν —¦ L.

b1 bν

ˆ

4. Compute a basis F of k-rational solutions of the equation L(y) = 0. For each element

f in this basis, test whether f satis¬es L(f ) = 0.

5. Return the number of elements of F that are not solutions of L(y) = 0.

We prove the correctness of this algorithm as follows. For a given (c1 , . . . , cν ) ∈ C ν , we have

that Z = M Z + j cj Bj admits a k-rational solution if and only if the equation L(y) =

does. Suppose f ∈ k satis¬es L(f ) = for some (c1 , . . . , cν ) ∈ C ν . It follows

j cj bj j cj bj

47

ˆ ˆ

that L(f ) = 0. Conversely, we see that if L(f ) = 0 and L(f ) = 0, then L(f ) = j cj bj for

some (c1 , . . . , cν ) ∈ C ν . The desired result now follows easily.

We note that it is possible to write a more e¬cient algorithm than the above, using

methods similar to those of Lemma 2.8 of [BS99].

We are now ready to present the main algorithm of this section.

Algorithm III.

Input: A matrix A ∈ C(x)n—n and a vector B ∈ C(x)n

Output: An explicit description of the Galois group of the system Y = AY + B

1. Using a cyclic-vector computation, rede¬ne A and compute Ai , Bi , Mi , mi so that the

system (3.33) is equivalent to the original system.

2. For 1 ¤ i ¤ s, write Bi = (Bi,1 , . . . , Bi,νi )T . Using Lemma 3.4.9, compute ri = dimC Ti ,

T T

where

Ti = (ci,1 , . . . , ci,νi ) : the system Z = Mi Z + ci,j Bi,j

j

admits a k-rational solution .

Let ri = νi ’ ri .

˜

3. Using [CS99], compute a set H of de¬ning equations for Ψ(GH ), where Ψ : GH ’

GLn (C) is a matrix representation of GH on VH with respect to some basis of VH

having the following property: Given a matrix Q = Ψ(σ), σ ∈ GH , then we have

¯ ¯ ¯

Q = diag(Q1 , . . . , Qs ) with Qi = diag(Qi , . . . , Qi ) (νi copies) and Qi gives the action

of σ on VMi with respect to some ¬xed basis of VMi for 1 ¤ i ¤ s. Here, VMi is the

solution space of Z = Mi Z.

4. Return H, m1 , . . . , ms , r1 , . . . , rs . The group of Y = AY + B is

˜ ˜

ˆ

C r i mi

˜

GH ,

i

where:

ˆ