170 III More on Divisibility
Proposition 41Let R be a principal ideal domain and let A be an m×n matrix with
entries from R. If A has rank r , then there exist invertible m×m, n×n matrices V,U
with entries from R such that S=VAU has the form
S=
(
DO
OO
)
,
where D=diag[d 1 ,...,dr]is a diagonal matrix with nonzero entries diand di|djfor
1 ≤i≤j≤r.
Proof We show first that it is enough to obtain a matrix which satisfies all the require-
ments except the divisibility conditions for thed’s.
Ifa,bare nonzero elements ofRwith greatest common divisord, then there exist
u,v∈Rsuch thatau+bv=d. It is easily verified that
(
11
−bv/dau/d
)(
a 0
0 b)(
u −b/d
v a/d)
=
(
d 0
0 ab/d)
,
and the outside matrices on the left-hand side are both invertible. By applying this
process finitely many times, a non-singular diagonal matrixD′ =diag[d 1 ′,...,dr′]
may be transformed into a non-singular diagonal matrixD=diag[d 1 ,...,dr]which
satisfiesdi|djfor 1≤i≤j≤r.
Consider now an arbitrary matrixA. By applying Proposition 35 to the transpose
ofA, we may reduce the problem to the case whereAhas rankmand then, by Corol-
lary 38, we may suppose further thatajj=0,ajk=0forallj<k.
It is now sufficient to show that, for any 2×2matrix
A=
(
a 0
bc)
,
with nonzero entriesa,b,c, there exist invertible 2×2 matricesU,Vsuch thatVAUis
a diagonal matrix. Moreover, we need only prove this when the greatest common divi-
sor(a,b,c)=1. But then there existsq∈Rsuch that(a,b+qc)=1. In fact, takeqto
be the product of the distinct primes which divideabut notb. For any prime divisorp
ofa,ifp|b,thenpc,pqand hencep(b+qc);ifpb,thenp|qand againp(b+qc).
If we putb′=b+qc, then there existx,y∈Rsuch thatax+b′y=1, and hence
ax+by= 1 −qcy. It is easily verified that
(
xy
−b′ a
)(
a 0
bc)(
1 −cy
q 1 −qcy)
=
(
10
0 ac)
,
and the outside matrices on the left-hand side are both invertible.
In the important special caseR=Z, there is a more constructive proof of Proposi-
tion 41. Obviously we may supposeA=O. By interchanges of rows and columns we
can arrange thata 11 is the nonzero entry ofAwith minimum absolute value. If there
is an entrya 1 k(k> 1 )in the first row which is not divisible bya 11 , then we can write
a 1 k=za 11 +a 1 ′k,wherez,a′ 1 k∈Zand|a 1 ′k|<|a 11 |. By subtractingztimes the first
column from thek-th column we replacea 1 kbya′ 1 k. Thus we obtain a new matrixA
in which the minimum absolute value of the nonzero entries has been reduced.