Number Theory: An Introduction to Mathematics

4 Linear Diophantine Equations 165

Supposem 1 =m 2 .Letaandbbe the entries in them 1 -th row of the first and
second columns, and letdbe their greatest common divisor. Thend=0andthere
exist integersu,vsuch thatau+bv=d. If we putU=V⊕In− 2 ,where

V=

(

u −b/d

v a/d

)

,

thenU is invertible. Moreover, the lastn−2 columns ofB = AUare the same
as inAand the firstm 1 −1 entries of the first two columns are still zero. However,
bm 11 =dandbm 12 =0. By permuting the lastn−1 columns, if necessary, we obtain a
matrixA′, of the same form asA, withm′ 1 ≤m′ 2 ≤···≤m′n,wherem′ 1 =m 1 and
m′ 2 +···+m′n>m 2 +···+mn.
By repeating this process finitely many times, we will obtain a matrix in echelon
form.

Corollary 38If A is an m×n matrix of rank m, then there exists an invertible n×n
matrix U such that AU=B=(bjk),where

bjj= 0 ,bjk= 0 if j<k ( 1 ≤j≤m, 1 ≤k≤n).

Before proceeding further we considerthe uniqueness of the echelon form. Let
T=(tjk)be anyr×rmatrix which is lower triangular and invertible, i.e.tjk=0if
j<kand the diagonal elementstjjare units. It is easily seen that ifU=T⊕In−r,
and ifBis an echelon form for a matrixAwith rankr,thenBUis also an echelon form
forA. We will show that all possible echelon forms forAare obtained in this way.
SupposeB′=BUis in echelon form, for some invertiblen×nmatrixU, and write
B=(B 1 O),

whereB 1 is anm×rsubmatrix. If

U=

(

U 1 U 2

U 3 U 4

)

,

then from(B 1 O)U=(B 1 ′O)we obtainU 2 =O,sinceB 1 U 2 =OandB 1 has rankr.
ConsequentlyU 1 is invertible and we can equally well takeU 3 =O,U 4 =I.Let
b 1 ,...,brbe the columns ofB 1 andb′ 1 ,...,b′rthe columns ofB′ 1 .IfU 1 =(tjk), then

b′k=t 1 kb 1 +···+trkbr ( 1 ≤k≤r).

Takingk=1, we obtainm′ 1 ≥m 1 and so, by symmetry,m′ 1 =m 1 .Sincem′k>m′ 1
fork>1, it follows thatt 1 k=0fork>1. Takingk=2, we now obtain in the same
waym′ 2 =m 2. Proceeding in this manner, we see thatU 1 is a lower triangular matrix.
We return now to the linear Diophantine equation

Ax=c.

The set of allc∈Zmfor which there exists a solutionx∈Znis evidently a moduleL⊆
Zm.IfUis an invertible matrix such thatB=AUis in echelon form, thenxis a solu-
tion of the given system if and only ify=U−^1 xis a solution of the transformed system