Number Theory: An Introduction to Mathematics

4 Linear Diophantine Equations 171

On the other hand, ifa 11 dividesa 1 kfor allk>1 then, by subtracting multiples
of the first column from the remaining columns, we can arrange thata 1 k=0forall
k>1. If there is now an entryaj 1 (j> 1 )in the first column which is not divisible
bya 11 then, by subtracting a multiple of the first row from thej-th row, the minimum
absolute value of the nonzero entries can again be reduced. Otherwise, by subtracting
multiples of the first row from the remaining rows, we can bringAto the form
(
a 11 O
OA′

)

.

SinceA = Oand the minimum absolute value of the nonzero entries cannot be
reduced indefinitely, we must in any event arrive at a matrix of this form after a
finite number of steps. The same procedure can now be applied to the submatrixA′,
and so on until we obtain a matrix
(
D′ O
OO

)

,

whereD′is a diagonal matrix with the same rank asA. As in the first part of the proof
of Proposition 41, we can now replaceD′by a diagonal matrixDwhich satisfies the
divisibility conditions.
Clearly this constructive proof is also valid for any Euclidean domainRand, in
particular, for the polynomial ringR=K[t], whereKis an arbitrary field.
It will now be shown that the Smith normal form of a matrixAis uniquely deter-
mined, apart from replacing eachdkby an arbitrary unit multiple. For, ifS′is another
Smith normal form, thenS′=V′SU′for some invertiblem×m,n×nmatricesV′,U′.
Sinced 1 divides all entries ofS, it also divides all entries ofS′. In particular,d 1 |d 1 ′.
Inthesamewayd 1 ′|d 1 and henced 1 ′is a unit multiple ofd 1. To show thatd′kis a unit
multiple ofdk,alsofork>1, it is quickest to use determinants (Chapter V,§1). Since
d 1 ···dkdivides allk×ksubdeterminants orminorsofS, it also divides allk×k
minors ofS′. In particular,d 1 ···dk|d 1 ′···dk′. Similarly,d 1 ′···dk′|d 1 ···dkand hence
d′ 1 ···dk′is a unit multiple ofd 1 ···dk. The conclusion now follows by induction onk.
The products∆k:=d 1 ···dk( 1 ≤k≤r)are known as theinvariant factorsof
the matrixA. A similar argument to that in the preceding paragraph shows that∆kis
the greatest common divisor of allk×kminors ofA.
Twom×nmatricesA,Bare said to beequivalentif there exist invertiblem×m,
n×nmatricesV,Usuch thatB=VAU. Since equivalence is indeed an ‘equivalence
relation’, the uniqueness of the Smith normal form implies that twom×nmatrices
A,Bare equivalent if and only if they have the same rank and the same invariant
factors.
We return now from matrices to modules. LetRbe a principal ideal domain and
Ma finitely generatedR-module, with generatorsa 1 ,...,an. The Smith normal form
tells us thatMhas generatorsa′ 1 ,...,a′n,where

ak=uk 1 a′ 1 +···+ukna′n ( 1 ≤k≤n)

for some invertible matrixU=(uk), such thatdka′k=O( 1 ≤k≤r). Moreover,

x 1 a′ 1 +···+xna′n=O