Number Theory: An Introduction to Mathematics

4 Linear Diophantine Equations 173

a 11 (D)x 1 +···+a 1 n(D)xn=c 1 (t)

a 21 (D)x 1 +···+a 2 n(D)xn=c 2 (t)

···

am 1 (D)x 1 +···+amn(D)xn=cm(t),

where the coefficientsajk(D)are polynomials inD=d/dtwith complex coefficients

and the right sidescj(t)are, say, infinitely differentiable functions of the timet.Since

C[s] is a Euclidean domain, we can bring the coefficient matrixA=(ajk(D))to Smith

normal form and thus replace the given system by an equivalent system in which the

variables are ‘uncoupled’.

For the polynomial ringR=K[t] it is possible to say more aboutR-modules than

for an arbitrary Euclidean domain, since the absolute value

|f|= 2 ∂(f) iff=O,|O|= 0 ,

has not only the Euclidean property, but also the properties

|f+g|≤max{|f|,|g|}, |fg|=|f||g| for anyf,g∈R.

For anya∈Rm,whereR=K[t], define|a|to be the maximum absolute value
of any of its coordinates. Then a basis for a moduleM⊆Rmcan be obtained in the
following way. SupposeM=Oand choose a nonzero elementa 1 ofMfor which|a 1 |
is a minimum. If there is an element ofMwhich is not of the formp 1 a 1 withp 1 ∈R,
choose one,a 2 ,forwhich|a 2 |is a minimum. If there is an element ofMwhich is not
of the formp 1 a 1 +p 2 a 2 withp 1 ,p 2 ∈R, choose one,a 3 ,forwhich|a 3 |is a minimum.
And so on.
Evidently|a 1 |≤|a 2 |≤···. We will show thata 1 ,a 2 ,...are linearly independent
for as long as the the process can be continued, and thus ultimately a basis is obtained.
If this is not the case, then there exists a positive integerk≤msuch thata 1 ,...,ak
are linearly independent, buta 1 ,...,ak+ 1 are not. Hence there exists 1 ,...,sk+ 1 ∈R
withsk+ 1 =0suchthats 1 a 1 +···+sk+ 1 ak+ 1 =O. For eachj≤k,thereexistqj,
rj∈Rsuch that

sj=qjsk+ 1 +rj, |rj|<|sk+ 1 |.

Put

a′k+ 1 =ak+ 1 +q 1 a 1 +···+qkak, bk=r 1 a 1 +···+rkak.

Sinceak+ 1 is not of the formp 1 a 1 +···+pkak, neither isa′k+ 1 and hence|a′k+ 1 |≥

|ak+ 1 |.Furthermore,|bk|≤max 1 ≤j≤k|rj||aj|<|sk+ 1 ||ak+ 1 |.Sincebk=−sk+ 1 a′k+ 1 ,

by construction, this is a contradiction.

AbasisforMwhich is obtained in this way will be called aminimal basis.

It is not difficult to show that a basisa 1 ,...,anis a minimal basis if and only if

|a 1 |≤···≤|an|and the sum|a 1 |+···+|an|is minimal. Although a minimal basis

is not uniquely determined, the values|a 1 |,...,|an|are uniquely determined.