SYSTEMS OF LINEAR CONGRUENCES, AN'D
LEFT-ASSOCIATIVITY OF MATRICES.
WHOSE ELEMENTS ARE INTEGERS FROM
AN ALGEBRA

Thesis for the bound oi Ph. D.
MICHIGAN STATE COLLEGE

Alton Thamas 'Buts‘on
I955

 

 

 

 

I* . Vw

lnggihfihfie 5
Michigan State
Universityg -

 

 

 

O'Q.‘ ,

This is to certify that the

thesis entitled

Systers of linear congruences,
and 1?;t—nseociefifiv3f3 of natrices,

o ‘

"whose elements are lutegers from 8L alga ya.

presented by

Alton Thomas Eutson

has been accepted towards fulfillment
of the requirements for

 

 

fl-W- W

 

 

 

Major professor

Date Lay a, 1.955

 

0-169

 

 

 

MSU

LIBRARIES
.—,——.

RETURNING MATERIALS:

 

 

 

Place in book drop to
remove this checkout from
your record. FINES will
be charged if book is
returned after the date
stamped below.

 

 

 

 

 

 

VITA

Alton Thomas Butson
candidate for the degree of
Doctor of Philosophy

Final examination, May 6, 1955, 2:00 P. M., in Room 510,
Physics Mathematics Building

Dissertation: Systems of Linear Congruences, and Left-
Associativity of Matrices, Whose Elements
are Integers from an Algebra

Outline of Studies

Major subject: Mathematics (algebra)
Minor subjects: Mathematics (analysis, statistics,
tepology)

Biographical Items
Born, February 18, 1926, Lancaster, Pennsylvania

Undergraduate Studies, Franklin & Marshall College,
1946-1950

Graduate Studies, Michigan State College, 1950-1951,
continued 1951-1955

Experience: Graduate Assistant, 1950-1955, Graduate
Teaching Assistant, 1955-1954, Instructor,
1954-1955, Michigan State College

Member of Phi Beta.Kappa, Phi Kappa Phi, Associate
member of the Society of the Sigma Xi, American
Mathematical Society, Mathematical Association of
America

 

 

SYSTEMS OF LINEAR CONGRUENCES, AND LEFT-ASSOCIATIVITY
OF MATRICES, WHOSE ELEMENTS ARE INTEGERS
FROM AN ALGEBRA

By
ALTON THOMAS BUTSON

A THESIS

Submitted to the School of Graduate Studies of Michigan
State College of Agriculture and Applied Science
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Mathematics

1955

T511

mi

‘3 .h‘u hu...’ 'JIIE'MIVA fihulal .o' i
-

 

ACKNOWLEDGMENTS

The author wishes to express his sincere thanks to
Professor B. M. Stewart, under whose constant supervision
and.unfailing interest this investigatibn was undertaken
and to whom the results are herewith dedicated. Grateful
acknowledgment is also due many others in the Mathematics.

Department for their kind help and encouragement.

The writer also extends his sincere thanks to his
wife whose cooperation and encouragement helped make this

thesis possible.

360052

SYSTEMS OF LINEAR CONGRUENCES, AND LEFT-ASSOCIATIVITY
OF MATRICES, WHOSE ELEMENTS ARE INTEGERS
FROM AN ALGEBRA

BY
Alton Thomas Butson

AN ABSTRACT

Submitted to the School of Graduate Studies of Michigan
State College of Agriculture and Applied Science
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Mathematics

Year 1955

Approved fl. fig SW A

ABSTRACT

A major part Of this thesis is devoted to the problem
of solving a system of linear equations or a system of
linear congruences whose elements are‘integers from an
algebra. By means of regular representations each of
these systems is replaced by an equivalent system whose
elements are in a principal ideal ring. A system of
equations is replaced by a system of linear equations of
a classical type whose solution is known. A system of
congruences is replaced by a system of linear congruences
whose elements are actually matrices over a principal
ideal ring. This latter system is solved by a procedure
analogous to that employed in the classical case. Neces-
sary and.sufficient conditions are obtained for the exis-
tence of a solution whose elements are integers of the
algebra. These conditions are in terms of elements of
the principal ideal ring. This problem is completely
solved - the main tool used being the regular representa-
tions.

Each matrix A whose elements are integers from an
algebra has as a reduced regular representation a matrix
s(A) whose elements are in a principal ideal ring. The
remainder of the thesis is concerned with the possibility
that a necessary and sufficient condition that A and B be

left-associates is that s(A) and s(B) have the same Hermite
form. The condition is a necessary one and.will be shown
sufficient when A and B are not divisors of 0. A problem
for further research is whether the condition is sufficient

when A and B are divisors of 0.

 

.tlv. . “:1

9—de

Section

1.
2.
5.
4.
5.
6.

7.

8.

9.

10.
11.

12.

 

TABLE OF CONTENTS

INTRODUCTION.................................
CANONICAL FORMS..............................
LINEAR EQUATIONS IN'TI.......................
LINEAR CONGRUENCES IND
A MIXED SYSTEM IN I).........................
INTEGRAL ELEMENTS AND REGULAR
REPRESENTATIONS..............................
SYSTEMS OF LINEAR EQUATIONS OVER @5..........
MINIMAL BASES FOR IDEALS IN 65...............
SYSTEMS 0F LINEAR CONGRUENCES MODULO

IDEALS OVER @5...............................
MATRICES IN TWXn,n;@;).......................
LEFT-ASSOCIATIVITY 0F MATRICES IN

mn,n;g)0000.000......OOIOOOOOOOOOOOOOOOOCO
CONCLUSIONOOOOOICCCOIO.IIOOOOOCOOCOOIOOOOOCCC

BIBLIOGRAPIHOOOO0......0.0....0.0000000000000IOOOOOOOC

Page

11
16
22

27
51
58

43
62

69
79

 

 

 

 

(I)

L-

SYSTEMS OF LINEAR CONGRUENCES, AND LEFT-ASSOCIATIVITY OF
MATRICES, WHOSE ELEMENTS ARE INTEGERS
FROM AN ALGEBRA

1. Introduction. The problem of solving a system of
linear equations or a system of linear congruences whose
elements are in a principal ideal ring has been solved very
neatly and.comp1etely a long time ago by H. J. S. Smith
[8,9]. A major part of this thesis is devoted to extending
these results to systems whose elements are integers from
an algebra. The modus operandi-is to replace by means of
the regular representations the system whose elements are
integers from.an algebra by an equivalent system whose
elements are in a principal ideal ring. A system of equa-
tions is replaced by a system of linear equations of the
type solved by Smith. A system of congruences is replaced
by a system of linear congruences whose elements including
the moduli are actually matrices over a principal ideal
ring. This latter system is solved by a procedure analo-
gous to that used by Smith in solving an ordinary system of
congruences. Necessary and.sufficient conditions are
obtained for the existence of a solution whose elements are
integers from the algebra. These conditions are in terms
of the invariant factors of the coefficient matrix and the

augmented.matrix of the corresponding system in the

of

A.

principal ideal ring. This problem of solving a system
whose elements are integers from an algebra is completely
resolved - the main tool used being the regular representa-
tions.

B. M. Stewart [12] determined a necessary and sufficient
condition that two matrices A and B whose elements are
integers of an algebraic field be left-associates, 1.6.,
that there exists a unimodular matrix P whose elements are
also integers of the algebraic field such that PA==B. The

condition is that AE andBE have the same Hermite form,

where AE and B8

are the matrices in the rational domain
obtained by replacing each element of A and B, respectively,
by its second regular representation. The remainder of this
thesis is concerned with an attempt to extend this result to
matrices AI and B* Whose elements are integers from an
algebra. A reduced regular representation Of A“ is the
matrix s(AI) whose elements are in a principal ideal ring;
consequently, the Hermite form of s(A’) is well-defined.

The condition that s(AI) and s(B*) have the same Hermite
form is a necessary one for AI and.B* to be left-associates,
and it will be shown sufficient when A* and 3* are not
divisors of 0. The method used will suggest how a future
investigation might proceed either to obtain a complete

proof or to construct a negative example.

 

2. Canonical Forms. In this section the Hermite and
the Smith canonical forms for matrices with elements in a
principal ideal ring will be described. The following
brief summary will recall the position that the principal
ideal ring occupies with respect to other related algebraic
varieties.

A ring is a.mathematical system cOmposed Of more than
one element, an equals relation, and two operations,-+ and
‘x, under which the set of elements is closed. With.respect
to the operation-I, the elements form an Abelian group with
O as an identity. The operation X.is associative, and
distributive with respect to the operation-+. The opera-
tion X may or may not have an identity element 1, may or
may not provide inverses, may or may not be commutative,
and.may or may not possess divisors of 0.

A domain of integrity is a commutative ring without
divisors of 0. A principal ideal ring is a domain of
integrity which has an identity element 1, and in which
every two elements not both 0 have a greatest common
divisor representable linearly in terms of the elements;

further, there is a chain condition that if in the sequence

31,32,55, so.

every number is a proper divisor of the preceding, there

are but a finite number of a's in the sequence. A field is
a principal ideal ring in which the elements other than 0
form an Abelian group with respect to the operation x.

Familiar examples of a field and a principal ideal
ring are the rational field Rb. and the rational integral
domain [Rd] respectively.

Let I} be a principal ideal ring with elements a,b,...;
and denote by m(n,p;13) the set of all n-by-p matrices

A: (are), B=(br8)'... (r=l,2,ooo,n; 8:1’2,0003p)

with elements, in I3 . A matrix P of Mn,n;P) is called
unimodular if there exists a matrix Q in Wmngp )‘such
that Q,P=In (In==(8r8), where 8rs=1 if r=s, and 8r3=0
if rats). In terms of determinants this implies that
det(Q)det(P)=l, hence det(P) is a unit of D . Therefore
P1 (the inverse of P) is in Wmngp): since PIP=PPI=In
it follows that Q=PI and that Q is also unimodular.

If there exists a unimodular matrix P such that PA=B,
than B is said to be a left-associate of A. This relation
is an equivalence relation; hence A and B may be said to
be left-associated without ambiguity of meaning.

The following lemma was first stated by C. Hermite
for non-singular matrices with rational integral elements,

a fact suggesting the term ”Hermite form”. However,

lie:

of

III
IIIIIII-l
.[lfilll

 

 

 

 

MacDuffee provided an additional construction in the case
of singular matrices which gives a uniqge form in all
cases [4].

Lemma 2.1. A matrix A in 3n1n,p;13) is the left-
assoCiate of a matrix H having 0's above the main diagonal,
each diagonal element lying in a prescribed system of non-
associates, and each element below the main diagonal lying
in a prescribed residue system modulo the diagonal element
above it (where web mod 0 implies a=b). If a diagonal
element be 0, all the elements of its row can be made 0.
This form H is unique.

The Hermite form H of a matrix A is determined by two
sets of transformations.

First one operates on A column by column from right
to left to determine the diagonal elements of H. This is
essentially a process of finding unimodular matrices which
will transform a given column vector with elements
a1,...,aJ into the column vector 0,...0,h where the ideal
(a1,...,aj) is the principal ideal (h). This step can.be.
performed theoretically in any principal ideal ring, and
can be accomplished by elementary transformations in a
Euclidean ring [6,Th.22.5] -- for example, in [REL

Thus if A is in Wu,n; 13) (this is no restriction

since any rectangular matrix can be squared by adding

either rows or columns of 0's) and has the n-th column not
all 0, A.may be transformed so that column n consists
entirely of 0's except for Emaéo. In the new matrix
exclude the row n from consideration and transform so that
column n-l consists entirely of 0's except possibly for
hn-l,n-l'

But if column n of A is all 0, take hnn==03 then in
working with column n-l include the row n in the considera-
tion so that the transformed matrix may have hn,n-l==°'

By continued inclusion of the row n in the subsequent
finding of all diagOnal elements all the elements of row n
of H may be made 0.

The column-by-column application of these steps gives
the diagonal elements of H, gives 0's above the main.
diagonal, and rows of 0's whenever the corresponding
diagonal element is 0.

Secondly, one operates column-by-column from right to
left to reduce the elements below the main diagonal module
the diagonal element above. This may be done by elementary
transformations that do not affect the properties attained
by the first set of operations. Note that in case a
diagonal element is 0, the elements below must be left-
just as they happen to appear whenever the second set of
operations has been completed on the other columns of the

matrix.

For example, let A have elements in [Ra], where the
residue system may be prescribed to be 0 and the set of
positive integers less than the modulus. A succession Of
transformations from A to H is shown together with the

unimodular matrix P such that PA =H.

6210 6210 1600 1600 30-2
A: 3945-» 394544300» 000=H,P= 01-5.
1 s 15 -5 1 5 -s 1 5 11 1 5 2 O -1

To prove the uniqueness of the Hermite form, assume
that H can be the left-associate of another Hermite form
H', 1.0., that there exists a unimodular G such that GH=H'.
The properties of the Hermite form'are restrictive enough
to require that H=H', whereas G is revealed as the most
general unimodular matrix leaving H unaltered when used as
a left factor. The exact structure of G is as follows:

Let 1111an for i=s1,s2,...,sr; let h11=0 for
i=tl,t2,...,tn_r. Then the matrix G has as its columns
s1,s2,..,sr the unit vectors (83'1)’(83'2)'""(Sj'r);
while the columns tl,t2,...,tn_r are arbitrary, except

that the matrix G11 formed by deleting rows and columns
sl,s2,...,sr from G must be unimodular. Here r is the rank
of the matrix H. In particular, if H is non-singular, then
G=In.

The other canonical form due to H. J. S. Smith
[6,Th.26.2] is described in the following lemma.

Lemma 2.2. For any matrix A in m(n,p;l3) there
exist unimodular matrices U in 3114mm?) and V in
31?,(p,p;13) such that UAV=E has zero elements everywhere
except in the main diagonal where there may appear non-
zero elements e1,e2,...,er, (which are called invariant
factors and which are uniquely determined up to associates
in l3 ), having the property that e1 divides e1+1 and
either répén or rén<p.

If A is of rank r, the rows and columns can be
shifted by elementary transformations so that the minor
determinant of order r in the upper left corner is 75 0.
Then as in the proof of Lemma 2.1, the element in the
(1,1)-position can be made at 0 and a g.c.d. of the elements
of the first column. The elements of the first column
below the first row can then be made 0's by elementary
transformations on the rows. If the element which now
stands in the (1,l)-position divides every other element
of the first row, these other elements can all be made 0's
by elementary transformations on the columns so as not to
disturb the first column of 0's. If they are not all
divisible by this element 311' then all can be replaced by
the g.c.d. of the elements of the first row, and this g.c.d.

Ilullalfs‘xfillcl I. -
I fall... 1 .V .
1‘1 ,5.
til. i."

will contain fewer prime factors than “11' The process is
now repeated until an element in the (1,l)-position is
obtained which divides every other element of the first row
and every other element of the first column. Since every
number of F} is factorable into a finite number of primes,
this stage is reached in a finite number of steps.

By working with the last n-l rows and last p-l columns,
then with the last n-2 rows and last p-2 columns etc., A

can be reduced to the form

d1 0 0.. o

D O 0 d2 O
, where D= , and diaéo.
O M

00 ...ar

Now M==0, for if one element of M were not 0, it could be
shifted into the (r+l,r+1)-position, and A would have a
non-vanishing minor determinant of order r+l. .

By adding column 2, column 3,..., column r to column 1,

D is made to assume the form

aloo ...O
(d2d2o ...O~

d3 0 d3 ... O .

\qo 01,)

 

 

 

10

As in the proof of Lemma 2.1, there is a unimodular matrix
K which, used as a left factor, replaces (11 by the g.c.d.
of d1,d2,...,dr. The new matrix 1CD has every element a
homogeneous linear combination of dl’d2""'dr' so each
element of ED is divisible by the new d1. Again reduce to

the diagonal form

d1 o 0.. o

O d2...0

0 o .0. dr
where now d1 divides d2,d3,...,dT. Continue until d1
(ii-Vida. d1+1, 1:1,2'esogr'10
We illustrate this procedure with a matrix A with
elements in [9221], and give the unimodular matrices U and V.

(2413‘ {201
~O65 O21

A=006-’OOO-*OOO-*OOO—’OO4::E

2 -2 O 2 O O 1 0.0
f \ I I I

021 001 020'

 

 

 

 

 

 

 

 

 

 

 

 

002 002 0-40 000 000
'04 o} IOAOI IO 40/ I04OI IOOOI
o 10-1-1
1-10-50 Oll
U=0000 ,v=001.
001-: 10-2

(ROI-4

0-20 3

I a Iii-glut 1“. av

III it’ll-Till. Animal

 

 

 

5. Linear Equations in I}. Using matric notation a
new exposition of Smith's material is given in this and the
immediately suCceeding section. The results are easier to
state and the proofs are greatly simplified through the use
of Lemma 2.2.

The coefficients, constants, and moduli in the equa-
tions and congruences of sections 5, 4, and 5 are assumed
to be in a specified principal ideal ring D , such as the
rational domain. For the system of p linear equations in

n.unknowns represented by

n
E x1a13=k3, j=1s2900°sp3
i:

we will use the metric notation
(5.1) n=K’

where X is l-by-n, A is in SNXn,p313), and.K is in
Tnxl,p;¥3). We wish to determine when (5.1) has a solution
x in 31?,(1,n: )3), to find how many solutions there may be,
and to give a method for actually Obtaining the solution.
By Lemma 2.2 there exist unimodular matrices U in
m(n,n;13) and V in megp) such that UAV=B is the

Smith normal form with invariant factors °1'°2""’°r’

where e1 divides 01+]. and. either r‘épén or rén<p.

12

Hence the system (5.1) may be replaced by the equivalent
system (XUI)(UAV)=KV, so that by setting Y-—-=xuI and C=KV

we arrive at
(5.2) YET-C.

The system (5.2) is so simple that we can immediately
conclude that necessary and sufficient conditions for its

solvability are as follows:

(5.5) °i must divide °i’ i=1,2,...,r;
01: O, 1)!‘.

If we define A' =6?) as the augmented matrix of (5.1),

then using the conventional block notation we have

(2 3mm,

so that a further transformation by unimodular matrices U'
in Wn+l,n+l;p) and V' in Mp,p;l3)- will take A' into
its Smith normal form, say U'(§)V'=B', which is

in Wn+l,p;P) with the invariant factors e'l,s'2,....

If we use the block notation and write

E O

E l
= 0 0 ,
C

C’1 G2

‘. '
l"'*mim——5’0-——.—c—

I
3.! 'M-v .13

-—nb.——._

 

 

H
7' .
MOE.5.

13

°2
where‘El== ,

01 O ... 0
0 .0. o

 

0 O ... er]

cl: (C1,°2, ee o’er), 311d 02 =(cr+1,0r+2, o e o'cp)’

it is quite obvious that if the conditions (3.5) are
satisfied the Smith normal form of A' is

and let x and'Y be the inverses of U' and.V' respectively,

in block notation we have .

I‘1 0 x11 x1.2 3‘15 E1
0 _ o Yn YlZ
° - 1‘21 x22 x23 0 -
21 22
Cl 02 x31 x:52 3‘33 0

Performing the block multiplication on the right we obtain

l4

E1=x11E1Y1v °1=x3131Y1r °2=x31E1Y12' and

xnfl’fflz = x21ElYll= XZlElYlZ = 0 ’

From the first of these equations and a well known theorem

concerning determinants we have
det (E1) = det(x11)det(31)det(Y11) ;

which implies, since E1 is non-singular, that
det(xll)det(Y11) = 1. Now x11 and Y11 are in m(r,r;p),
so det(xll) and det(Y11) are in 13 . Hence set-4x11) and
detfill) are units of D and X11 and Y11 are unimodular,

.so that x111 and Y111 are in er; D). From the first
of the above equations we obtain E1Y11=xlllEP which we

substitute into the second to yield

__ I
01" xsixu E‘1'
Since 111 is unimodular and El is non-singular, it follows

from X11E1Y12=0 that Y12 must be 0; and, consequently that
02 =0.

Hence the conditions (5.5) are satisfied.

If we now agree that all the elements in the main
diagonal of E and E' are to be denoted by e1 and e'i,
respectively, and observe when pén that E and E‘ have p

elements in the main diagonal, and when n<p that E has n,

15

and E' has n+1 elements in the main diagonal, then depending
on the relative size of n and p, the conditions (5.5) may ‘
be replaced by the equivalent conditions:

IM

(5.4) p. n: e1==e'1, i==l,2,...,p;
n

(304') (P: 31: 9'1, 1=1,2,...,n; and

I _.
e n+l—O‘

Supposing that these necessary and sufficient condi-
tions are satisfied, we return to (5.2) and see that the
first r of the y's are determined uniquely by y1==c1/e1,
while the remaining n-r of the y's are arbitrary. The
complete solution of (5.1) is then given by XF=YU and
involves n-r parameters; but it is not necessarily the
unique expression for the general solution, since the

matrices U and V are not unique.

- ._ .-—_._. “—1-. ...—...._ ...—_,___~ ”A. A.
A:- — —- ...-p _ ——— _ a. H H.- 4..— fl

_-

I ..-

(4.1)

A'.’S“|‘. ‘-
“Ve A}.

(4.1')

Ofp 14..

«"5:

16

4. Linear Congruences in B . For the system of linear

congruences represented by

n
E 111313581 Rica (1113), 3:1D29"'9p;
1"].

we will use the matric notation

ml 0 ... 0

0 ... O
(4.1) XBEG mod 11', where M'= m2

0 0 ...mp

A matrix x in 311(me will be a solution of (4.1) if and
only if there exists a matrix T in m(1,p;p) such that

(4.2) XB+TM'=G.

Two solutions x and x' of (4.1) will be called congruent

 

if and only if XEX' mod ijn' for j=1,2,...,p. Another

system

n1 0 co. 0

o .0. o
(4.1') ZAEK mod N', where N'= n2

0 o
np

01’ p linear congruences in n unknowns will be called

 

 

--fiflgw

c-i._——‘

hm

,. .
:u-‘
10 n
a. bl

.e '
-.. v

f

0L6 .

I... .

""r

“#4..

l O

.
“'1:

..“.

Va.
N .

.t‘

cg“!

1?

equivalent to the system (4.1) if and only if there exists
a unimodular matrix Q, in mummfl) such that: if X1 is a
solution of (4.1), then zl=x1q is a solution of (4.1');
if 22 is a solution of (4.1'), then X2=22QI is a solution
of (4.1); if x1 and x2 are congruent solutions of (4.1),
then 21 and 22 are congruent solutions of (4.1'); and if
21 and 22 are congruent solutions of (4.1'), then x1 and X2
are congruent solutions of (4.1).

If m=[m1,m2,...,m.p] is the least common multiple of
the m3, and R is a diagonal matrix whose elements r.j are

such that m=mjrj, multiplication of the system (4.1) on
the right by R gives a system

(4.3) XAEK mod Mp,

where A=BR, K=GR, and Mp=mIp. This system is equivalent
to (4.1) since in the above definition we can choose Q=In3
and if XEX' mod ijn' J=l,2,...,p, that XEX' mod Mn, and
conversely, follows from the properties of the least common
multiple.

We shall now determine necessary and sufficient
conditions for the solvability of (4.5), the number of

incongruent solutions, and a method of obtaining the

solution.

The system (4.5) of congruences has a solution X

 

...---

 

—-..# h... -. ————. —.-— —_‘ ~_ -_ m— “w ._.—- “....

L.

“1". r0
0“ v3.,'.’

[I

u- dM‘L"

 

18

in 312(1,n;13) 1: and only if there exists a matrix T

in 3121me such that

which is an equivalent system of pl=p equations in

n1== n+p unknowns. Since pl( n1, we apply the test (5.4)
which requires us to compute the invariant factors of

(flip) and (fill) .. Fortunately this task is easy because of
the form of M . Following an argument which is more direct

P
then that used by Smith we write

U 0 A E
o v1 - M '
“p p

Because e1 divides e1+1, we see that no further rearrange-
ment of columns is necessary and that the i-th invariant
factor of (fip) is either (e1,m) when iépén, or is m when
n<1§pe 7 _
1

Similarly, for (:1 ) the i—th invariant, factor .is

P
(e'1,m) when iépén; but when n<P. the_(n+l)-st invariant

factor, is (e'n+l,m); and when n+l< iép, the i-th invariant
factor is m.

Hence the test (5.4) shows that the necessary and
sufficient conditions for the solution of (4.5) (and,

moreover, of (4.1)) are as follows:

A. ll." -'

 

‘Ufl- ~.. _ _——_ — -_ ———- .—._ _—_. ”1—— __.—.—-_.s__‘ ...-ow *—_

l_—

(305)

4:!
\‘03

.. 0‘

'5‘ :5»: U

I ‘Q
Q . :-
:t1

1

u: o

-.l ,.

3...“..-9“
,

a. ‘ F

3-1: ' v

(4.7)

It }
‘13-‘11 '3.
1111:.”I +

V‘,".l,.-
h“. n
"r.."

356 the:
13 a 53;"

I
95“

19

(4.5) Pén: (319m)=(°'19m)o 1:112: 0 ' 'op3
(4.5') n<p: (e1,m)=(e'1,m), i=1,2,...,n; and
m—(e'n+l,m).

We note that the final condition in (4.5') may be written
°'n+lEO mod m, in close analogy with (5.4').

As in section 5, we replace the system (4.4) by the

equivalent system (XUI)UAV+TM V=KV, so that by setting

P

Y=XUI, C=KV, and T'=TV, (MpV=VM.p since M is a scalar

P
matrix), we obtain

(4.6) YE+T'MP=C,
which can be written as the following system of congruences,

(4.7) YEEC mod Mp.

If X1 is a solution of (4.5), then there exists a

matrix T1 such that X1A+T1M =K. Since A=UIEVI we have

P

I I _ . .. I u =
multiplying on the right by V we obtain Y1K +T'1Mp=c and
see that Y1 is a solution of (4.7). If we assume that Y1
is a solution of (4.7) we can reverse the above steps to
show that xl=Y1U is a solution of (4.5). If x1 and X2 are
two congruent solutions of ( 4.5) there must exist a matrix
w in Mlfi‘up) such that xl-x2= wmn. Multiplying on the

right by UI we have xlUI-XZUI=WUIMn. This last equation

 

 

 

 

2O

' __ I
shows that Yl— X10

and Y2=X2UI are congruent solutions of
(4.7). If we let Y1 and Y2 be congruent solutions of (4.7)
and reverse the preceding steps we easily obtain that x1
and x2 are congruent solutions of (4.5). This establishes
the equivalence of the systems (4.5) and (4.7).

From (4.7) we see that the first r of the y's are
determined by congruences of the form yieiaci mod m.
From properties of D we know there are as many solutions
yi which are incongruent mod m as there are residue classes
of ’43 , mod (ei,m). The remaining y's are arbitrary, so for
each of these there are as many solutions incongruent mod m
as there are residue classes of 13, mod m. The general
solution of (4.5) and of (4.1) is given explicitly by
KEN mod Mn. .

In particular, when p is the domain of rational

integers, the above considerations show that there are

exactly

N a (e1,m) ( e2,m) . . .(er,m)mn'r

distinct solutions of (4.1).
For an example we take 13 to be the rational integers

and consider the system

5x1+5x2=l.

21

Using the notation of the preceding sections, we have

(0 1) (a 5)(1 5) (1 o)
UAv= = =8,
1 -3 1 5 o -1 o 4

1 3
KV=(5 1) ( )= (5 14)=c,

o -1

1 O O 1 0 10
U'(§)= -5 -5 l O 4 = 0 2 =E'.
10 '7 -2 5 14 00

Since 4=e2¢e'2=2, it follows from (5.4) that the
system has no solution in rational integers.

Considering the same system mod M2, we see from (4.5)
that we must have (l,m)=(l,m) and (4,m)=(2.,m). If
mEO mod 4, there are no solutions; if mEl or 5 mod 4,
there will be N=1 solution; and, if mEZ mod 4, there will
be N=2 solutions. .

Thus if m=10, we solve yl-‘E5, 4y2514, for ylE5,
yzslg and y1§ 5, y256. Then from X=YU, we compute
x151, x252; and x126, 57, respectively.

22

5. A Mixed System in 13 . We are now going to exhibit
a procedure for solving a mixed system of equations and
congruences in 13 . This was not considered by Smith but
we shall have occasion to refer to it in the sequel, and
it is included at this point since the system is in a
principal ideal ring. F

In the matric notation of the preceding sections ,o

(5.1) ‘ n1: K1 and 4
' =

where X is 1-by-n, A1 is in m(n,p1«;p), A2 is in

Wimpy)“. K1 is in ml.pl;13), K2 is in m(1,p2;13),

and Hp2=mI , represent, respectively, a system of p1

P2
equations in n unknowns of the type (5.1) and a system of

 

p2 congruences in n unknowns of the type (4.5). Since we
are concerned to find all solutions common to both systems
we regard the former as a system of congruences each mod 0,
and letting p=pl+ p2, A=(A1 12), K==(K1 K2), and i=(o Mp2)

we can write
(5.2) XAEK mod if.

This system will have a solution if and only if there exists
a matrix T in Wlmzflp) satisfying

 

23

which is a system of p equations in n-rpz unknowns. We
apply the test (5.4) to the coefficient matrix (g) and the
augmented matrix (£4) to determine whether or not (5.5) has
a solution. Due to the form of M the invariant factors are
not as simply expressed as in section 4.

Assuming the conditions of (5.4) are met we proceed to
determine the common solutions of (5.1) and (5.1').
Letting UlA v =31 with rank r1, Y=XUll, and c =K v

11 l 11’
and proceeding as in section 5 we find that yl,y2,...,yr
1

are uniquely determined, yrl+l,yr1+2,...,yn are arbitrary,

andx==YU1 is the general solution of (5.1). We set

U1.

Y'=(.Y1:Y230°Uyr )' Y" =(yr +1’yr +2""’yn)’ and 01: '
1 1 1 U1”
where Ul‘ has rl rows; and since X is to be also a solution

of (5.1') we now consider

Since y1,y2,...,yr1 are uniquely determined, we let
w__ a w== _,I u
A2 -U1A2 andK2 KZYUlAzand write

(5.4) Y"A "Z—K " mod M ,
2
2 p2

which is a system of p2 congruences in n-r1 unknowns of the
type (4.5). Letting U2A2"V2==32 with rank r2 and invariant

factors e1, Z=Y"UZI, and 02 =K2'V2 we proceed as in section

4 andrfind.that zl,z2,...,zr are determined by congruences
2

«Nuts—....”
'.

 

24

of the type zieiaci mod m, Zr2+l'zr2+2""'zn-rl are. :
arbitrary and ”1"5202 mod Mp2 is the general solution of

(5.4). Then the general solution of (5.1) and (5.1') is

given by x=(Y'U1'+Y“U1') where Y"EZU2 mod Mp2.

Since (5.4) is a system of congruences of the type

(4.5), the discussion in section 4 concerning the number
of incongruent solutions of (4.5) can be applied directly
to (5.4). In particular, if 13 is [Ra], we note that the

number of incongruent solutions of (5.4) is
N =(el,m) ( 62,111) . . .(er2,m) mn-rl-rz.

We now agree that two common solutions it and x of (5.1) and

(5.1') are to be considered congruent when
(5.5) its-3x mod Mn.

Let x=Y'U1'+Y'U1' and X=Y'U1'+Y"U1* be two congruent
solutions of (5.1) and (5.1'). Then there must exist a
T in Ml,n;p) so that

(5.6) Tmn=2 - X=Y”U1" - Y”U1".

I__ w _.
Let U1 --(L1 L2) so that U1 L2—1n_r1. Then multiplication

of (5.6) on the right by L2 gives

Y" ' Y"=TMnL2=TL2Mn_r1=WMn_rl,

 

25

where W=TL2 is in MLn-rfin), which implies that Y”
and Y" are congruent solutions of (5.4). Conversely, if
we assume that I?“ and Y" are congruent solutions of (5.4),
then there exists a matrix w in MLn-rvp) so that
(5.7) Y" - y"=wmn_rl.

Multiplication of (5.7) on the right by U" gives

wn_uw= n=w=«
TU YU “Mn-r1” wumn Thn

where T=WU" is in Manp). Then
TMn=Y"U" - Y"U" =(Y'U1'+Y"U”) - (Y'U1'+Y'U')=X - x,

and X and X are congruent solutions of (5.1) and (5.1').
Hence the number of incongruent solutions of (5.1) and (5.1')
is the same as the number of incongruent solutions of (5.4).

As an example, we consider (5.2) when

2264
x=(x1x2x5)‘, a= O 66 ,
0120

_ 04o
K=(488), and M: .
’ 004

Since the invariant factors of (g) are e1: 2, e2=2, e3=4

 

26

3
- and of (3%) are e'1=2, e'2=2, e'5==4 we are assured that
solutions exist. Since (5.1) is 2x1=4 we have immediately
(2 x2 13) is the general solution. For this to be also a

solution of (5.1') requires

26 4 -
4 0
(2x x) 6 6 E(88)mod ,
2 5 O 4
12 0

which gives 6x2+l2x350 mod 4, 6x250 mod 4. Hence we

have x250 mod 2 and x:5 is arbitrary, and the general

common solution is given by

x1: 2,

1 E0 mod 2,

2

x3 arbitrary.

We remark that there are N=2-4=8 incongruent solutions.

 

f.".

w“

._ in
'-

UN

 

 

27

6. Integral Elements and Regular Representations.
Our immediate goal is the extension of Smith's results to
a mathematical system more general than a principal ideal.
ring. In this section this system is defined, and,
following the terminology of MacDuffee [5], it is called
a 'set of integral elements”. Also, the first and second 1'
regular representations of an integral element are described; (
and an intertwining relationship between the two which
will be extremely useful is observed. a

An algebra {21; over a field 17" is a mathematical system
composed of more than one element, an equals relation, and
three operations,+ , x, and 0 , under which the set of
elements is closed. The operation a , called scalar
multiplication, may be performed on any number a of J:
and any element cc of 2C to produce a unique element aooC,
called the scalar product, which for simplicity we write
as aac . It is assumed to satisfy aaC=eca, s(boc.)=(ab)eC,
(aoC)(b/3)=(ab)(o<6), (a+b)o<== aoc+bOC, and
a(o(+fl)=ao<+afi . The operation + , called addition, is
commutative and associative. The operation X , called
multiplication, is assumed to satisfy oc(/3+))= OCfl-toq,
(fl +U)a( =floC+BoC. If multiplication is associative, 2C
is called an associative algebra. If it contains an ele-

ment 6 such that oce=eoc=oc for all oc in M, then 6. is

 

28

called a modulus.

We now let M be an associative algebra, with a
modulus E , defined over a field I]: ; and we assume that 13
is a principal ideal ring contained in {F . Then each
element of a set E of (elements of 21: will be called an
integral element if the set has the following three

properties:

C(closure): the set is closed under addition,
subtraction, and multiplication;

U(unity): the set contains the modulus é;
B(finite basis): the set contains elements
€1=6,€2,...,6k such that every element of the set is
expressed uniquely in the form Zaiéi, where each a1

is in 3p . '

As an example we may take k=1 and obtain as 6 the
ring )3 itself. Again when 1? is the rational field and D
the rational domain, we see that 6 is a set of integral
elements (but not necessarily a maximal set) in the sense

01‘ L. E. Dickson [1].

k
If OC=E a1€1 is any element of G, by properties
1‘].

C and B there must exist elements rtj and sjt of I3

such that

 

 

 

 

 

 

 

29

0<€J=(Za1€1)63=:rtj€t, . j=l,2,...,k; a
éjoc=€J(Za1€1)=Zth€t, j=l,2,...,k.

Hence with each oCin (‘5’ there are associated matrices
R<oc)=<rtj) and stone“) in muses).
If E”. indicates the l-by-k matrix with elements 9.

E €2”°"€k’ then in matric notation we have

1’

(6.1) ocE*=E*R(oc), E*To<=3(oC)E*T.

tr'mr-r“ - .

Since 61=€, the first column of 1201) and the first
row of S(oC) consist of precisely the elements a1,a2,...,ak.
Then from property B it follows that the correspondences

defined by (6.1) are both one-to-one. Since

3*T(oc+fi)=s*Toc+s*Tfi = 8(d)E*T+3(fi )E*T=(s(oo+s(f3 HE“.
E*T(oC/3) =(E*Toos = (smiths = 8(oC)(E*Tfi)
=s<oo(s(mE*T)=<s<oos(mm“.

and since the second correspondence in (6.1) is one-to-one
it follows that S(oC+fi)=S(oC)+S(/3) and S(oC/3)=S(oC)S(5).
In an analogous manner it is easily shown that the first
correspondence in (6.1) is also preserved under both addition
and multiplication. Hence the matrices Md) and the
matrices 5(OC) provide isomorphic representations for 6,
well-known, respectively, as the first and second regular

representations.

50

If 0C and 6 are in G; , we may use (6.1) and the fact I

that elements of 39 commits with elements of 6 to write

RTecm a )E“=RT(<><)E*T£ = (s*a(oc)>Tp = anhTs = henna/3
=(oc1k)8(£3)E*T=3(fi)(ocIk)E*T=8(/J’)(o<B*)T
=s(/3)(E*R(oo)T—.=s(mathm‘T; ‘

then from property B, it follows that, [5]: 5
T _. T _
R (ot)S(.fl)—S(fl)R (at).

In particular, letting A=(al,a2,...,ak) and
B=(b1,b2,...,bk) be the first rows of RT(oC) and s(fi ),

respectively, we obtain the useful relation

(6.2) as(/3)=BRT(oc)o

 

31

7. Systems of Linear Equations over g. We are now
going to extend the material in section 5, and we consider

the following system of p linear equations in n unknowns:

n
(701) 20(1in flij=Kjo J=li2l°°09p3
181

where the cc”, 613, and K1 are given elements of C6.
Since 6 is not necessarily commutative, note that
coefficients are allowed on both sides of the unknowns.
We are concerned to establish necessary and sufficient
conditions that (7.1) have solutions 7(=(7£1, 12,..., Kn)
1n Ml,n;C§).

If we assume that such solutions exist, we may write
X1=Zx13€r where the x” are in 13 , and define
X1 =(1119x129000011k)e Supposing Kj=ZkJi€P we define
x3 =(k31,k12,...,k3k). we define A13 to be the first row
01‘ 8(ocij). Then (6.2) and (7.1) imply that

EFT=ZA1FT 7‘1 611‘2‘13“ 7‘1"“ 613"“
=insT(o<1.J)s( dun“.

Hence property B, implies that

T .
KJ=ZX1R (%3)3(fi13)s j=1s290009P0

 

32

we set K=(K1,K2,...,Kp), x=(x1,x2,...,xn), and.
A=(RT(OC13)S( [313”, where K is in Mlmmfi), X is in
minim), and the "enlarged coefficient matrix” A is in
Mampkdl) and is made up of k-by-k blocks of which the
one in the (i,j)-position is RT(OC11)S( fl”). Then the
equations obtained above may be written as the single matric

equation
(7 .2) XA=K.

Except for the size of the matrices involved, (7.2) is
precisely a system of the classical type (5.1) with kp
equations in kn unknowns, with the elements involved all
in p .
Conversely, if (7.2) has a solution x in 13 , we can
' retrace the steps above to obtain in g a solution of (7.1).
Thus the problem of solving (7.1) in 6 has been shown
e(3.11.:1valent to solving (7.2) in B. Referring to (5.4) and
(3-4‘) we can assert that if e1,e2,... are the invariant
f8“tors of A and if e'1,e'2,... are the invariant factors
of the augmented matrix (Q), then necessary and sufficient
°°nditions that the system (7.1) have a solution are that

(7.3) pén: 61:6.1, 1-1,2'eee‘kp;
(7.3.) n<p: 61:6.1, 1:1,2'eeegh1; and

e'kn+1=00

33

Determining the number of solutions and the most
general solution proceeds along the lines given in section 5.
In these matters it is worth a word of caution that the rank
of A need not be a multiple of k.

Letting 1F be the rational field and 13 the rational '
domain, we consider the algebra it having as a basis
€l=6,62,€3 with 6262:62, €352=5y and 62£3=€3€5=0.

If we take as @5 the set of all oc=a1€1+a2€2+a563 where

a1,a2, and a3 are in {3 , we have a set of integral elements

with the basis 51, 62'65‘ Using (6.1) we find

a1 a2 a:5 a1 a2 a3
RT (0C): 0 a1+a2 a3 , s(oc)= O a1+a2 O .
C 0 a1 0 0 a1+a2 .

AB an example, we study
can a ‘= K,

When oC=(5 5 1m“. f3=(1 5 2m“. (and K45 3° 0’3“?

an(Elfind
361 152 55312
A=RT(oc)s(,6)= 061 060 = 056 6 ,
005 006 0018

‘2' ‘” ‘10.: in" 1 “fans..."

54

1 00 55312 1-4 --15 5'0 0

oav=010 0566 00-1=-06 o=s,

0-3 1 0 0 la 0 1 6 0 0 106

)
(1-4

 

KV=(6 50 0) 0 0 -1 =(6 ~24 -1oa)=c,
0 1 6
1000 {5 0 o\ 60 0
s 0100 0 6 0 06 0
U.(C)V'= IS: =EI.
0 o 1 0 0 0 108 0 o 108
-2 4 1 11 \6 ~24 -1os I 0 0 o

 

 

Since 61:6'1,1==1,2,3, a solution exists; and, moreover,

Since r=p==5 it is a unique solution. Since (5.2) is

3 0 o
(y1 y2 ya) 0 6 o = (6 -24 -108),
0 0 108

I

We obtain (yl y2 y3)=(2 -4 -l); and hence the desired
°°lution in 13 is

1 0.0.
(x1x2x3)=(2 -4-1) 0 10 =(2 -l -1).
0-51

So the unique solution in g 18 x=251'62'65'

35

We note that one type of matric equation, well-known
in the literature, is included in the above discussion.
Let the algebra ’21: be the total matric algebra Wmnm'F)
and the set of integral elements S be the total matric
algebra m(n,n;13). The matrices 213 of Wn,n;13), where

has 1 in the (i,J)-position and 0's elsewhere, and

213
when y=i, form a natural

2 Z isOwhen iandZ
xy 13 yet x3

basis for m(n,n;p). If

/

Ex- =(le, e e .,Z1n3Z21, e o 0,2211; 0 0 032111, 0 ° 'Iznn)9

it follows from (6.1) and the relation 2113:; bszix
that the typical element figE b132,"1 in 31?,(n,n;13),

Which we ordinarily represent as B =(b13) , has the regular

representations
R(fi)=In-XB, s(f3)=B'XIn,

where AoXB indicates the direct product matrix in
Wn2,n2;3p) whose (i,J)-block is Ab“. Then a linear
e(luaition like 0( X. fl=X is replaced, according to the
theory above for passing from (7.1) to (7.2), by an

equation x'D'=c' , where

D'= RT(o<)s( fl)=(InoXA)T(B-X1n)= s-xsT,

X' is l-by--n2 and is obtained from x=(xu) by taking
row blocks, and C' is in Mungp) and is obtained

56

from C==(°ij) by taking row blocks. The general linear
equation in one unknown 2 (Xi X/J’1= ‘0 may be treated in

the same manner, the enlarged coefficient matrix being

w_§ T
D - Bi 'XAi 0

This is the ,nivellatenr studied by Sylvester [15], however,
only for the case 13= \F.

Similarly, the system of equations (7.1) may be
generalized to allow each unlmown to appear in a finite
number of summands in each equation; the technique for
passing to (7.2) remains the same, except each component
block of the enlarged coefficient matrix will now be a
sum of matrices of the type RT(O(U)S( (1’13).

If 21: is a non-commutative field and (7.1) is a one-
sided system, then if a solution of (7.1) existsin «2J2
it can be found by an elimination process somewhat
analogous to that employed in the classical case -- i.e.,
in solving a linear system over a commutative field. This
result is due to Ore [7] , who, by introducing a new
definition of determinants in a non-commutative field,
determined that elimination between linear systems can be
performed in all rings for which a quotient field can
exist. If a ring has a quotient field, however, it must

contain no divisors of 0. Since 6 may contain divisors

57

of 0 and (7.1) may be two-sided, the results in this
section can be employed to solve linear systems that could
not be solved by the elimination process of Ore. Moreover,
our results determine whether the solution is in. 65

itself, not just in some suitable extension of GS.

38

8. Minimal Bases for Ideals in E . In the usual
manner the left ideal m generated by Q1, §2""’ gt’ a
given set of elements of 6, is defined to be the set of

elements

t
ZVi gi

obtained by allowing the left-multipliers V1 to vary
independently over all of @3 . A minimal basis for the
ideal m is by definition a set of elements #1, H2""' H8
such that an element of (5 is in the ideal mn- and only

if it can be represented in the form

Zciui

. i=1

where the c1 are in p ; and this representation is to be
unique.

An argument by MacDuffee [5] shows that if H is the
uniquely determined left-Hermite form, described in

{M §1)\

3‘ S2)

Lemma 2.1, of the matrix

S:

(8(a)!

 

 

I"!

39

then the non-zero rows H1 of H determine a minimal basis
for m, having sé k, by the relation “1:133“. The
notation which we have been using makes it simple to
reproduce the proof.

Let U be a unimodular‘matrix in Wkt,kt;p) such that
US==H. Let V=UI, so that s=vs. If the i-th row of U is

divided into l-by-k blocks U13, then

_. _ T__ T _

where V11=nga is in g; hence M1 is in the ideal m,
and so are all E 01 #1.

Conversely, given any element 11:2 V1 S1 in the
ideal, we have V1=E nijéj and if we define

N1=(n11,n12,...,n1k) we can write V1=N1£§T. Hence
y =ZN1VT§1=ZN1M Si)l:"T=wsr'*T=1ws1:‘*T=2:c1 #1

where N is in m(l,kt;13) and is made up of the l-by-k
blocks N1, and where c1 is the element in the i-th column
of NV. Since °i is in p , a representation of the desired
type for V has been found. The uniqueness of the
representation follows from the independence of the non-
zero rows in the canonical left-Hermite form H.

In an analogous way we define the right-ideal
generated by g1, g2..." gt to be the set of elements

40

261721

obtained by allowing the right-multipliers >71 to vary
independently over ('5 . In this case a minimal basis can

be found by computing the left-Hermite form D of the matrix
T

(R «w
T

R ($2)

\RT‘ st)!

in 311(kt,k;)3); for if D1,D2,...,Dr are the non-zero rows

 

 

of D, necessarily with rék, the elements SJ=DJE*T serve
as [a minimal basis.

By combining these operations we can find a minimal
basis for the two-sided ideal generated by £1, £2...” St,
whose typical element is

where the qi are 'all finite. For we may first compute a

minimal basis #1, #2,..., MB for the left-ideal generated
by S1, S2""' gt and replace each V13 Q1 by

Z °ijm um:

m=l

4 1
Then

a {M

m-l

t q
77111:; Z: °ijm7713°

Hence if, secondly, we compute a minimal basis

where

81, 62...” SI, for the right ideal generated by
#1, [12,..., [18 we will have arrived at a suitable minimal
basis 51, 52,..., 8r for the two-sided ideal generated by
$1, swung?
However, not every matrix H in left-Hermite form
represents a minimal basis for an ideal of g [5].
Ford and fl in g , by the notation

OCEfl modm

we mean that oC-fl is in the ideal 912, and we say that o(
and fl are in the same residue class mod m. For the next
section, it is important to notice that, in general, it is
only when the ideal 312. is two-sided that multiplication of
residue classes mod m is well-defined.

As an example we take (£5 to be the set defined in
section 7 and compute the minimal basis for the two-sided '

ideal generated by 3 =4€2+6€3.

046

Since S(‘6) = 0 4 O has the Hermite form

004

42

000
040
002

we note that a basis for the left ideal (75] is “1:462,

RT( (11)
(.12: 263. Next we find .
RT( “2)

000‘
000
000

Hermite form
' O O O

040
\002}

basis is 61:462, 62:426.!”

 

 

/

 

\

040
...\
000
002
002

 

000}

has the

, and conclude that the desired

43

9. gyptems of Linear Congruences Module Ideals over Ci.
With the necessary preliminary remarks concerning ideals
and minimal bases stated in section 8, we are now ready
to consider over @ the following system of p linear con-

gruences, modulo ideals of 6 , in n unknowns:

n
(901) 2 £13 X1 flij '2 K1 mad m3, 3:1'2geee,pe
i=1

We will assume as explained in section 8 that for the
ideal m1 whether it be left, right, or two-sided, a
minimal basis of sJ elements has been found, say
(113, Hernausjj, given by M11=H113*T where the H“
are non-zero rows of a left-Hermite matrix in Mk,k;p).
We let H.1 be the matrix in marina) with rows 31: (this
33 is what is sometimes called the "echelon row form”).
Then X1, X2,..., Xn is a solution of (9.1) in

Ml,n;6) if and only if there exist elmnents t1: in ‘3
satisfying

n 8
(9.2) Edijxiflij+ztijuij=xj, 3:1,2,eee'pe

Supposing that X1, X2""'Xn is a solution of (9.1),
that all the ideals 31?.) are two-sided, and that

44

(903) 701 5X1 mOd m3: 1:192:00091'13 3:192:0009133

then 701, 702..." 7011 also solves (9.1). But if one
or more of the ideals m3 is one-sided, (9.5). is no
longer sufficient to guarantee that 701, 1'2"... 7L'n
is a solution of (9.1). Having given these words. of
caution, we now define sets of solutions of (9.1) which
satisfy (9.5) to be congruent sets. Two solutions of
(9.1) which do not satisfy (9.5) are called incongruent.
As in section 7 we let X1=XiE'T, KJ=KJE*T, A13
be the first row of s(ocij), and T 5 be the matrix
(tlj,t25,...,tsjj) in m(.1,sj;13). Then (6.2) and (9.2)

1mp 1y that

JEg-T: *T
2:113?"r X1513+T3nfj
-.- 2 113m xim £19195 T 31113“
*T

=ZX1RT (C(13)3(fl13)E*T+TJHEj .

Hexloo property B implies that
(9.4) KJ=§ :xisT (d H)S(/313)+T s j==l,2,...,p.

we Set K=(K1,K2,eee'Kp)' x=(xlng,eee,&)'
T =(T1.T2.....Tp). A=(RT(0(13)3(513)L and

H r H14- 62 4'- . . . Lap, where A-‘t s _ denotes the. direct sum

A 0
matrix

) . Then the equations (9.4) can be
0 B

45

written as the single matric equation
(9.5) XA+TH=K.

We now write

(9.6) XAEK mod H,

and agree that x=(x1,x2,...,xn) is a solution of (9.6)
if and only if there exists a matrix T in m(l,s;13)
satisfying (9.5), where s =2 s3. Following the
development of section 4 we call two solutions X and X'

°r (9.6) congruent if and only if
(9.7) X'Ex mod (HJ'XIn). J=1,2,...,p.

TWO solutions of (9.6) which do not satisfy (9.7) are
called incongruent.

Now if X1, X2,..., Xn is a solution of (9.1), and
X1=X1E*T, then x=(x1,x2,...,xn) is a solution of (9.6).
Conversely, if x=(x1,x2,....,xn) is a solution of (9.6),
a111cc the steps leading from (9.1) to (9.6) are reversible,
it follows that X1, 12"... 7(n is a solution of (9.1).
Letting X1, 12"”, Kn and 701, 702“”, 7011 be two
c"Zingruent solutions of (9.1), (9.5) requires the existence

or elements wrj in (3 such that

46

s
701 " 701::er urj'

r=l

which can be written as

'1‘ T T
X'iE‘ "' X1? :2 erHrjE" e

Letting WJ=(wlj,w23,...,wa 1), from property 8 we have
.1 .
X'1 - X1=WJHJ, i=1,2,...,n; j=l,2,. ..,p;

which, by (9.7), means that x and x' are congrumt
80liltions of (9.6). Since these steps are reversible,
‘70 can conclude that the problem of solving the system
01’ congruences (9.1) in @5 is resolved if we solve the
8Iratem of congruences (9.6) in D .

Since the system of congruences (9.6) is equivalent
to the system of equations (9.5), we write ( 9.5) in the
form (X T) (£)=K, which is a system of pk equations in
n-k-t-s unknowns. If pkénk+s, we apply (5.4) toobtain

the necessary and sufficient conditions

" A
(9.8) A = (K), i=1,2'eee, ks
°i(H) °i H w P

If nk+s<pk, we apply (5.4') to obtain the necessary and

sufficient conditions

47

A' .
(9.8.) 01(1Ai)=°1 K), i=1,2,...nk+8; and
H

 

A
61(K)=0 for i=nk+ s+l.
H

Thus (9.8) and (9.8') represent necessary and sufficient
conditions for the solution of (9.6), and of (9.1).

The solution of ( 9.6) may be obtained by solving the
BYBtem of equations (9.5) by the method of section 5; and
for each solution (X T) of (9.5) so obtained, x will be a
solution of (9.6). This procedure, however, involves the
additional parameters ti); so we now describe an alterna-
tive method which does not involve the tij and is analogous
to the procedure of section 4.

Let P be a unimodular matrix in Mayer?) and Q1

:1
be a unimodular matrix in 311(k,k;13) such that PJHJQJ=DJ

13 the Smith normal form of H3. Since H has rank 3 ék,

J 3

DJ has- the form

dlj o .0. o O .0. o
o 621 0.. 0 O .0. o

0 0 ... d 0 ... 0

3J3

Let m be the 1.06m. Of dij, i=1,2,ooo,33' i=1,2’000'p;

48

and let m=dijrij. Denote by R3 the non-singular diagonal
matrix in Wik,k;)3) whose i-th diagonal element is rij
for iésj, and 1 for sj<i=<=k. Then DjRJ has the form

(M$3 0), where Msjzmlsj. Letting P=r14p24 ...s'Lpp,
Q=Q1+Q2+...+Qp, D=D1+D2+...+Dp, and

R‘==R1-3- R24...-(-Rp; we note that P and Q are unimodular, and
PHQ=D. We let RXR'G where G is a permutation matrix so
that DR has the form (M3 0) where Mszzzmls. Multiplication of

the system of equations (9.5) on the right by QR gives
XAQR+TPIPHQR=KQR;

so that by setting X=AQR, T=TPI, Reach, and

M =PHQ£=DR=(M8 0) we have
(9.9) XI+TE=L

We now write

(9.10) xii-7K mod ii;

and, as usual, we agree that (9.10) has a solution X if
84'16. only if there exists a matrix T in (”141,833) satis-
rYing (9.9). The system (9.10) is a mixed system of
kD-s equations and s congruences of precisely the type

ccJrlsidered in section 5, and may be solved by the method

described in that section.

49

Since the steps leading from (9.6) to (9.10) are
reversible, it follows that any solution of (9.6) is a
solution of (9.10), and conversely. However, as will'be
illustrated by examples, two solutions X' and X may be
congruent solutions of one system and incongruent solu-
tions of the other.

In the particular case when sjzk, j==l,2,...,p,
131RJ =mk=m1k, M=DR=Mkp=mIkp and (9.10) is a system
of kp congruences of the type (4.5). Since D5 and R.1
are diagonal matrices it follows that DJR‘1 =RJD 3' Also
MkQJI=QJIMk since Mk is a scalar matrix. It now follows
from Mk= DJR3= RJDJ=RJPJHJQJ that QJIMk=RJPjHJ. If new
x' and X are congruent solutions of (9.10) it is necessary

that a matrix T in 312(1,kn;)3) exists such that
X' " x=TMm,

= , h
where Mkn mIkn T on

x' - x=Tu1m
=T(MkoXIn )
=T(QJ'XIn Haj: 0X1 n’mr'fln )
=T(QJ-XIn)(QJIuk-x1n )
=T(QJ-XIn)(RJP J HJ-xln)
=T(Q,j .XIn) (RJPJ .xIn) (HJ .XIn)
=T(QJRJPj-X1n) (Iij ~x1n).

5O

Denoting T(QJRJPJ-X1n) which is in 012(1,kn;13) by wJ,

we have

X. - X=WJ(HJ KID), . I it‘ll-9290009133

which are precisely the conditions (9.7) that x' and X
be congruent solutions of (9.6). Hence when s=kp all the
desired incongruent solutions of (9.6) are found among
the incongruent solutions of (9.10)). However, the two
systems are not equivalent, because two incongruent
solutions of (9.10) may be congruent solutions of (9.6).
We remark that when 3D= [R0,], if the rank of I is r and
UIv=s is the smith form of I with invariant factors 61,
then the number if of incongruent solutions of (9.6) is
such that fié(el,m)(62,m)...(ei‘,m)mlm-r. When s<kp,
it is even possible that two congruent solutions of (9.10)
are incongruent solutions of (9.6)..

We observe that the conditions (9.7) for two solutions
x' and x of (9.6) to be congruent imply that x' - x is a
common left multiple of the 3;) oXIn. By repeated applica-
tion of the method described in [11] there is a construc-

tive way of finding HL’ the l.c.l.m. of HI'HZ””'Hp

Then HL°XIn 15 the 1.0.1.311. of Hl’XIngfiz'XIngeee'Hp.XIn;
and, if HI. is in say 312.(6L,k;13), the conditions (9.7) are
equivalent to the existence ofa matrix W in m(l,nsL;p)

51

such that
(9.11) x' - x=w(HLoXIn).

Then for any two particular solutions x' and X, (9.11) is
a system of equations of the type (5.1). Hence to
determine if X' and X are congruent we may apply (5.4)
and (5.4') to obtain conditions expressed in terms of
HL’XIn
the invariant factors of (HL-XIn) and .
X' - X
We take 6 to be the same set of integral elements

described in section 7, and as the first example study

(9.12) 00(6 5K mod (5]
(9.13) o( yams/(mod [5).

when oC=(5 s l)s*T, /3=(l 5 as“, K=(o 0 2)E*T,
3":(6 2 l2)E*T, and where (5] and [5) indicate, respec-
tively, the left and right ideals generated by 7!.

We compute:

 

f‘ 551 152 55512‘
RT(0()S(fl)= 061 060 = 056 6=A:
005 006 00191
100 55512 1-4-15 50 01

UAV=010 0366 00-1

06 O(=E;
0 -s 1 0 0 18 0 1 6 0 0 1061

 

52

1 -4 -15
KV=(O 0 2) 0 0 -1 =(0 2 12)=C;

0 l 6
6 2 12 6 2 12
sm=oeo :RT(25)=0812 ;
0 0 8 0 0 6
’24 0 0\\
H = 12 4 0 , the left-Hermite form of 8(5); and
6 2 4
24 0 0
G -_= 6 2 0 , the left-Hermite form of RT“).
0 0 6

Next, by the method of Lemma 2.2, we find the invariant
factors of (g) are e1=l,e2=2,e3=l2; the invariant
factors of (3.) are e'l=l,e'2=2,e'3=12; and we conclude
by (9.8) that solutions of (9.12).exist. Similarly we
find the invariant factors of (a) are e1=l,e2=6,e5 =12;
the invariant factors of (3') are e'1= l,e'2-2,e'3=12;
and we conclude by (9.8) that there is no solution to
(9.15).

The solution of (9.12) will now be obtained using
the method and notation of this section. The system

0 ,,'-

 

55

(9.6) for this example is

5 55 12 . 24 0 0
(111215) 0566 ‘-_"-:'(002)mod 1240 o
0 0 18 6 2 4

Upon computing

001 2400 00-1 200
PHQ\=01-2 1240 12-6=060=D,
100 624 0-10 0024

1200
a: 050 ,
001

5 55 12 0 0 1 ' 12 0 0 596 162 ~96
AQR= 066 6 1 2-5 O50=452198-108 =I,
0 0 16 0 -1 0 0 0 l 0 -54 0

001 1200
KQR=(OO2) 1 2-5 050 =(0 -60)==K,
0-10 001

200 1200 2400
DR=060 050 = 0240=H,
0024 001 0024

54

(9.10) for this example is found to be

696 162 -96 24 0 0
(x1 x2 x3) ’462 196 ~106 =3. (0 ~6 0) mod 0 24 0 ,
0 ~54 ‘ 0 . 0 0 24

a system of the type (4.5). Proceeding as in section 4

we find
1 1 7 696 162 -96 2 ~6 6 6 0 0
UIv= 6 4 25 462196-106 1 -2-6 = 066 0 =6,
0 ~6 ~11 0 ~54 o 6 ~12 66 0 0 624
61 ~10 ~6
UI == 66 ~11 ~4 ,
-9 6 1
2 ~6 6
iv=(o ~6 0) l -2 ~6 = (-6 12 66)=5;
6 ~12 66

and letting YBXUI the system (4.7) is

6 0 0 24 0 0
(y1 y2 ya) 0 66 0 E (~6 12 66) mod 0 24 0 .
0 0 524 0 0 24

55

The incongruent solutions of this system are

yl=5+4t1, ' where t1= 0,1,...,5;
y2=1+2t2’ Where t2:0’1,000’11;
y3=l+2t3, . where t3=O,l,...,ll;

and we note that/there are N=(6,24)(l2,24)(12,24)=
6-12-12=864 incongruent ones. The general solution

=Y‘U of (9.10) is given by

x1= y1+ 5y2
x2: y1+ 4y2 - 5y5
x3== 7y1+ 25y2 - llys,

which when expressed in terms of the parameters t1 yields

= + +
x1 4t1 6t2 6

where t1=0,l,...,5; t2=0,l,...,ll; and t =0,1‘,...,11.

5
Since s=kp=5 all the desired incongruent solutions of
(9.6) occur among these 864 incongruent solutions of
(9.10). The conditions(9.1l) for two solutions x' and x
of (9.6) to be congruent are X' - X=WH, which implies

that (X' - X)QR=(WPI)(PHQR) or (x' ~ 100320 mod E.

56

Since
0 0 l 12 O 0 O O 1
GR: 12-5 050:126-5 ,
O -1 O 0 0 l O -5 O
we have

' - -
12(x 2 x2)_.0 mod 24
' - a ' Q ——
6(x 2 x2) 5(x 3 x3)::0 mod 24

(x'l - x1)-5(x'2 - x EEO mod 24,

2

which requires

X'l ' 11=6q1 Q1§Q2 mad 4
x'2 - x2==2q2 and qsgaqz mod 2.

Expressing these conditions in terms of the parameters

t1 and t'1 gives

t'lEtl mod 6

t' -t Et'

2 2 t mod 4.

6 ' 6

Hence for any choice of t1,t2,t3 there is 1 way of choosing
t‘l, 12 ways of choosing t'2, 5 ways of choosing t'3, and
hence 56 ways of choosing t'1,t'2,t'3 to obtain solutions
(x'1 x'2 x's) of (9.10) and (9.6) which are incongruent to
(x1 x2 x5) for (9.10) but congruent to (x1 x2 x3) for (9.6).

64
Hence the number of incongruent solutions of (9.6) is %§;==24.

57

‘s an exam is we not .111 = = = ' =
A p beveltl t2t5t106nd

t'zzt'szl, that the incongruent solutions (6 4 55) and
(12 6 65) of (9.10) are congruent solutions of (9.6).

To illustrate the procedure when s<kp we choose
o(=(2 0 us“, ,6=(i 2 5)E*T, K==(4 a on“, J=4€2+6€3,

and consider
(9.14) 006/3 E/(mod (5).

where (5) denotes the two-sided ideal generated by J .

In section 8 a basis for this ideal was found to be

“1:462, “2:263, so that H=(g g g). We compute

20.1 125 2416
RT(o()S(/3)= 021 060=066 =1,
002 006 006

and note that in section 2 the invariant factors of (H)
were found to be 61:1,82= 2,63=4. The invariant factors
A' .
of (H) are e 1
do exist; and to find them we proceed to solve (9.6)

=l,e'2=2,e'3=4, so solutions of (9.14)

which is

2415

040
(xlx2x3) 065 =(484)m0d 002 .

006

We compute

01 040 200
pnq: t 010: =D,
10 002 040

100
200 0011
R: 010 , QR: 010 ,
001 200
200 '
200 400
DR: 010 = =3
040 040
001
2413 001 2642
AQB= 063 010: 660 =1,
006 200 1200
001
KQR=(484) 010 =(sa4)=K,
200
and (9.10) is then
2642
( ( ) 400
x xx 660 2884mod
1 2 s 040

1200

) .

58

 

59

This system was solved in section 5, and the 8 incongruent

solutions are

x1=2
12=O,2
x5=0,1,2,5.

The condition (9.11) for two solutions of (9.6) to be
congruent is x' - X50 mod H, from which we obtain

()0 - nos-=20 mod if. Simplifying this last relation yields)

1 ...
x 1‘11

' =
x 2-x2 mod 4

' :=
1: 3-13 mod 2

as the conditions that two solutions of-(9.6) be congruent.
If new x'1= x1,x’2512 mod 4, and x'si-xa mod 4, which
are the conditions that x' and x be congruent solutions
of (9.10), then certainly the above conditions are
satisfied and X' and X are also congruent solutions of
(9-6). so in this example also all the desired incon-
gruent solutions are found among those of (9.10). The
desired incongruent solutions are quite obviously (2 0 0),
(2 o 1), (2 2 o) and (2 2 1).

In order to illustrate that two congruent solutions

of (9.10) may actually be incongruent solutions of (9.6)

we consider

(9.15) Xfl E/fimod (b)

60

when fl=(o 1 1)E*T, K=(o 2 one“, and 5::(0 o 3)E*T. A

basis for this two-sided ideal is “1::(0 0 5)E*T. It is

easily seen that the conditions (9.8) are satisfied so that

solutions do exist. The system (9.6) is

011
(x1 x2 13) O l 0 3(0 20) mod (0 0 5);
001
001 110
r=(1), Q= 010 , 11:13, I: 010
100 100

O

i=(0 2 O), fi=D=(3 O 0), and the system (9.10) is

110

(11 x

l 0 0
The solution is quite obviously given by

11+ x2: 2

X1+ x550 mOd 30

21(3) 010 E(020)mod(300).

Let, us consider the two particular solutions (5 -5 4) and

(8 -6 4). Since

61

300
(5 -s 4)-(s -6 4)=(-330)=(-110) 0:50 ,
003

these are congruent solutions of (9.10). For them to be
congruent solutions of (9.6) would require the existence of

a rational integer I! such that
(5 -3 4) - (8 -6 4)=(-3 3 O)=w(0 0 5).

Quite obviously no such w exists, hence these are incon-
gruent solutions of (9.6).
In order to illustrate the necessity of the caution

employed in defining congruent solutions, we consider

(9.16) XflE/(mod(5]

Where fl=(o 0 1)E*T, K,=(0 0 0)s*T, and 25=(e 2 12)E*T.
Let 79:10 1 2)E*T and X2=(6 s an“. Since

2400 2400
(6 se)=(012)+(001) 1240 ,whereI-I= 1240
(624: 624

it follows that X2-;-'X1 mod (6",. Since the solution of
(9.16) is given by xli. 0 mod 8 and x2 and x3 arbitrary,
We note that X1 is a solution of (9.16) and X2 is not a

aGlution of (9.16) even though it is congruent to X1.

62

10. Matrices in (Hung; Q. In the foregoing sections
we were able to solve a system of linear equations or
linear congruences in 6 by solving an equivalent system
in )3 . This latter system was obtained directly through
the use of the regular representations. B. M. Stewart
in [12] made good use of the second regular representation
of elements of an algebraic domain to solve the problem
of characterizing left-associated matrices. A brief
summary of this paper follows.

Let 1? be an algebraic field of order 1: over the
rational field Rd, and [1?] the corresponding algebraic
domain. A matrix P of 311mm; [ED is called unimodular
if there exists a matrix Q of 3n(n,n;[1F]) such that
QP=In; and two matrices A and B of Mn,n;[1F]) are said
to be left-associates in m(n,n; [’LFh if there exists a
unimodular matrix P of moms; [117]) such that ”=13. This
notion of left-associativity is an equivalence relation
dividing the matrices of mum; [5]) into mutually
exclusive classes of left-associated matrices. The fund-
amental problem of the author was to determine necessary
and sufficient conditions for this class division.

If the domain under consideration is a principal
ideal ring, a necessary and sufficient condition that

i and s be left-associates is that A and s have the same

{it in.

.I),.IB$ i...
.. s.

.1.) (II-lav ll) tit! II.) I] II ‘

63

Hermite canonical form; but for domains whose class number
is greater than one, the presence of non-principal ideals
prevents the direct solution of the problem.by an Hermite
form.

However, if each element of a matrix A of 3114mm [tut-h
is replaced by its k-by-k second regular representation,
there is produced an enlarged.matrix A3, of order kn-by-kn,
to be sure, but with elements in the rational domain.
Hence for AE the Hermite form is well-defined and easily
found. Stewart's main result was that a necessary and .
sufficient condition that matrices A and B of QRKn,n;[EFJ)
be left-associates in (Hymn; DIN) is that the correspond-
ing enlarged matrices AB and BE be left-associates, i.e.,~
that the enlarged matrices have the same Hermite form.

Since the main factor in obtaining this result was
the use of the second regular representation, an attempt
was made to establish this same theorem for matrices in
ann,n;€5) and the partial results obtained are discussed
in the remainder of this dissertation.

We recall from section 7 that the matrices 213, form
a basis for finxn,n;¥3) such that any matrix A==(a13) in
Oflln,n;13) can be written uniquely in the form

2 aijzij’ where ‘13 is in *3. We let 81(A) denote the
1.3

64

second regular representation of A, and recall that it has
the simple form 81(A)=A-X1n, where A-XB stands for the
direct product matrix (Abij) in Mn2,n2313) whose (1,5)-
block is Ab”. We also let 82(00 denote the second regular
representation, described in section 6, of any element
ocof @.

The direct product flunmfilmé has the basis

(211,61),...,(Zln, 61),...,_(Zn1,€1), ...,(Znn,€1);
(211’62)""’(zln’€2)'"°’(znl’€2)""’(znn'éé);

(211.619...some,»....cznl.€k).....<zm.€kn

where (Zij'ét) denotes the matrix having 6t in the (1,3)-

position and 0's elsewhere, and

(er,€1) (zuv’ 63): (zrszuv’ 6i 61) ’
If A*== (C(13) is any matrix in Wmngé) with

061.1 =2: ‘ijtet' we write A“ =2 a13t(21j,€t) and conclude

9 D

that 9R(n,n;6) is m(n,n;13)X6.

In order to obtain the second regular representation

e ..
of A we note that z-zn+ 222+...ji-Znn is In and write

1* w ( 0,9123%» WWW

65

(qus Er)A* = (qua Er1;t31Jt(zijs 61;)

figure”); At(z,€t), where A15; autmiyel)
=(zpq.61)§; where)
=2: :1: aqxtmpx’eret)
=22: Z €gxt°rty<sz'€y)'
t y x

where €r€t=E crtyéy’ Arranging (qu,€p) and (pr'ey)
each in the order shown above (i.e., hold y and t constant

and sum on x, then hold t constant and sum on y, and then

sum on t) we find that a second regular representation of

A“) is
l 2
ambit :8 (Atrxs (6t)

2
as; (it-x111) -X3 (60'

a matrix in Mm2,kn2;n). For our purposes the repeti-

tion in this representation is useless and we shall use

(10.1) urn}; At-XS2(€t).

a matrix in Mknfimgfl ) called the reduced regular

66

representation. This reduced representation is obviously
isomorphic to mzxn,n;@5). Since the first row of 32(6t)
has a l in the t-th position and zeros elsewhere we see
that the first row block of s(A*) consists of precisely

A1,A2,...,A.k, the coefficients involved when we write If}
in the form A*=§ :At(Z,€t). since the coefficients At

are unique we see that the reduced regular representation
8(A*) is completely determined by its first row block.
From this observation follows immediately an extremely
useful lemma.

Lemma 10.2. If X and Y are matrices in 911(kn,kn;13)
such that Xs(i*)=Y, then there exist matrices x* and Y"
in m(n,n;€) such that s(x*)s(A*)=s(Y*); and

”=2; xt'(z, (it), Y*=Z;Yt(z,€t) where xt and Yt are the
matrices in Wmngn) found by separating the first block
of :1 rows of x and Y, respectively, into 1: blocks.

We remark that when Y is in s-form, say Y=s(B*), since
the reduced regular representation is completely determined
by the first row block, Y'= 3* and hence s(x*)s(A*)=s(B*).

If we had considered m(n,n; S) from the alternative

Point of view, i.e., as (43 an,n;fl), we would have
obtained as a reduced regular representation of A“ the
matrix A*E=(32(o(1 )) in m(kn,kn:p). When 2C=J—’,

6 = [H and 9= (Rel , A*E is the matrix A8 used by

67

Stewart. However, by using s(A*), the results to follow
can be stated more easily.

In order to compare these two reduced regular repre-
sentations we consider W2,2;6) when Gris the same set

of integral elements described in section '7 and determine

 

 

s(A") and A'E in this particular case. We use the above r
!.
notation.
Cillcxlz 3
«a: .. - 2
31.11 a132 “133 3;
Then, since 82(093) = 0 “131+“132 0 , we have P
O 0. aiji+a132
2 2
‘*E == 3 @111) 3 «Xi2)
32«Xé1) Sztxég)
“111 “112 “113 “121 “122 “125
° a111+“112 ° ° “121+“122 O
“211 “212 “213 “221- “222 “223
° “211“212 ° ° “221“222 °
) ° ° “211+“212 ° ° “221+“222(

 

 

1 0 0 1 0 o 0 0
31““ z11= 0 ‘0! 212: 0 0 ' Z21"“1 0 ' 222=o 1 '

and Z=Z +2

11 22=12, we write

 

68

*—
A -' A1(Z:€1)+Az(za 62) +A3(Zs 63) s

a a fit 0
where “t = llt 2L2t)an d—(Z,€b) = (1:13.)
“zit “2st 0 6

Then we have

 

 

 

 

 

s(A*)=A All-X82(€ )+A2 -xs2(€ H)+A30X82(€ ) T‘s.
A1 0 0 0 A2 0 0 0 A5 t J
=<0 A1 0 + 0 A2 0 + 0 o 0 :
0 0 A1 0 0 A2 00 o ‘ I;
=(“1 “2 “s V
0 A1+A2 0
0 0 A1+A2
“111 “121' 8112 “122 “113 “123
{2 “211 “221‘ “212 “222 “213 “223 \
_ ° “111+“112 “121“122 ° ° 1
- _° ° “211+“212 “221+“222 ° ° .
\0 0 O 0 “111“112 la‘121H122/
° ° 0 0 “211+“212 “221+“222

 

The relation between these two reduced regular repre-
sentations is readily apparent when they are written in

the form

s(A*) =2: AtoX82(€t), A*E =2 82(Et)-XAt.
t

t

 

69

ll. Left-Associativity of Matrices in Tammi). A
matrix P“. in 312,(n,n;6) is said to be unimodular if there
exists a Q“) in 311(n,n;@5) such that Q*P*=In. Two matrices
A* and 8* in OTZ,(n,n; S) are called left-associates if there
is a unimodular P“. in 312(n,n; S) such that P’A*=B*. This

notion is obviously an equivalence relation and hence P
divides the matrices of M(n,n;@3) into mutually exclusive E
classes of left-associated matrices. We wish to compare 1
the left-associativity of A* and 3* in W(n,n;6) with the b

left-associativity of s(A") and s(B") in Wm,kn;p),
i.e., with the condition that s(A*) and s(B*) have the same
Hermite form. .

If Q*P*=In, then s(Q*)s(r')= s(In) =Ikn and s(r*)
is unimodular with s(Q“) = [s(P*)]I. Then s(P“)s(Q,‘»)=ILm

I

which implies that P*Q*=I hence Q*=r‘ and

n'
[s(P*)]I=s(P*I). Conversely, we assume that s(P*) is
unimodular so that a c exists in Wknflnnfi) such that
Qs(P*)=Ikn. Since Ikn=s(In), applying lemma 10.2 yields,
according to the remark immediately succeeding the lemma,
9. Q“ such that s(Q*)s(P*)=s(In)-. Then Q= [s(P*)]I= “Q”
andwe conclude that Q is in s-form, and since Q"P'“'"--"-In
that 13* is unimodular. Hence a necessary and sufficient

condition that P* be unimodular in M(n,n;6) is that s(P‘)
be unimodular in flukn,kn;)3). ’

70

Now if A* and 8* are left-associates in Wmmé) so
that P*A*==B*' for some 13* unimodular in 9n.(n,n;@), it
follows that s(P*)s(A* =s(B*) and s(P’) is unimodular
in 3T7,(kn,kn;(3). Hence s(A“) and s(B’) are left-associates;

and, by Lemma 2.1, must have the same Hermite form. This

establishes that: f“

A necessary condition that A"r and-3* be left- 3
3380013388 in min.n;@) is that s(A*) and s(B*) have 2
the same Hermite form. ii

Let 0 .1 denote the j-by-j matrix which consists entirely
of 0's. If 11* is a proper divisor or O, i.e., (“#011 and
there exists a W*¢On in m(n,n;6) such that “ff-10w
then s(W'“)s(A"")-.-=s(On)==O1m and s(W‘) #01“). Hence the
rows of chi“) are linearly dependent over ‘13 and s(A“)
is singular. Conversely, let us assume that an") is
singular. Then the rows of s(A‘“) are linearly dependent
{over D and there exists a T1 in muflmg-fl) such that

Tls(A*) = (0,0, . . .,0)

and not all the elements of T1 are 0. Letting T' be the
matrix in (numbing?) whose first row is T1 and whose

remaining elements are all 0's, we have

Ts(A*) = 0m.

71

We apply Lemma 10.2 to determine T* in W(n,n;6) such
that s(T*)s(A*)=s(0n). Then 'I"'“A‘“'=On and T*-¢0n since

T contained elements other than“ 0. Hence a necessary

1
and sufficient condition that A* be a divisor of O is that
s(x*) be singular.

Let us now assume that A* and B* are not divisors
of O, and are such that s(A“) and s(B*) have the same
Hermite form B so that there exist matrices x and Y,
unimodular in 311(kn,kn;13), such that Xs(A*)=H =Ys(B*).
Then P=YIX is unimodular‘in 313(kn,kn;13) and Ps(A*) =s(B*).
Applying Lemma 10.2 to this relation determines , according
to the remark immediately succeeding the lemma, a P’ in
3n(n,n;6) such that s(P*)s(A*)=s(B*). Since s(A*) is
non-singular, however, we have P=s(B*) [s(A*)] I=s(P'")
which means that P is in s-form. Since s(P*)=P is
unimodular in 9T2.(kn,kn;13), it follows, as we have shown
earlier, that r“ is unimodular in 912(n,n;6). Thus P*A*=s*

with P“ unimodular, and we can now state the following

theorem :

If A"% and B“ of Mnmzé) are not divisors of 0,
then a necessary and sufficient condition that they be
left-associates in 311(n,n;6) is that s(A'“) and s(B'“) be
left-associates in Wknfimfil).

To illustrate we choose the same set )nK2,2;@§) that

we used in section 10, and consider

2e-t +26 -6+- + ‘
Ai'== 1 E2 5 1 62 “a and

61"‘5.a"'7’(‘:s 61+E2'265

B =

2 -1 1 1 2 1
Since A = A = A =
1 1 1 ' 2 -1 1 ' 3 -s -2 '

v -2 -1 -4 ‘ 0 1
and B '== 13 == 13 ==
1 12 -s ' 2 -21 11 ' 3 1 1 ’

72

from the expression for s(A*) derived in section 10 we find

OOOOHH

NOOONH
as
g
p.

obouHH

OGOOOIN

s(A*)==

OOOOI—‘N
OONOI—‘H

-2 -l -4
-3 -21 11
0 6 -6

O O 0
O 0 0 -

(003000-‘0
GQOOl-‘H
C

73

We compute

.-

 

We discover that there exists a unimodular Y. such that

e
H
/llll||l|\
=
\l‘) \I) 0
000001 ‘1) s
362312 > 000044.
000010 3 110068
262311 t . 440024
000100 m. 010069
senses m . messes
lo 0 0 416800
021100 00 0 e .1. dfiznwoo
062300 W 116900
662323 a nan» - 120000
862—069 M
600023 1 2111-..00 350000
H
= = = 00001.“. =
... ... I
u w = m I
8 8 I h =
X Y Y T P

and we note, as the theory predicted, that P is unimodular

and in s-form.

I! .
o s ,
Juli ‘ PCJ

.. ‘EV

74

We now obtain

(5 1)(Elo)+(-1-4 620 + -1 o 6.30

52 061 ~82 062 40.063

__ 361' €2'Ee 61-462

— 561-862-55 261+2€2 ' E
which is the desired unimodular matrix such that P*A*=B*. I
If A* and 8* are divisors of 0, and are such that I
s(A*) and s(B*) have the same Hermite form H, as before L
there exist matrices x and Y, unimodular in flulm,kn;13),
such that x:(A*)=H=Ys(B*) ; and P=YIX is unimodular
in Mummfl) and such that Ps(A*)=s(B*). We also can
apply Lamma 10.2 to determine from the first row block
of P a matrix P* in 3THn,n;G5) such that s(P*)s(A*)=s(B*).
‘However, as we shall show by means of an example, the
matrix s(P") so determined is not necessarily unimodular.
Since s(A*) and MB") are singular, H is also; and the
most general unimodular matrix 0 (described in Lemma 2.1)
such that GH=H is not Ikzn’ Since YIGX is unimodular
1n Mummp) and such that YIGXa(A*)=a(B*), there is
some freedom in the choice of the matrix P and hence of 1’“.
Whether or not 0 can be chosen so that YIGX is in s-form

has not been established.

75

If we let Q=XIY, then Qs(B*)=s(A*); and applying

Lemma 10.2 to this relation determines a Q“ in mummg)

such that s(Q*)s(B*)=s(A*) and s(q*) is not necessarily

unimodular. Hence, if A" and B‘" are divisors of 0 and such
that s(A*) and s(B*) have the same Hermite form, then there
exist matrices P“ and 0* in m(n,n;C¢5) such that P*A*==B* E‘
and Q*B*=A* -- i.e., A.“ and 13* are mutually left-divisible.
At this point, by referring to the result due to Steinitz [10]

-v>e—_— .
' . A ‘..' {'1 so.

that mutual left-divisibility is equivalent to left- IJ
associativity for matrices in jukn,n;Efi:b, Stewart was able ' ‘
to establish his result where EUFjis an algebraic domain
of classical type. 6

Some results about mutual left-divisibility implying
left-associativity are given by Kaplansky [2], but they
cannot be applied here for we have not restricted the
algebra Zr, which contains g .

As an example we consider once more the same

m<2,2;6) and study

10*: 262+€5 o and B*- 262+265 0
o o ' 63 0

We note that

A00) 20 10 oo
= A:‘ A: B:

1 ’ ’ 9 o
oo 200 500 1oo

76

so that

)

000000
210020
000000
202000
000000

000000

{|\

and s(B*)

)
000000

I 100020

000000
202000
000000

0.00000
{|I\

s(A*)

We compute

\I

 

000000
100020
000000
202000
000000

000000

{III-\\
\I‘)

000001
100000
000100
2010.....0
010000

9%00010

{III||.I\

Xflffi

I)

\IIIIII/

000000
000010
000000
002000
000000

000000

/II|\\

We find a unimodular'Y such that Ys(B*)==H and we compute

\||/

000001
210020
000100
101000
010010

100000
/|\

T.
Y

‘ [I ilbzrllfiI
5344‘ «"0 .... .

 

Then

"U

fl

'4

H

><
. H
OOOOOH

We note that P is unimodular but not in s-form.

ONOOHO

OHOOI—‘O

OHOOt-‘O

OOOI—‘OH

1
1
1
O
2
O

OOHOOO

OOHOOO

omooraw

ooooow

HOOOOO

HOOOOO

77

ouooom
oooo~o
oLowom
oowooo
ooooow
HOOOOO

When we

apply Lemma 10.2 to Obtain the matrix in s-form determined

by the first row block of P we find

s(P*)==

OOOOHO

OOOOHO

OOOHHH

OOHOOO

which we eaeily see

above is

a
H

_ ~ (311
821

851
841
851

 

\ 361

GOOD-‘00

OHOOOH

is_gingglar.

HOéOOO

The matrix G mentioned

 

OI—‘OOOO

 

a ‘qmi-

78

where is unimodular,

 

so in this particular example there is a great deal of

freedom that we can exercise in choosing P==YIGX. However,

due to the simplicity of a(A*) and s(3*), by direct

observation we can find ‘

OOOI—‘HH

a(P*)== , which is obviously

OOOOHO
OOOOOH
OOHHHO
OHOOOH
HHOOOO

unimodular; and hence a unimodular matrix of the desired

type is

= eye 61
61-62 6.;

Pi-

 

79

12. Conclusion. The problem of solving a system of
linear equations or a system of linear congruences Whose
elements are integers from an algebra has been completely
solved. Concerning the left-associativity of matrices

whose elements are integers from an algebra, it has been

i

established that when A. and.B* are not divisors of 0,
a necessary and sufficient condition that they be left-
associates is that s(A*) and s(B*) have the same Hermite

form. Also, when A* and.B* are divisors of 0, this con-

‘fl’li. Wav‘u-d 1“..uw no H.“ J -mofi
L
0

gm“ _‘

dition is necessary. The problem remaining for further
research is the determination whether, when A* and 3* are
divisors of O, the fact that s(A?) and s(B”) have the same
Hermite form is a sufficient condition theta“ and 13* be
left-associates. Perhaps additional conditions concerning
A“ and 13* must be added; but if this is not so, the Hermite
form.of the reduced regular representations would certainly
'be an interesting and practical criterion for determining
left-associated.matrices whose elements are integers from

an algebra.

1.
2.

3.
4.
5.

6.
7.

8.

9.

10.

11.

12.

13.

80

BIBLI OGRAPHY

Dickson, L. E., Al ebras and their arithmetics,
(Chicago, 1925), Chapter X.

Kaplansky, 1., Elementa%%_divisors and modules, Trans.
“61'. Math. 300., (194”, 464.191.

 

MacDuffee, C. C., An introduction to the theo of
ideals in linear associative algebras, Trans. :
Amer. M87511. 8°C., ’ - o "i

MacDuffee, C. C., Matrices with elements in a rinci a1
ideal ring, Bull.*Kmer. Math. Soc., 3§II§555,

MacDuffee, C. C., Modules and ideals in a Frobenius
algebra, MonaFI—ffir Math. ufid Ffiysik, Z§l1§3§I,

03H

 

 

"ifs—Z“... :4. -.
'
..

 

MacDuffee, C. C., Theory of Matrices, (Chelsea, 1946).

Ore, 0., Linear e uations in non-commutative fields,
Annals of fia%5., 3§Il§315, 333-377. ‘

Smith, H. J. 8., On systems of linear indeterminate
e uations andicon ruences,:FEII7jf?Ens. Rby"§5c.
o ondon, lam-526. .:-~

\-

 

 

Smith, H. J. 3., on the arithmetical invariants of a
rectangular matrix 057WEich the constituents;are

Integral numbers, Free. London Math. 30s.,
‘ - 9 7
O . \

\

 

Steinitz, E., Rectecki e systems und.moduln in
algebraiscfien zah oraern, Mathematishe Innalen,
. , - ' an (1912), 297-545. '
Stewart, B. M., A note on least common left-multiples,
Bull. Amer, 9. o 030' , " 0
Stewart, B. M., Left-associated matrices with_glements
in an al ebraicdomain, Amer. Jour. of Math.,
LXIX119475, 562-574. .

Sylvester, J., C. R. Acad. Sci., Paris, 99(1884),
117-118, 409-412, 432-436, 527-529.

FUTHHSAH STATE UN‘VERSI'Y LIBRARIES

 

 

 

 

 

 

4

....-w

 
  

   

  

 

 

“.-