4 Linear Diophantine Equations 167A 1 X=A 2.We say in this case thatA 1 is aleft divisorofA 2 ,orthatA 2 is aright multipleofA 1.
We may also define greatest common divisors and least common multiples for
matrices. Anm×pmatrixDis agreatest common left divisorofA 1 andA 2 if it is a
left divisor of bothA 1 andA 2 , and if every left divisorCof bothA 1 andA 2 is also a
left divisor ofD.Anm×qmatrixHis aleast common right multipleofA 1 andA 2
if it is a right multiple of bothA 1 andA 2 , and if every right multipleGof bothA 1 and
A 2 is also a right multiple ofH. It will now be shown that these objects exist and have
simple geometrical interpretations.
LetM 1 ,M 2 be the modules defined by the matricesA 1 ,A 2. We will show that if
the sumM 1 +M 2 is defined by the matrixD,thenDis a greatest common left divisor
ofA 1 andA 2. In factDis a common left divisor ofA 1 andA 2 ,sinceM 1 andM 2 are
contained inM 1 +M 2. On the other hand, any common left divisorCofA 1 andA 2
defines a module which containsM 1 +M 2 , since it contains bothM 1 andM 2 ,andso
Cis a left divisor ofD.
A similar argument shows that if the intersectionM 1 ∩M 2 is defined by the matrix
H,thenHis a least common right multiple ofA 1 andA 2.
The sumM 1 +M 2 is defined, in particular, by the block matrix (A 1 A 2 ). There
exists an invertible(n 1 +n 2 )×(n 1 +n 2 )matrixUsuch that
(A 1 A 2 )U=(D′O),whereD′is anm×rsubmatrix of rankr.If
U=(
U 1 U 2
U 3 U 4
)
,
is the corresponding partition ofU,then
A 1 U 1 +A 2 U 3 =D′.On the other hand,
(A 1 A 2 )=(D′O)U−^1.If
U−^1 =(
V 1 V 2
V 3 V 4
)
is the corresponding partition ofU−^1 ,then
A 1 =D′V 1 , A 2 =D′V 2.ThusD′is a common left divisor ofA 1 andA 2 , and the previous relation implies that
it is a greatest common left divisor. It follows thatanygreatest common left divisorD
ofA 1 andA 2 has a right ‘B ́ezout’ representationD=A 1 X 1 +A 2 X 2.
We may also define coprimeness for matrices. Two matrices A 1 ,A 2 of size
m×n 1 ,m×n 2 areleft coprimeifImis a greatest common left divisor. IfM 1 ,M 2
are the modules defined byA 1 ,A 2 ,thismeansthatM 1 +M 2 =Zm. The definition
may also be reformulated in several other ways: