Number Theory: An Introduction to Mathematics

164 III More on Divisibility

The elementsb 1 ,...,brof a moduleMare said to be abasisforMif they generate

Mand are linearly independent, i.e.x 1 b 1 +···+xrbr=Ofor somex 1 ,...,xr∈Z

implies thatx 1 =···=xr=0. IfOis the only element ofM, we say also thatOis a

basis forM.

In geometric terms, Proposition 35 says that any finitely generated moduleM⊆

Zmhas a finite basis, and that a finite set of generators is a basis if and only if its ele-

ments are linearly independent overQ. Hence any two bases have the same cardinality.

Proposition 36For any m×n matrix A, the setNof allx∈Znsuch that Ax=Ois

a module with a finite basis.

Proof It is evident thatNis a module. By Proposition 35, there exists an invertible
n×nmatrixUsuch thatAU=B=(B 1 O),whereB 1 is anm×rsubmatrix of
rankr. HenceBy=Oif and only if the firstrcoordinates ofyvanish. By takingyto
be the vector withk-th coordinate 1 and all other coordinates 0, for eachksuch that
r<k≤n, we see that the equationBy=Ohasn−rlinearly independent solutions
y(^1 ),...,y(n−r)such that all solutions are given by

y=z 1 y(^1 )+···+zn−ry(n−r),

wherez 1 ,...,zn−r are arbitrary integers. If we putx(j) =Uy(j), it follows that

x(^1 ),...,x(n−r)are a basis for the moduleN. 

Anm×nmatrixB=(bjk)will be said to be inechelon formif the following two

conditions are satisfied:

(i)bjk=0foralljifk>r;

(ii)bjk=0forsomejifk≤rand, ifmkis the least suchj,then1≤m 1 <m 2 <

···<mr≤m.

Evidentlyr=rankB.

Proposition 37For any m×n matrix A, there exists an invertible n×nmatrixU

such that B=AU is in echelon form.

Proof By Proposition 35, we may suppose thatAhas the form(A 1 O),whereA 1 is
anm×rsubmatrix of rankr, and by replacingA 1 byAwe may suppose thatAitself
has rankn. We are going to show that there exists an invertiblen×nmatrixUsuch
that, ifAU=B=(bjk),thenbjk=0forallj<k.
Ifm = 1, this follows from Proposition 33. We assumem >1 and use in-
duction onm. Then the firstm−1rowsofAmay be assumed to have already the
required triangular form. Ifn≤m, there is nothing more to do. Ifn>m, we can take
U=Im− 1 ⊕U′,whereU′is an invertible(n−m+ 1 )×(n−m+ 1 )matrix such that

(am,mam,m+ 1 ···am,n)U′=(a′ 0 ··· 0 ).

ReplacingBbyA, we now suppose that forAitself we haveajk=0forall

j<k.SinceAstill has rankn, each column ofAcontains a nonzero entry. If the first

nonzero entry in thek-th column appears in themk-th row, thenmk≥k. By permuting

the columns, if necessary, we may suppose in addition thatm 1 ≤m 2 ≤···≤mn.