Number Theory: An Introduction to Mathematics

4 Linear Diophantine Equations 163

common divisor ofa 2 ,...,an, there exists an invertible(n− 1 )×(n− 1 )matrixV′
such that

(a 2 ···an)V′=(d′ 0 ··· 0 ).

Sincedis the greatest common divisor ofa 1 andd′, there exist integersu,vsuch that

a 1 u+d′v=d.

PutV=I 1 ⊕V′andW=W′⊕In− 2 ,where

W′=

(

u −d′/d

v a 1 /d

)

.

ThenVandWare invertible, and

(a 1 a 2 ···an)VW=(a 1 d′ 0 ··· 0 )W=(d 0 ··· 0 ).

Thus we can takeU=VW.

Corollary 34For any given integers a 1 ,...,an, there exists an invertible n×n
matrix U with a 1 ,...,anas its first row if and only if the greatest common divisor
of a 1 ,...,anis 1.

Proof An invertible matrixUhasa 1 ,...,anas its first row if and only if

(a 1 a 2 ···an)=( 10 ··· 0 )U. 

IfUis invertible, then its transpose is also invertible. It follows that there exists
an invertiblen×nmatrix witha 1 ,...,anas its first column also if and only if the
greatest common divisor ofa 1 ,...,anis 1.

Proposition 35For any m×n matrix A, there exists an invertible n×nmatrixU
such that B=AU has the form

B=(B 1 O),

where B 1 is an m×r submatrix of rank r.

Proof LetAhave rankr.Ifr=n, there is nothing to do. Ifr<nand we denote the
columns ofAbya 1 ,...,an, then there existx 1 ,...,xn∈Z, not all zero, such that

x 1 a 1 +···+xnan=O.

Moreover, we may assume thatx 1 ,...,xnhave greatest common divisor 1. Then,
by Corollary 34, there exists an invertiblen×nmatrixU′withx 1 ,...,xnas its last
column. HenceA′:=AU′has its last column zero. Ifr<n−1, we can apply the
same argument to the submatrix formed by the firstn−1 columns ofA′, and so on
until we arrive at a matrixBof the required form.