THE CLA$§ EGUAHCN FQR

ROW-EQLEWALEM MAMECES G'VER

PRINCWAL WEAR. BO

“mats *or “10 Degree 0‘ D61, D.
MICHEGAN ST ATE UNWEBLSITY

Bernard R. McDonald
i968

”1:213

 

This is to certify that the

thesis entitled
The Class Equation For
Row-Equivalent Matrices Over A
Principal Ideal Domain Modulo 3

presented by
Bernard R. McDonald

has been accepted towards fulfillment
of the requirements for

_Eh._D._ degree in Mics

j//) 1/” SU‘LQ‘fC/LT

LIBRARY

Michigan State
University

 

 

Major professor

0-169

.‘

ABSTRACT

THE CLASS EQUATION FOR ROW-EQUIVALENT MATRICES OVER
A PRINCIPAL IDEAL DOMAIN MODULO a

by Bernard R. McDonald

In 1955 L. E. Fuller developed a canonical form under
row equivalence for matrices with elements from a residue
class of a principal ideal domain (PID) R. By the Chinese
Remainder Theorem, the situation may be reduced to that of a
PID R modulo pn for a prime p. For p (prime) and a.
elements of a PID R , define d(a) = t where pt is the
g.c.d. of a and pn; then every m X m matrix over R/an
is.a left associate of a matrix (Fuller Canonical Form)
having:

(1) d(a..).i d(a..) for all i and j.

13 11

(2) If ajj # 0, then d(a.-

31) > d(ajj) for i < j.

(3) Every diagonal element is in the form pt,
0.: t.: n.
4 If i ' and d a.. > d a.. , then a.. = O.
H #3 <13>_<33> 13
If d(a..) < d(a..), then a.. is unique modulo
13 J] l]
a...
33
This thesis concerns the combinatorial problem of par—
titioning the canonical matrices into sets and for each
canonical matrix in each set, counting the number of matrices
row equivalent to the canonical matrix. For counting pur-
poses it is assumed that lR/Rp‘ < 00.
By (3), let p(r0, r1, ---, rn; m) equal the number of

. . . i .
canonical matrices of order m haV1ng p occur ri times

1

Bernard R. McDonald

along the diagonal. Recursion and counting formulas are

obtained for p(ro, r1, ---, r 7 m). For example:

 

n
p(ro, r1, ..., rl-l, ..., rk, ..., rn; m) =
rl-l
Srk p(ro, ..., r1, ..., rk-i, ..., rn; m)
and
p(r0' : rkl , In; m) :
Trk p(rOI 0 I rk-1’ - o, In; III-'1)
where
r1
r -J. Ak Bk x — 1
s =
A B r
rk l l x k _ 1
>
rk _,1
X - 1
T = A B
r k k r
k x k - 1
and
X = lR/RPI
k-1 .
_ -1 .
Ak = v x(k 1 )rl A0 - A1 = 1
i=0
n (i-k-1)r-
Bk — .77— X 1- Bn : Bn—l _ 1

1=k+1

Further relations and closed expressions are found for

p(r0, r1, ..., rn; m).

Define Q(m, a) to be the number of unimodular matrices

of order m over R/Ra; N[ro, r1, ..., r m] to be the

‘0

n

number of unimodular matrices which fix a canonical matrix

2

Bernard R. McDonald
of type [r0, r1, ..., rn; m] (that is, having p1 occur
ri times along the diagonal); T[r0, r1, ..., rn; m] to

be the number of matrices which are row equivalent to a

 

 

 

canonical matrix of type [r0, r1, ..., rn; m]; then
n
T[ro, r1, ..., r ; m] = ~Qim'9 )
n N[r0, r1, ..., r ;m]
n
where
n-1 ir m
.W x if rn = O
F 1:0
r
n i
N[ro, r1, ..., rn;m] =-( n ir.m .F (x - 1)
w x 121 if r > 0
i=0 rn(rn+1772 n
c x
2 1 1 1 _
Q(m,a) = Nm v (i - ;)(1 "-h) ... (1 - —m), x - lR/Rpl
pla x x

and

N lR/Ral.
These formulas may be summarized by the class equation

for matrices over R/an of order m:

n m2 ‘\\ ‘
) = Z/’ . T[r0, r1,..., rn; m] p(ro, r1,...,rn; m).

 

r0+r1+o . o+rn=m

The results are then extended from R/an to R/Ra,

a1 32 ak . . . .
a = p1 p2 ... pk . For n = 1, R/Rp is a finite GalOis

field and the results specialize to several already known

for matrices over finite fields.

THE CLASS EQUATION FOR ROW-EQUIVALENT MATRICES OVER

A PRINCIPAL IDEAL DOMAIN MODULO a

BY

Bernard Rf McDonald

A THESIS

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY
Department of Mathematics

1968

\q

\
i“)

Q)
Q)

ACKNOWLEDGMENTS

The author is indebted to his major professor, Professor
B. M. Stewart, for suggesting this thesis problem and for
his helpful guidance during its preparation. Appreciation
is due him eSpecially for his kind consideration during

the author's period of study at Michigan State University.

ii

Dedicated to

Aaron and Betsy McDonald

(without whose help it may have

been finished sooner)

iii

Summary of Definitions and Notation

The basic definitions and notation concerning principal
ideal domains, residue classes, etc., is consistent with

that of Zariski and Samuel [10].

Definitions

 

p(m,n) = the number of canonical matrices of order m
over R/an.

p(r , r , ..., r ; m) = the number of canonical matrices of
o 1 n

order m having pl occur ri times along the
diagonal.

A of type [r0, r1, ..., rn; m] means that A is a

canonical matrix of order m having pl occur
ri times along the diagonal.

N[ro, r1, ..., rn; m] = the number of unimodular matrices

which fix a canonical matrix of type

[r0] r1, 00., In; m].

T[r0, r1, ..., rn; m] = the number of matrices which are

row equivalent to a canonical matrix of type

 

[r0, r1, ..., In; m].
Notation
x = number of elements of R/Rp under finiteness assumption.
m m .

Pi ) = p(ro. r1. .... rl-1.-.., rn; m), p£ ) = 0 if rl - 0.

1 1-1 r-
M1: 77' X( )1 IMO=1

i=0

iv

TABLE OF CONTENTS

INTRODUCTION . . . . . . . . . . . . . . . . . .
0.1 Principal Ideal Domains . . . . . . .
0.2 Special Principal Ideal Rings . . . .

CHAPTER I FULLER CANONICAL FORM . . . . . .
1.1 Preliminaries . . . . . . . . . . . .

1.2 Fuller Canonical Form . . . . . . . .
CHAPTER II THE FUNCTION p(ro, r1, --°, r ; m)
2.1 The Case lR/Rp] < oo . . . . . . . .
2.2 The Function p(ro, r1, --~, r ; m)
2.3 A Remark on p(m, n) . . .-. . ... .
CHAPTER III THE CLASS EQUATION FOR R/Rpn .

3.1 The Number of Unimodular Matrices of
Order m over R/an . . . . . .

3.2 The Number of Matrices which Fix a
Canonical Matrix . . . . . . . .

3.3 The Class Equation for Row Equivalence
over R/an . . . . . . . . . .

CHAPTER IV THE EXTENSION TO R/Rm WHERE

a1 a2 ak

m = p1 p2 --- pk . . . . . . .

4.1 A Variation of the Chinese Remainder
Theorem . . . . . . . . . . . . .

4.2 The Extension of the Fuller Canonical Form

4.3 Extensions of the Counting Formulas .

vi

Page

CDU'IU'le-‘H

11
11
14
34
38

38

43

55

57

57
60
62

TABLE OF CONTENTS (Cont.)

Page
CHAPTER V AN EXAMPLE: MATRICES OF ORDER 2 OVER
Z/an . . . . . . . . . . . . . . . . 64
5.1 Total Number of Canonical Forms . . . . . 64
5.2 The Number of Matrices Which Fix a
Canonical Matrix . . . . . . . . . . 66
5.3 The Calculation of p(ro, r1, ---, rm; 2) . 70
5.4 The Calculation of T[r0,.r1, ---, rn; 2]
and the Class Equation . . . . . . . 70
CHAPTER VI CONCLUDING REMARKS . . . . . . . . . . 76
BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . 79
APPENDIX . . . . . . . . . . . . . . . . . . . . . . 86
Section I An Example . . . . . . . . . . . . 87
Section II The Field Case . . . . . . . . . . 89
Section III Tables for p(ro, I1, -°-, rn; m) . 92
Section IV An Example: Extension to General
Modulus . . . . . . . . . . . 96

vii

INTRODUCTI ON

0.1 Principal Ideal Domains

The purpose of this dissertation is the study of matrices
over residue classes of principal ideal domains and the ex-
amination of certain recursive relationships arising from
the row equivalence of these matrices to canonical matrices
over these residue classes.

A principal ideal domain, PID, is an integral domain

 

in which every ideal is principal. There exists some in-
consistency in the literature with reSpect to this termin-
ology, as a principal ideal domain is often referred to as
a principal ideal ring (MacDuffee [6]). This usage has
occurred as recently as Herstein's , TOpics in Algebra (1964).
Other writers (Zariski and Samuel [10]) define the principal
ideal ring, PIR, to be a commutative ring, possibly posses-
sing divisors of zero, in which every ideal is principal.
This latter approach will be adopted here.
The basic properties of a principal ideal domain R
may be summarized as
(1) The prOper prime ideals in R are those generated
by prime (irreducible) elements, and they are
maximal. (In a PID the concepts prime element and
irreducible element are equivalent).
(2) The ring R is a unique factorization domain.

(3) The ring R is noetherian.

2
(4) Any two non-zero elements a and b of R have
a greatest common divisor d expressible linearly
in terms of a and b.
(5) If CR.iS a prOper ideal of R, then R/Cn satis-
fies the descending Chain conditions.
Proofs of these assertions may be found in Zariski and
Samuel [10].
A field gives a trivial example of a principal ideal
domain. Other examples are:
(1) The rational integers, Z.
(2) Polynomial rings over a field F in one indeter-
minate, F[x].
(3) The Gaussian integers.
More generally,
(4) Any Euclidean ring.
(5) Algebraic number fields with class number 1.
(6) Formal power series in one indeterminate, F[[x]],
over a field F.
(7) P-adic integers.
On the other hand, if R is a domain and w is a non-
negative integer-valued function on R, then a necessary
and sufficient condition that R be a PID is that
(1) If a divides b then ¢(a) i.w(b). If p(a) =
p(b) then a and b are associates.
(2) If neither a nor b divides the other, then
there exists p, q, r in R with r = ap + bq
and Mr) imin(¢/(a), ¢I(b)).

For a proof see Zariski and Samuel [10].

3

0.2 Special Principal Ideal Rings.

The primary object of study in this paper is a principal
ideal domain R modulo the power of a prime ideal *3n =
(pm), that is, R/an. This is an instance of a more gen-
eral concept, the "special" principal ideal ring (Zariski
and Samuel [10]).

A PIR R is said to be Special if, both

(1) R possesses a unique prime ideal *3 # R,
and

(2) The ideal :p is nilpotent, i.e. :p = (0) for

some integer n > 0.

Observe that if R is a PID and p a prime element
of R, then the residue class ring R/an is a special PIR
having Rp/an as its unique prime ideal.

A special PIR R is characterized by the form of its
elements. Letting *3 = (p) and m be the least integer
such that pm = 0, then every non—zero a in the FIR R
can be written as a = upk where u is a unit and
0 :.k,:.m-1. The verification of this consists of observing
that either a is a unit or a is contained in the unique
maximal ideal Rp of R. In the latter case, k is taken
to be the highest power of p dividing a. Further, the
integer k can be shown to be unique while the unit u is
unique modulo Rpm-k.

Conversely, if a commutative ring R contains a nil-

potent element p with the property that every element

4
, . k . .
a #()1n R can be written as a = up Wlth u a unit, then
R is a special PIR.
It can be Shown, in the way of a structure theorem,
that a direct sum of PIR's is a PIR and that every PIR
is a direct sum of PID's and Special PIR's (Zariski

and Samuel [10]).

CHAPTER I
FULLER CANONICAL FORM
1.1 Preliminaries

A principal ideal domain R is a unique factorization
domain, consequently for a given element a” (non-zero) of
R and a prime p, a = pk b where the greatest common
divisor of p and b is 1, (p,b) = 1.

By defining, for a in R, a # O, vp(a) = k and

setting vp(0) = 00, a function

 

v :R Z U 00
p > t }
is constructed called the logarithmic p-adic valuation on
R.

For a and b in R, it is easy to see that

1 v ab = v a + b

< > p( > p( > vp( >

v +b 2. ' a , b
(2) p(2:1 > mm<vp< > vp( >>

The basic situation considered is the residue class

ring of the PID R modulo Rpk, R/Rpk, for a prime p. For

this case, a restricted version of the logarithmic valuation
called the p:degree of the element a, denoted dp(a) is

employed. For a in R, define dp(a) = t where pt is

 

the greatest common divisor of a and pk. Clearly,
0 fi.dp(a) :.k and all elements of the same degree are as—
sociates in R/Rpk. If d (a) = k, then a is in the zero

P
class of the residue class ring. If dp(a) = 0, then the

5

6
image of a in R/Rpk is a unit. Elements of degree less
than k and greater than 0 map into proper zero divisors
of R/Rpk. Thus, the elements a of R map onto k + I
ordered classes 3' of R/Rpk and, as is customary, the
bar over the elements of the residue class will be omitted.
Similarly, when the prime p is understood, vp and dp

will be denoted v and d respectively.
1.2 Fuller Canonical Form

Let R be a principal ideal domain and a an element
of R. Consider the set of m x m matrices with elements
from R/Ra. It is obvious that this collection of matrices
forms a ring with identity whose units are the unimodular
matrices, that is, matrices whose determinants are units of
R/Ra.

Two matrices A and B are row equivalent, or left

associates, if there exists a unimodular matrix U such

 

that UA = B. Thus, the unimodular matrices determine
equivalence classes of the ring of matrices under left multi—
plication.

If R is a PID and p is a prime, then the equivalence
classes of matrices over R/an have the following canonical

representatives.

Theorem 1.1 (Fuller [2], 1955) Every m x m matrix with

 

elements from R/an is the left associate of a matrix

having the following properties:

7
(1) The degree of every element of each row is greater
than or equal to the degree of the diagonal element
of its row, i.e. d(aij) Z.d(aii) for all i and
j.
(2) If the diagonal element is not zero, then the
degree of every element below the diagonal is

greater than the degree of the diagonal element

of 'ts row, '.e. d a.. > d a.. for i < '
1 1 <11) <33) 3

'f a.. 0
1 3375
(3) Every diagonal element is in the form pt,

0.: t.: n.
4 f ' ', d d .. Z.d a.. then a.. = O.
( ) I 1 # J an (313) ( JJ) 13

if d(a..) < d(a..) then a.. is unique modulo

1] 33 1)
ajj’ i.e. aij is an element of (R/an)/(R/an)ajj.

Schematically, the canonical form appears as

 

 

a = s a
ii 9 °°° ij
a ° a épt
ji ... jj
_ “'m x m
where
(1) d(aij) 2.5 and aij is reduced modulo pt.
(2) d(aji) > t and aji is reduced modulo ps

8

Properties (1) and (2) relate the elements in a row
and their diagonal elements. Property (4) relates the
elements in a column and their diagonal element.

Examples of this canonical form for the cases Z/Zp2
(order 2), Z/Zp3 (order 2) and Z/sz (order 3) are pro-
vided on pages 16, 17 and the Appendix respectively.

If n = 1, then R/Rp is a field. The diagonal ele-
ments are either p0 = 1 or p1 = 0 and all elements are
either of degree 1 or of degree 0. By property (1), if
the diagonal element is zero, then the entire row is zero.
If the diagonal element is p° = 1 (of degree zero), then
by property (4) the column containing this diagonal is 0.
By property (2) the canonical matrix is upper triangular,
that is, below the diagonal all elements are zero. Thus,
it is clear that for n = 1, the field case, the Hermite
(non—reduced) canonical form results.

The uniqueness proof of this canonical form will not
be presented here and the reader may consult Fuller [2].
The proof is based on an ordering, which, though stated
differently, was discovered to be somewhat analogous to the
proof given later in this paper of the number of matrices
which leave a canonical matrix fixed under left multiplica-
tion.

However, a method for arriving at the canonical form
‘will be described: Note that each element of the matrix
belongs to one of the n + 1 ordered classes based on their

degrees. Scan the matrix and select an element of the

9
lowest class for the given matrix. If a row contains more
than one element of this class of lowest degree, then to
establish property (2) the element must be selected of least
column index. Place this element, by an interchange of rows,
in a diagonal position and, by multiplication by a suitable
unit, change it to a power of p.

Due to the choice of the diagonal element, all other
elements in the column are multiples of it and, thus, by
elementary transformations may be reduced to zero.

Consider now the submatrix constructed by the deletion
of the above column and row containing the above chosen
diagonal element. Repeat the procedure on this submatrix.
Again for this new diagonal element each element in its
column will be a multiple of it and can be reduced to zero
with the exception of the row containing the first chosen
diagonal element. This can only be transformed to a repre—
sentative of its residue class modulo the new diagonal ele-
ment. Continue in this manner.

Consider the following examples. Let the PID R = Z.
p = 2, n = 3, and, thus, R/an = Z/Z23. A superscript in
parentheses in the initial matrix will denote the degree
of the element. A multiplication by m of row i will be

denoted mRi.

 

 

 

10

 

 

 

 

 

 

 

 

 

Example 1
0(3) 1(0) 2(1)
5(0) 2(1) 0(3) Interchange
R1 and R2
4(2) 6(1) 7(0)
_ J
5 0 4
R1 - 2R2
R3 _ 6R2 > 0 2° 2
_4 o 3_]
F _
2o 0 4
R3 _ 4R1
0 2° 2 >
.5“ 0 3.1
2° 0 o—
3R3
> 0
Example 2
'- fl
1(0) 2(1) 1(0)
2(1) 0(3) 2(1) R3 ' 7R1 >
R2 — 2R1
7(0) 6(1) 1(0)]

 

 

 

 

 

 

 

 

VS 2

o 1

4 6
5R1

F20 0
o 20
(o o
FPO 2
o 22
o o

 

 

 

 

LP

CHAPTER II

THE FUNCTION p(ro. r1. ---, rn; m)

2.1 The Case lg/Rp] < 00

f

 

It is the purpose of this dissertation, as stated in
the introduction, to count the number of canonical forms
and the number of matrices row equivalent to acanonical form
for the residue class ring of a principal ideal domain R.
Of course, for these to be non-trivial enumerations it is
necessary for R/Rp to be finite, i.e. IR/Rpl < 00.

Examples of PID'S possessing this prOperty are the
rational integers Z, rational p-adic integers, polynomial
rings in one indeterminate over a finite field, and the
formal power series in one indeterminate over a finite field.
Then, if lR/Rp] < 00, it is necessary to count the number
of distinct elements of R/an. With this in mind, the
following results are presented. They originate in the
classical theory of p-adic extensions of Dedekind domains
and can be found in several sources, for example, S. Lang's
Algebra or H. Hancock's, Foundations of the Theory of
Algebraic Numbers. Here, the results will be Specialized
to a PID R.

Let R' be a fixed complete set of coset representatives
containing 0 for the residue class field R/Rp. Let v
be the p-adic logarithmic valuation on R discussed in

Section 1.1.

11

12
Proposition 2.1 Every element a of R can be writ-
ten as a sum

a=Xo+X1p+°-°+kaK+gk

where V(gk) > k and the xi are uniquely determined ele-

ments of the transversal R:

Egggf: The existence proof is by induction on k.
First, the step from k to k + 1 will be considered Since
the case k = 0 becomes a special instance of this step.

Assume the proposition is true for k and

a = x0 + xlp + x2p2 + --- + xkpk + 5k
where the xi are in R. and v(gk) > k. Observe that
either 8k = upwgk) where (u,p) = 1 or 8k - 0 and

v(gk) = 00.

Case I For either situation, if v(gk) > k + 1

choose xk+1 = 0 and 5k+1 = 5k.

Case II If V(ek) = k + 1, then xk+1 E u mod p

for some xk+1 in R.

Consequently,
k+1
a = x0 + xlp + --- + Xk+1 p + €k+1
where = (u — ) k+1 is the desired re resenta-
8k+1 xk+1 p p

tion. Note that

v(ek+1) = v{(u - Xk+1) Pk+11

v(u - Xk+1) + (k + 1)

IV

k + 2.

13
Now for the initial step of the induction proof, k = 0,
set s_1 = a and x_1 = 0 and proceed as above.

For uniqueness, suppose

x0 + le + --° + xkpk + 8k =
k
Yo + Yip + "' + Ykp + 5k-

Then

X0 E Yo mod p.
But, then x0 = y0 since they were drawn from R3 In the
same manner,

X19 5 Y1? mod 92
Thus x1 E y1 mod p and x1 = y1. Continuing, xi = yi

In several Situations notation will be introduced and
then adopted throughout. To aid the reader a list of nota-
tion is provided prior to the introduction and when it is
introduced it will be preceeded by the letters [NOTE.

NOTE. For the remainder of this paper, it will be
required that the principal ideal domain R possesses a
finite residue class field of order x modulo the prime p,
that is, x = lR/Rpl.

When lR/Rpl < 00, Since R/Rp is a field, R/Rp
is isomorphic to some finite Galois field GF(qn) where
q is a rational prime and n 2.1. Consequently, the
number x of elements of R/Rp is q? where q is a

rational prime. It will be found that the prime q does

not enter into the calculations explicitly.

14

Corollary 2.2 Then number of distinct elements of

R/Rpk is xk.

 

Proof: If a is an element of R, then by the pre—
vious proposition

a E X0 + xlp + °°° + xk__1pk-1 mod pk

where the xi are in R/Rp. Thus, the number of distinct
residue classes of R/Rpk is simply the number of choices

for the Xi' namely xk.

Perhaps it is useful here to state that a very suitable
example, one that will be employed Consistently, is the
rational integers modulo the power of a prime, Z/an, with

x = p.

2.2 The Function p(ro.r1.r2. '°°. In; m)

Consider a canonical matrix of order m, that is of
dimension m x m, over R/an. It will be useful to ob-

serve the number of possible choices for an off—diagonal

 

_ S _ t . . .
element aij when aii — p and ajj — p . Define T(1,j)
by
1 if S > t
when i < j
xt_s if 5.: t
T(i:j) = i
1 if t + 1 > S
when i > j
- —1
x5 t if t +1.: 5 ,
L
then the number of choices for a.. is T(i,j).

1]

15

This is easy to see, for suppose i < j, that is, a.

lj

lies above the diagonal. Consider two cases:
Case I. (s > t) In this case, d(aij) 3.5 by prop-
erty (1) of the Fuller canonical form. But by property (4),
aij is reduced modulo pt. However, 5 > t, so aij must

equal zero, hence one choice for aij’ namely 0.

Case II. (3.: t) For this situation, as above,
d(aij).l S and aij is reduced modulo pt. Thus by the
results in Section 2.1,
aij = xopS + xlpS+1 + --- + xt_s_1pt_1
where xk are elements of R/Rp chosen as in Section 2.1.
Thus one has x choices for each xk and consequently
xt-s choices for a...

13
When aij lies below the diagonal, i.e. i > j, then
the situation is analogous to the above cases with the addi-
tional requirement that d(aij) Z.t + 1.

Two functions will now be defined with respect to the
number of canonical matrices over R/an.

The function p(m,n) represents the total number of
canonical matrices of order m, i.e. dimension m x m, with
elements from R/an.

The function p(ro,r1,r2, ---, rn; m) is the number
of canonical matrices of order m over R/an having the

property that p1 occurs ri times along the diagonal.

It Should be observed that

16

 

 

i]
p(m,n) = ,:> . p(ro, r1, r2, "'I In; m)
r0+r1+°°’+r =m
n
If n = 1, the Situation reduces to the case of a field,

then p(ro, r1; m) counts the number of canonical matrices

of rank r0.

NOTE. It has proven desirable to employ two representatives
of the zero residue class of R/an. This Class
representative will be denoted by pn when occurring
as a diagonal element and 0 otherwise. This con-
vention is established in order to conveniently de-
scribe the diagonal elements.

Consider the following examples. In both example, the
diagonal element is as indicated, the number "0" indicates
one choice for the position occupied, namely 0, and "(pk)"

indicates pk choices for the position.

Example 3 The canonical matrices over Z/Zp2 of

 

order 2.

P° (p)

o
P0 0
91 0 P1 0 P1 (P)
0 p0 0 p1 O 2
0 .
p0

po

0

'U

H
I o w I
"O

»

 

 

Observe that

P(2.

9(0:

and

0.

2.

Example 4

 

order 2.

 

The functions

p(2, 0, 0.
p(0, 2, 0.
‘p(0, 0, 2,
p(0, 0, O,

FPO 0-

 

0;
0:
0:
2:

p(ro, r1, r2, r3; 2)

NNNNNNN

The

= 1

= p + 1

p + 1

17

P2+P

= p2 + 3p + 5.

canonical matrices over

 

lo .01

 

Ic, $41
[A
'U

I o 'qJ ' o .J
o “A o
L____J L____J L_____J

p2

and
p(O, 1, 1, 0; 2)
p(0, 1. 0. 1; 2)
p(O, 0, 1, 1; 2)

and

Z/Zp3

of

 

p3

p(m, n) become:

p + 1

P2+P
p + 1

18

p(1, 1, O, O; 2) = p + 1 p(2, 3) = p3 + 3p2 + 5p + 7.
p(1, 0, 1, 0; 2) = p2 + p
= p3 + p2

p(1, O, O, 1; 2)

A third example, the canonical forms of order 3 over
Z/Zp2 is provided in the Appendix, Section I.

The remainder of this chapter will be concerned with
the determination, in a recursive manner, of the value of
p(ro, r1, r2, :--, rn; m + 1) to be defined in terms of
p(ro, r1, °", rn; m), that is, to construct the counting
function of order m + 1 from those of order m.

NOTE. If A is a canonical matrix of order m and having
p°, p1, ---, pn appearing r0, r1, ---, rn times, respec-
tively, along the diagonal, then A will be said to be of
type [r0, r1, --°, rn; m]. Clearly, there are

p(ro, r1, °°-, rn: m) canonical matrices of type

[r0, r1, ---, r ; m].

Further, the following notation will be adopted.

Let
(m)
P = _ . (m) _
if r1 = 0.
l (l-i)ri
M1 = W X where Mo = 1
i=0
n (i-l—1)ri
N1 = F x where N = N _1 = 1.
i=l+1 n n

Proposition 2.3

n

19
Proof: The formula will be deduced from a direct study

of the canonical form. Let A be a matrix of type

 

 

[r0, r1, '°-, rn; m + 1]. The matrix A may be written as
T . ‘
Aim) : *
A = ------- f—---
' l
* : P
J... .—
where A£m> is an m x m block of type [r0, r1, ---,

rl-l, ---, rn; m] and p1 occupies the m + 1 diagonal

position with 0.: 1.: n.

Case I Consider the (m + 1) - column. The position

(i. m + 1) may have a non-zero element only if the ith—

diagonal position contains pt with t < 1. Thus, consider
only those rows with diagonal elements of degree less than

1, i.e. the rows counted by r0, r1, ---, r1_1.
_j <.< . l-j
For a.. — p , 0._ j._ 1, there eXlSt x

choices
ii

for the (i, m + 1)—position. Therefore, there are x(1-3)rj

choices for the rj-rows. Hence,

1 (l—j)r.
W X 3 = M

j=o 1

choices for the (m + 1)-column.

Case II Consider the (m + 1)-row. The position
(m + 1, i) will possibly contain a non-zero element only

if the ith-diagonal position contains pt with t > 1 + 1.

' '— 1+1
Thus, for aii = P]: n ->-j : l + 1. there exist it3 ( )

20

choices for the (m + 1, i)-position. Consequently,

(j-l—1)r.
x 3 Choices for the rj rows. Thus
n (j-l-1)r-
r x 3 = N1
j:l+1

possibilities for the (m + 1)-row when p1 occupies the
(m + 1)-diagonal position.

Multiplying these products with p(m) (the number of

1
possible choices for the block A£m)) one obtains a count
of the number of canonical matrices of type [r0, r1, ---,

rn: m+1] having p1 in the (m + 1)-diagona1 position,

(m)
MlNlpl .

But 0 2.1 i n, thus

n
p(ro' ‘1' "°' rn’ m +1) = 1:0 MlNlpi

m)

completing the proof.

If n = 1, the field case, the formula becomes
p(ro. r1; m + 1) = P(ro‘1l r1, m) + Xro p(ro. r1‘17 m)

which gives the number of Hermite canonical matrices of

rank re and order m + 1 in terms of the number of
canonical matrices of ranks r0 - 1 and r0 and order m.
The restriction of n to 1 gives as a special case a
number of recursion formulas and results for matrices over

a Galois field. These results have been obtained by a purely
matrix theoretic approach by Stewart [9], but are well-

known from the study of finite projective geometries.

21
(Hall [3], Artin [1]). Thus, the case n = 1 deserves
special note; consequently, the results are summarized for
n = 1 in Section II of the Appendix.
The above recursion formula is written explicitly below

for the cases R/Rp2 and R/Rp3.
Case I R/Rp2

p(ro, r1, r2; m+1) = xr2 p(ro-l, r1, r2; m)
ro
+ x p(ro, r1—1, r2; m)

+ ero ){r1 p(ro, r1, 1.2-1; “1)
Case II R/Rp3

p(ro, r1, r2, r3; m+1) =

r 2r
x 2 x 3 p(ro-l, r1, r2, r3; m)

r r
+ x 0 x 3 p(ro, r1-1, r2, r3; m)
2r r
+ x 0 x 1 p(ro, r1, r2-1, r3; m)
3r 2r r
+ x 0 x 1 x 2 p(ro, r1, r2, r3-1; m)

The above recursion formula for the case R/Rp3 was used
to generate counts of the number of canonical matrices for
various choices of r0, r1, r2, and r3 for matrices
through order 5. Tables displaying these results are given
in Section III of the Appendix.

The purpose will be to develop more convenient tech-
niques for computing p(ro, r1, r2, ---, rn; m) and to

observe various relationships for the function p(ro, r1,

NOTE.

22

The following convenient notation will be defined

and employed throughout the remainder of this Chapter.

 

 

Let
1-1 (l—i-1)r.
A1 = .F x where A0 = A1 = 1
i=0
n (i-l-1)r.
B = W x where B = B = 1.
l i=l+1 n n-i
It is useful to observe
M 1-1 I.
l _ i
(1) r“ 77' X
1 1:0
and
N
(2) E]; = 1.
1
Further, define the function Sr(’_1 by
k
r
ro—1 AkBk x °-1 >
Sr =1??— r . rk—l
r .—
Proposition 2.4 Let Sro be defined as above,
k
p(ro-l’ I‘1' ...! rkl ': In; m+1) =

The proof of this proposition will be postponed for a

Srk p(rO’ r1, ..., rk_

ro-l
1. °°°. In:

few pages, as several preliminary results are needed.

Proposition 2.4 will prove to be the basic tool for

evaluating p(ro, r1, r2, "°. rn:

m+1).

The proposition

23
states that the number of canonical matrices of type
[r0, r1, ---, rk-l, ---, rn; m+1] when multiplied by the

r -1 . . .
factor Sro‘ gives the number of canonical matrices of
k

type [ro-l, r1, ---, rk, ---, rn; m+1]. It is clear then,
beginning with p(m+1, 0, :°-, 0; m+1) = 1 and by suc-

. . . . r -1 . .
ceSSIve application of Sr0 for various chOIces of k,
'k

the value of p(ro, r1, '°°, rn; m+1) could be determined.
The choice of matrices of order m + 1 is for later con-

venience.

r —1
It should be noted, the factor Sr0 is also a func-
k
tion of r1, -°-, rk_1, rk+1, ---, rn; however, as PropOSI-

tion 2.4 suggests it is not convenient to include

. . . r0‘1
, rn in the notational chOIce, Sr ,
k

r1, '°°' rk-i’ rk+1’
for the representation of the recursion factor.

It will be assumed that Proposition 2.4 is valid for
matrices of order k , 1 :.k :.m. Under this assumption
two results will be developed and later utilized in an in-
duction proof of Proposition 2.4.

The first of these results will demonstrate that the

necessity of increasing rk at the expense of r0 may be

 

dismissed.
r
r-1 AB 1
Proposition 2.5 Let S l = _§_E. §__.' 1
r A B r
l l x k _ 1

where rk :_1, then

.(Note that Z ri = m + 1. It has proved illuminating to ob-
serve the varying values of Zri in this series of proposi-
tions. In general 2 ri# m. Thus, the value of Z ri will
be enclosed in parentheses in the proofs when it is con-

sidered necessary for clarity.)

Proof: Under the assumption that Proposition 2.4 is
valid for k, 1 :.k :.m, and employing the notation on

page 18, one has

 

r0"1 (m) = (m) _ r0"1 (m) _
Sr pl p0 - Sr pk (z ri _ m + 1)
1 k
Thus
ro-l
p(m) = rk (m)
r .—
Sr° 1
1
r
_ AkBk x 1 - 1 p(m)
— A B r k
1 1 x k _ 1

”“1-1 (m)

It will now be shown that the number of canonical

matrices of type [r0, r1, ---, rk-l, -~-, rn; m-l]

(Z ri = m) when multiplied by an appropriate factor yields

25
the number of canonical matrices of type [r0, r1, ‘°° r

---, r : m] (2 ri = m).

x k - 1

m
_ x - 1
Tr _AkBk[r rk:1
As agreed PrOposition 2.4 is valid for k, 1 j.k i.m.

Proppsition 2.6
p(ro’ III ...I rk’ ..., r ; m) 2

T p(rOI r1! ..., rk-ll ...I In; m-l)

Proof: By Proposition 2.3,

 

 

 

 

_ n (m-l) _
p(ro. r1, °°°, rk. "~. In; m) - 12 MlNlpl (Z ri - m)
=0
But, by Proposition 2.5 "\Thc ease wv-i
(m-l) r1"1 (m-l)
P1 = 8r Pk (2 ri = m)
Therefore
P(ro. r1. ---, rk. "'. In: m) (2 Ii = m)
n r -i
1 (m-l)
= Z M N S p
1:0 1 1 rk k
n AkB rl ( ) r 1
_ m-1 '
: z MlNl A Bk Xr 1 k (def. of S )
1-0 1 l k k
x -1
M N (m-i)
_ n 1 1 r1 AkBk pk
- z [x - 1]
1:0 AIBI rk
[X - 1]

26

 

 

 

(m-l)
n l—i r. r B p
= g (,7; x 1) [x 1 - 1] Akrkk ((1). (2) p. 22)
1-0 i-o [x k _ 1]
r +r +---+r B p(m—l)
: x o 1 n — 1] Akrk k (Telescoping sum)
k
[X - 1]
AB p(m-l)
= [Xm _ 1] krk k (2 r. = m)
k i
[X - 1]
_ (In-1)
_ Trk pk

Now, with the aid Of Propositions 2.6 and 2.5, a proof of

Proposition 2.4 will be presented.

Proof of Prpposition 2.4: The proof is by induction

on m, the order of the matrix.For the case m = 1; rk = 1,

’ r0 = 1, r. = 0, i # 0, i # k, and

i
r -1
Sr0 =1
k
(1)
Pk =1
1
Pd) =1
1 r -1
thus, clearly, pg ) = S O p(l).
rk k

Therefore, assume that the recursion formula is valid
for k, 1 fi.k :.m. Consequently, Proposition 2.5 is valid
for m and hence Proposition 2.6 is valid for m + 1. Re- ‘

call,

1-1 .
A1 = w x(1-l-1)ri , A0 = A1 = 1
i=0
(3)
n (i-l—1)ri
B1 = W x . Bn = B _1 = 1.
i=l+1 n

It will be shown that both sides of the equation Simplify

to the same expression.

Case I Consider the right Side of the equation

ro-i
r
k

S p(rOI I1, ...: rk'll ...! In; m+1) (2 ri = m+2)

r-i I l ... I.
= Sr: p(ro. r1, '°'. IR’ . rn. m+1)

(Letting r; represent the numerical value of the ith

position, namely rk-l if k = i and ri for k # i).

This, by Proposition 2.6, equals

ro-l Xm+1 - 1 I I (m). g _
Sr .[:;;—-—-—- A0 Bo po (2 ri — m + 1)

k - 1
The prime indicates that ri replaces the "letter" rk in
m
the formulas (3) for Al and B1 and in pg ).
However, A5 = A0 = 1 and

B0 = W x w
i=1 i=k+1
k k-i (i-1)r. (k-1)rk n (1-1)r 3
=,(1 “.1. x )(x )(iiflx 1
: (1-k) p X(i-1)ri = X(i-k) Bo
i=1

28

r0'1 (m+1 330‘1 xm+1 — 1 l-k (m).
Sr pk ) = Sr [ r X( ) AOBOPO
k k x 0 - 1
_ Ak Bk xr0 - 1 x’“+1 - 1 X(1_k) A B (m)'
— A0 Bo rk r0 0 0 p0
x - 1 - 1
+1 -
(14‘) Bill—Li (m)
X Ak Bk rk p0
x - 1
where Z rk = m + 2 and Z rk = m + 1.
Case II Consider now the left side of the recursion
formula
p(ro_1I 000’ rk’ ..., rn; m+1) =
p(rg. If. °'-. r5: m+1)
where the value of the ith position is given by r? and

2 r. = m + 2, Z r. = m + 1.
i 1

By the induction hypothesis for the case m, Proposi-

tion 2.6 is valid for m + 1. Thus

p(m+1) = T" p(m)u
° rk k
Xm+1 - 1 H H (111)" n
=[T“"‘— Akkak (Zri=m+1)
x k - 1

AS in Case I, the double prime indicates that r; replaces

the "letter" ri in the formulas (3) and pfim)

But analogous to Case I,

H : (1-k) I. =
Ak x Ak , B Bk

29

and
(m)" (m)‘
pk - p(ro-l. r1. °°. rk-l. "‘. rn: m) - p0
where
Z r = m + 1 = Z r? .
1
Therefore
(m+1) (1-k) xm+1 - 1 (m)'
Po - X ‘E;""" AkBk Po
x - 1
(Z rk = m + 2, Ztri = m + 1).

Comparing Case I and Case II,

(m+1) ro-i (m+1).
Po Sr ’
k

completing the induction proof.

NOTE. Let the following symbols be defined by

[Lil] (—-——><———> ---(*":i‘i ; 1)

 

 

r S+1-i _ 1
= 1 ( i ) for S Z.r
i=1 x - 1
S
= 1
[ioii
r
k
r r0 1’:
(5) RI0 = g5- , R0k = 1
k 0 r

30

(a) ark = pk] k [in] .00 = 1

One of the difficulties of the previous recursion
formulas is that both Proposition 2.4 and Proposition 2.6
allow only the alteration of one diagonal position for each
application of the S or T factors. For example, to
construct p(ro, r1, ---, rk_1, S, O, ---, 0; m) from

p(ro, r1, ---, rk_1, 0, 0, ---, O; m-S) requires 8 ap-

 

 

plications of Tr , rk = 1, 2, -°-, s. In an attempt to
k
remedy this, several further recursive relations were ob-
tained.
. . r0'1
The first of these generalizes Sr .
k
ro .
Proposition 2.7 Let Rr (r0 3_ rk) be defined
k
as above, then
p(ro — rk, r1, ---, rk_1, rk, O, ---, 0; m)
ro
— Rr p(r-.0: r1: ...: rk_1I or ...! OI m)
k
Proof: The proof consists of simply applying repeat-
ro-l
edly S to p(ro, r1, "'. r , 0, ---, 0; m) to
rk k-i
to construct p(ro-rk, r1, °°°. rk_1, rk, 0, °--, 0; m).
Observe
r
Sro-l = Ak Bk x ° - 1
rk A0 Bo rk

31

since ri = 0 for i > k implies Bk = A0 = 1. By factor-

ing out of Ak and Bo those x whose powers involve

 

 

either r0 or rk,
(k-1)r r
Sro-l = x o 215. £3.23.
rk (k—15rk Ck ' rk
x X - 1
where Dk and Ck are functions of r1, ---, rk_1.
Then
p(ro-rkl r1! ...: rkl 0, ...I 07 m)
ro'rk ro-rk+1 (ro-l)-1 ro-l
= Sr Sr _1 ..o Sz 81 p(rOI r1,°",rk_1.0"0:m)
k k
rk r0"i
= .W Si p(IOI III ...I rk-l' OI .. I O; m)
1:1
r . .
: Wk X(14.1)[r0+1-1] Eli. <Xro+1-1_ 1 p
i=1 x(k-1)l Ck xl - 1

 

r
[X(k-1)rOJrk x(1-k)[1+2+o..+(rk_1) ] Eh. k
(k-1)[1+2+---+rk] Ck

X

[x (k-1)rolrk
WI [Ck

since 1 + 2 + --- + t = £1E_i_ll and then

 

U
ix:
L____JH
H H
3‘ O
p

32

 

 

(r -1)
(1_k)[:1L;1;__]
x = 1
X(k—1)[:££;E::Zq X(k—i)[:§£:5::l;+ibigfiiil]

(k 1)rk [:( rk:]
x x
Therefore, the above equals

r

 

(k‘1)ro k
X Dk r0
VTk-ljrk r p
x Ck k
Ak rk r0
— [:EZ' rk p
r0
= Rrk p

PrOposition 2.7 allows the first of two closed expressions

for p(ro, r1, -°-, r 7 m).

Corollaryf2.8

) r 0 r0 r0 r0
p(ro,r1, ,rn, m — an an_1 Rr3 er er Rr0
where

R = p(m, 0, °', 0, ; m) = 1

I0

and

ro=m

k
rgk) = m - Z ri .

33

r
Proof: The verification follows by applying Rro as
k

in Proposition 2.7 to p(m, 0, "°, 0; m) with correct

choices for ID and rk to construct p(ro, r1,°--, rn; m).

Now as a generalization of TI , one has
k

PIOBQSition 2'9 Let Or be defined
k

p(ro: :1, "°, rk_1, rk, 0, °°°, O; m) :

as above (6), then

 

Qr p(ro, r1. '°-, rk_1, 0, °--, 0; m-rk).

k
. . Io"1 .
Proof: In PropOSition 2.7, Sr was applied re-
k
r
peatedly, constructing Rro. Here, analogously, successive
k
0 I | - 0..
applications of Tr; for rk - 1, 2, , rk to

p(ro, ---, rk_1, O, ---, O; m-rk) to form

p(ro, r1, ---, rk_1, rk, O, ..., O; m).

Recall
m
Tr r Ak Bk
k k
x - 1
.00. O — < <
But, for p(ro, rk_1. 5. 0. .0, m rk+S) 0._s ..rk.

the value of B is 1. Moreover, A does not depend

k k
on rk, i.e. Ak is a function of r0, --°, rk_1.
Consequently,

p(ro' r1, ..., rk_1' rk’ 0’ ..., 0; m)

 

= TI TI _1 -- T3 T2 T1 p(ro, - , rk_1. 0, °° , 0; m-rk)
k k
m-r +1
_[A]rk(xm-1) ”(x k -1) .
k rk x - 1 p

34

As before, Proposition 2.9, allows a second closed

expression for p(ro, r1, ---, r ; m).

Corollary 2.10

 

p(ro: r1, ’°-rn: m) = an an_1 - - ° er Qr0 where
Qr0 = 1 and Qri = 1 if ri = 0.
Proof: The verification is analogous to Corollary
2.8. Apply Qr.’ i = O, 1, °°°, n, repeatedly to
i
p(ro, O, ---, 0; r0) = 1.

2.3 A Remark on_me,n)

The function p(m,n) counts the total number of

canonical forms of order m over R/an. As observed before

\ I
p(mln) = / J p(roI r1: r2: ..., In; I“).
ro+r1+o o o+rn=m

 

It would be pleasant to obtain a recursive determina-
tion of p(m,n) in terms of the total number of canonical
matrices of lower order and/or modulus. Unfortunately, this
was not able to be found, except in several special cases.
[The case m = 2 for Z/Zpn is given in Chapter V. The
case n = 1, and m :_3, which was already known, is given

in the Appendix, Section III.] This is not to say, that

35

such a recursion does not exist, although an unsuccessful
attempt was made to demonstrate that p(m,n) could not be
defined linearly in terms of p(s,n) (s < m) with coef-
ficients being polynomial functions of xm. This is the
situation for n = 1 and m 2.3. In any case, the question
appears difficult.

An alternate approach would be on application of the
results of Section 2.2 to p(ro, r1, ---, r ; m) in hopes

n

of achieving a more convenient form for the computation of

 

‘7 I

p(m,n) = ,> ggj p(ro, r1, ---, rn; m).
r0+r1+' ' °+rn=m

A possible approach is illustrated below.

Case I
p(m,1) = Z p(ro, r1; m)
ro+r1=m
= Z Qr Qr (Cor. 2.10)
r0+r1=m 1 0
m ( >
= 2 Q Q = 1
r1=0 r1 r0
m m
= Z
r1=0 r1
Case II
p(m,2) = E : p(ro, r1, r2; m)

r0+r1+r2=m

Z I r I

= I; [[m mgrz [[m-r2 x(m-r2-r1)r2

r2=0 r2 r1=0

In a similar manner, p(m,k), k > 2, can be written

as sums involving powers of x and the function

3 = (x8 -1)(XS-1 -lli-°° Lxs+1 _ 1) .
(x - 1><x2 - 1) (xr - 1)

 

 

 

r
s
The function clearly can be computed recursively,
r
using either
s (xs _ 1) s-1
r (XS-r - 1) r
or
s (ss-r+1_1) s
r (xr - 1) r-1
where s > and:[[
Letting j = s - rr,[:= becomes
.+ . 1 . .
3 r = (X34. _ 1)(3(3+2 _ 1) ... (Xj+r _ 1)

r (x - 1)(x2 — 1) --- (xr - 1)

37
which is a familiar function in the theory of partitions.
This is the generating function which enumerates the parti-
tions in which the number of parts and the highest part
are limited by the numbers r and j respectively.
Considerable information is available concerning the
3+r

function . It is treated in Riordan [8] and
r

discussed extensively, occupying an entire chapter in

MacMahon's, Combinatory Analysis [5]. MacMahon utilizes

 

an approach by Cayley, referred toes Cayley's Transforma—
tion, to transform the product so that it may be broken up
into partial fractions. The notation, which is consistent
with the literature, arises from denoting 1 - xk by (k),
then

3'” ___ (j +1)(1+2) u +r)
(r) (r - 1) ... (2) (1)

CHAPTER III
THE CLASS EQUATION FOR R/an

Let R be a principal ideal domain, PID, and p a
prime of R. It will be assumed that the residue class
field R/Rp is finite and x = lR/Rpl. Consequently, the
number of elements of R/Rpn will be xn. The reader
will observe that several results developed in this chapter

have no need of this restriction. It is necessary for

counting procedures only.

3.1 The Number of Unimodular Matrices of Order m over

RZan

The following result will prove to be of basic import-

ance .

Proposition 3.1 A matrix A is unimodular over

R/an if and only if A is unimodular over R/an-l.

Proof: Let |A| denote the determinant of A and
adj A the adjoint of A. Supose |A| and a are rela-
tively prime, (|A],a) = 1. Then, there exist 5 and t
with

1 = s|A| + ta.
Consequently, to determine A—1 over R/Ra,
A(s adj A) = s |A| I s I mod a.
Thus, A_1 = 3 adj A over R/Ra.

38

39
Conversely, if A is unimodular modulo a then [Al

is a unit of R/Ra , i.e. (|A|, a) = 1.

But (IA , pn) = 1 is equivalent to (iA|,pn-1) = 1

 

and the result follows.

Proposition 3.2 The number Q(m,a) of unimodular

 

matrices of order m over R/Ra is given by

Q(m,a)=Nm2 7T (1-%)(1—-]—‘-2)...(1—.]_'m)
9‘3 X X
x = |R/Rpl
where N - |R/Ra|.

If a is a prime p, then the function Q(m,p) =
-1 .
(xm - 1)(xm - x) "’ (xm - xm ) which counts the number
of non-singular matrices of order m over a finite field

of x elements.

If R = z and a a rational integer,.then

Q(m,a) = am2 w (1 --l) --- (1 - 1m)
pla p P
which counts the number of unimodular matrices in integers
modulo a.

Variations of this prOposition occur frequently in the
literature. It is the author's belief that this was first
proven for integers by C. Jordan, Traité des Substitutions,
Gauthier-Villars, Paris, 1870. Other proofs for the rational
integers have occurred as recently as Stewart's Unimodular

Matrices in Integers Modulo m [9]; Brawley, Similar Involutory

Matrices (modpn) (1966) [11]; and by M. Rosen, Direct

40
Products of Cyclic Groups, Amer.-Math. Monthly 73, 55-57
(1966).
The finite field case is treated by Artin in Geometric
Algebra [1].
The proof is similar to one suggested by Referee's

Report on [9], Unimodular Matrices Modulo m.

 

Proof: Consider, for the initial case, Q(m,p) where
p is a prime of R. For this situation, R/Rp is a finite
field of x elements.

For R/Rp, if A is a unimodular matrix, i.e. non-
singular, then its rows must be linearly independent. Thus,
a count of the number of choices for each row will be given
with care taken to preserve linear independence.

The first row must have one non—zero element, hence
can be chosen in xm - 1 ways. The second row can be a
multiple of the first in x ways. Thus, one has xm - x

choices for the second row. Continuing, Q(m,p) becomes

Q(m,p) = (xm - 1)(xm - x) °-- (xm - xm-l) where x =
|R/Rp|, which, rewritten, becomes
2 1 1 1
amp) = x‘“ (1 -;><1 -§2) (1 -;m)

It will now be shown that

t+1) m2

Q(m.p = X Q(m,pt)-

Suppose A = [aij] is unimodular over R/Rpt. From A

construct A' = [aij] by choosing values of aij such that

41

. _ t
a.. = a.. mod p
13 . 13
. t+1 . .
where aij are elements of R/Rp . There eXist x chOices
2
for aij and, consequently, xm choices for aij; i =

1, "°, m, j = 1, ..., m. By Proposition 3.1, each A' so
constructed is unimodular. Thus,

2
xm oompt) :. o<m.pt+1>

But each unimodular matrix A' over R/Rpt+1

is congruent
to a unimodular matrix A over R/Rpt, so

m2

1
X Q(m,pt) = Q(mlpt+ )

Finally, it remains to observe that Q(m,a) is a
multiplicative function in its modulus; that is, for r
and s with (r,s) = 1,
Q(m,rs) = Q(m,r) Q(m,s).
It will be shown that for (r,s) = 1, there exists a bijec-
tion Y taking the set of unimodular matrices modulo rs,
Mrs’ to the product, Mr x Ms’ of the sets of unimodular

matrices modulo r and s respectively.

Let A = [ai ] be unimodular modulo rs and (r,s) =

j
1, then a.. can be written as a.. = sr.. + rs.. where
13 13 13 1)
rij and sij are elements of the complete residue sys-
tems mod r and s , reSpectively. The last statement
involves showing that if (r,s) = 1 and a1, ---, a1 and
b1, ---, bk are complete residue systems mod r and s,
respectively, then the set {sai + rbj] forms a complete

residue system mod rs. This is an easy exercise.

42

Define

 

by

Y[a..] = ([srij], [rsij]).

By the discussion above this is injective. If, when
[a..] is unimodular, then [sr..] and [rs..] are uni-
13 13 1]

modular. Since [ai ] = A is unimodular, (|A|, rs) = 1.

1
Therefore, both (|A|, r) = 1 and (|A|, s) = 1. Thus,

A is unimodular over R/Rr and R/Rs. But.

A = [aij] E [rsij] mod 3

A [sr..] mod r

a..
ij 13

II
III

so [rsij] and [srij] are unimodular over R/Rs and

R/Rr, respectively. 'Hence

Q(mIIS) 5. Q(m,r) Q(m:S)

Finally, Y is onto if, when B = [bij] and c =
[Cij] are unimodular mod I and s, then A = [aij] =
[sbij + rcij] is unimodular mod rs. Observe that ([A|, r)
= 1 since |A|

m
l[Sbij]l = S I

(s,r) = 1 and (|B|,r) = 1. Similarly, (|A|,s) = 1. Con-

Bl mod r and both

sequently, (|A|,rs) = 1 and A is unimodular over R/Rrs.
Thus Y is onto and

Q(mqr) Q(mqs) :.Q(m,rs).

To conclude, note that, if a = p131

Q(m. p31 £3?)

a a
=(2(m,p11) Q(mIPzz) "' Q(mlp:k)

a
--- pk k then

Q(m,a)

43
and the result follows.
Perhaps it would now be useful to remark to the reader
that Chapter V consists of an example of the formulas in

this chapter applied to 2 x 2 matrices over Z/an.
3.2 The Number of Matrices which Fix a Canonical Matrix

In this section the major result of the chapter will
be presented. The basic problem is to count the number of
matrices which are row equivalent to a Fuller canonical
matrix. It will be seen that this problem can be answered
by determining the number of matrices which "fix" a
canonical matrix under left multiplication.

A matrix X is said to be fixed by a matrix A if
AX = X.

Let m be an element of R a PID.

Lemma 3.3 Let P be a permutation matrix, then the

 

number of matrices which fix a matrix X over R/Rm

equals the number of matrices which fix PX over R/Rm.

Proof: It is easy to verify that the function q
where

n(A) = RAP-1

is a bijective mapping of the set of matrices which fix X
to the set of matrices which fix PX.

Let C be a canonical matrix over R/an where p
is a prime of R. Under multiplication by a suitable per-

mutation matrix P, the canonical matrix may be written as

44

 

 

where Xi contains all those rows of C, ri in number,

which had p1 as the diagonal element.

 

Example 5. Consider the following canonical matrix C.

Fpo * * 0 * * 0 *-
0 p1 * o a: 0 0 as
O 0 p2 O O O O 0
0 0 * p0 * x- 0 a:

c =

0 0 0 O p2 O 0 0
O 0 0 O O p1 O O
0 0 * 0 * O p0 0

__O O O 0 0 O 0 p2

 

 

 

 

 

 

FPO x» * 0 * * 0 aefl
0 0 * p0 * * 0 *
O 0 * O * 0 p0 * _. _
------------------------------------ X0
0 p1 * 0 * O 0 *

X = = x1
0 0 O 0 0 p1 0 *
------------------------------------ X2
0 o p2 o o o o o - -
0 0 0 O p2 0 0 0
O 0 0 O 0 0 0 p2

45

Now, let those columns of C which contained p1 as

a diagonal element be indexed C. , C. , °°-, c. .
11 1.2 1r.
1

These columns, after operation on the left by P, will

th

be denoted as the i column set of X.

 

 

 

 

 

 

 

 

Let in denote the matrix constructed by selecting
the ith set of columns of the block matrix Xj' For
Example 5, these become:

30 o 0‘ Z *‘ '1 * *-
X00 = 0 p0 O X01 = 0 * X02 = x * *

.9 0 0_J .D 0_J _: * *_

0 0 0] pl 0 . * .
X10 = X11 = X12 =

O 0 0 0 p1 0 0 *

3 o o- _o o- E2 o 0"
X20 = 0 O O X21 = 0 O X22 = O p2 0

9 0 0__J _O O- __O 0 92.

 

 

 

 

Three prOperties may be deduced from the Fuller

canonical form.
_ k
(I) xkk — p Ir

where II is an identity matrix

k k
of order rk
(II) xjk = z j > k
(III) xjk a 2 mod p3 , j < k

where Z is a zero matrix of the appropriate

size.

46

Properties (II) and (III) follow from (1) and (2)

of Theorem 1.1, that is d(aij)’:'d(aii) for all i and

j and that aij is an element of (R/an)/(R/an)ajj:
(I) is immediate.

Let A be a matrix which fixes X. The next result

will determine the form of A. Partition A into block

matrices in the following manner:

7 1
A00 A01 ‘°° Aon
A10 A11 °'° Aln
A = C . .
__Ano An1 ... Ann_

 

 

where Aij is of dimension ri x rj. For Example 5,

 

 

where,
A00 is 3 x 3
A01 is 3 x 2
A02 is 3 x 3
A10 is 2 x 3
A11 is 2 x 2.

that is,

 

 

 

 

 

 

 

A00 A01 ’ ' Aon X0 X0
A10 A11 ‘° Am 1X1 X1
_Ano Ani Ann; _xnd _xn_
Equivalently, require
n
_ < <
.Z Aki Xi — Xk for 0 k _.n.
i=0
Theorem 3.4 If AX = X, then
(1) For 0 j_k :.n-1.
_ n-k .
Ajk _ Z mod p (3 # k)
_ n~k
Akk = Ir mod p
k
(2) For 0.: i.: n,
A. are arbitrary.
in

2322::
and properties (I), (I
employed extensively.
0 :.k j,n—1, where at
i.e. the columns

' I

X.
1

Case k = 0

The proof of

(1)
I) and (III) on page 45 will be

will be presented first

The proof will be by induction on k,
each stap, the "critical“ columns,

defined on page 45, will be examined.

The requirement is

A X.

1

IIM’J

i o 01

Thus, it is necessary

set)

mod pn.

X0

th

that (considering the 0 column

But, by (II),

"M:
:v
x

o u E A x 0
. 0]. 10 00 00
l O ,

Hence, A00 X00 E X00, which by (I) (noting X00 5 Ir

ko

0

mod pn), implies A00 5 Iro.

Similarly, examining the 0th set of X for

n n

.§ Aki Xi E Xk mod p , k # 0

1-0
implies

= n

E Akixi0_xk0 mod p , kyéo.

i-o
However, by (1), x00 E I and, by (II), X E Z

ro
(k # 0), thus combining

_ = n
Ak0 X00 = Xk0 _ Z mod p

and

_ n
Aka X00 2 ARC Iro ' A-ko mod p ,

Z.

Ill

it is found that Ak0

This completes the case k = 0.

Therefore, let the induction hypothesis, denoted by
(H), be that the form described for A has been established
for column blocks 0, 1, 2, -'-, k-1.

Recall the classical number theory result (applicable
to PID's) concerning solutions of linear congruences: (T)

if ax E b mod m and (a,m) = d and d divides b,

49

then alx E b1 mod m1 where dal = a, dbl — b and

Consider the blocks in column k where 1 j k.: n-1.

It is necessary that

z n
(1) Ajo x0k + + A].n xmk —. xjk mod p
But, by (II), Xjk E Z for j > k, hence,
_ n
(2) Ajo x0k + + Ajk xkk e xjk mod p .

When 3 < k, the induction hypothesis (H) applied

to AjS and (III) applied to XSk give
_ n-s . s '
Ajs xsk -.(p Ajs)(p xsk)
_ n I a
— p (Ajs xsk)

Z mod pn , s # j

and

._ n-j . j '
A..X. _ + A.. x.
33 3k r- p JJ][p 3k]

E x mod pn.

jk
The proof of the first part of Theorem 3.4 now reduces

to three cases.

Case I: If j < k, equation (2) reduces to
x +A x =x mod n
jk jk kk “ jk p
which becomes
E Z mod pn.

Ajk ka
Apply (I) to xkk,

k _ n
Ajk(p Irk) _ Z mod p ,

50
which by (T), becomes

_ n—k
jk - Ajk r Z mod p .

H
III

A

Case II: If j = k, (2) becomes

I l
N

n
Akk ka - kk mod p .

By property (I),

k _ k
Akk(p Irk) : p Irk mod pn
which by (T), reduces to
_ n-k
Akk : Ir mod p .
R
Case III: If j > k, equation (2) becomes

_ n
Ajk ka = Xjk mod p .

Since j > k, from (III)

Ajk xkk a 2 mod p“.

But, as above, application of (I) and (T) give

k = n
Ajk(p Irk) _ 2 mod p

Z mod pn-k .

Ajk
This completes the proof of the first part of Theorem 3.4.
It will now be shown that the block matrices Ain'

O §.i j,n, are arbitrary. Again, it is necessary that

._ n
(3) Ajo xon + -- +Ajnxnn = xjn mod p

“Men S < n, the above results and property (III)

51

_ n-s I s |
E Z mod 9“ (S # j)
and

_ n-j - j -

A.. X. — I + A.. X.
33 3n ( rj p 33)(p Jn)
.. n
: Xjn mOd p 0

Therefore, two cases arise.

Case I: If j < n, then equation (3) becomes

_ . n
+ _
x 0 A n X —’ x c mOd p

reducing to

mod pn.

II
N

Ajn Xnn _

Case II: If j = n, (3) becomes

n
Ann Xnn f Xnn mod p

But, for both cases

x a p I

n
nn . Z mod p ,

I
n

thus, Ajn’ 0 :.j i.n, may be chosen arbitrarily.
This completes the proof of Theorem 3.4.

Employing the notation of the previous theorem one has.

Proposition 3.5 A is a unimodular matrix fixing X

if and only if Ann is unimodular.

Proof: Recall Proposition 3.1, that a matrix A is

unimodular_ mod pn if and only if A is unimodular mod

n-1. Consequently, if A is unimodular mod pn, A is

52

unimodular mod p. However,

— -1

I Z .... Z A

ID on
Z Irl 0... Z In

A E . . . . . mod p,
Z z .... I
rn_1 n-lln

z z .... Z

 

 

Since A is unimodular, |A| is a unit of R/Rp . Bqt

|A| = IA thus IA is a unit of R/Rp and this is

nnl' nnl

sufficient for Ann to be unimodular.

Conversely, if An is unimodular mod pn then An

 

n n
is unimodular mod p. But, as above, [AI = |Ann| mod p,
thus A is unimodular mod pn.

Proposition 3.6 The number of matrices which fix a
canonical matrix (C of type [r0, r1, ---, rn, m] over
R/an is

n irim
w x (m = dimension
i=0 of C).

2322;: By Proposition 3.3, it is sufficient to count
the number of matrices which fix X -- the permuted form of
C. But by Theorem 3.4, if AX E X mod pn then A (re-
ducing each column modulo the modulus above the column)

appears as:

53

 

 

 

 

 

 

 

 

 

 

 

mod p Imod pn-1 mod pn-z mod p1 mod pol
" I' l ; l ' f 1
I I z ' z ' z ‘ z r
r0 ' ‘ | ' l 0
_______ r-_--_.___.l._....______+ F———-——+—-—————T)-+—
U l | | 'I
z I I z . . z 2 r1
r1 | l , L I
....... L--—--—-—--------—— ------ _______‘
I ' I r O
A E ' m
_______ '.________‘—_________r +._._-___1._______+ .
z ' z ‘ z I ' I ' z r
I I ‘ I rn_1' n-1
——————— L————————L—————————f :———————7‘-———————qr#
( l I t
I
z ' z ' z ' I z . z r
I I I I 1n
.. l I - _.4.

 

 

 

 

Note that there exist xk choices for y modulo pn

such that y E a mod pn-k. Thus,

 

 

 

 

 

 

 

 

 

 

 

Column Count
mro
0 (x0)
' mrl
1 (x1)
n-1 mr _
n-1 (x ) n 1
n mr
n (x )
n irim
‘which, by mulitplication, gives w x choices for A.
i=0

54

Proposition 3.7 Let N[ro, r1, ---, rn; m] denote

the number of unimodular matrices which fix a canonical

 

matrix of type [r0, r1, ---, rn: m]. Then,
if, r = O
n
n-i ir m
N[rOI r11 ...: r ; m] = 7T X
n .
i=0
if r > O
n
rn
n ir m 1:1 (x1 - 1)
Nlro. r1. "°, r :m] = w x
n i=0 rn(fn+1)/2
x
Proof:
Case I rn = 0 For this case, the matrix A of

Proposition 3.6 is unimodular and the count given there

'will suffice, after deleting last row and last column.

Case II. rn > O For this situation, consider an
array analogous to the one presented in Proposition 3.6 with
the added condition, from PrOposition 3.5, that Ann be
unimodular. Thus by Proposition 3.2, the number of choices

for A will be
nn

Q(rn. p“) = (x“> " 51; (1 - 11:)

H
X

nr2 _
_ n 8-1

X {351+sz

rn(rn + 1)

. + 00. + = 0
Since 1 2 + rn 2

 

 

For the first (n - 1) - blocks of column n there

55

 

n (m-rn)rn th
are (x ) choices, and for the n block
Q(r , pn) choices. -Multi lying and observing the cancel-
n -nr2 nrg
lation of x n and x n , there are
rn
s
F (x - 1)
Xnmrn s=1
x rn(rn+1)f2

choices for column n. Applying the results for the columns

0 :.k :.n-1 from Proposition 3.6, the result follows.
3.3 The Class Equation for Row Equivalence over R/Bpn

From the results of Section 3.2, it will now be pos-
sible to determine the number of matrices row equivalent

to a canonical matrix.

‘0

Proposition 3.8 Let T[ro, r1, °°- r m] be the

n

number of matrices which are row equivalent to a canonical

 

matrix of type [r0, r1, °°°, rn; m], then
0 m. p“)
T[r0, r1, "°, 1: 7 m] = (
n N[I‘o, r1: 0"! In; In]

Proof: Let X be a canonical matrix of type
[r0, r1, ---, rn; m]. Without loss of generality, X may
be taken in its permuted form of Section 3.2.

There are as many matrices row equivalent to X as

there are matrices of the form Ax where A is a member

of the unimodular group M of Q(m, pn) matrices. By

56
Proposition 3.7, there are N[ro, r1, ---, rn; m] uni-

modular matrices which fix X. -These form a subgroup
MX of M.

Observe that AIX = Azx if and only if A1 and A;
lie in the same left-coset of “X' Thus, there are as
many distinct matrices AX as there are left cosets of
MX' Therefore,

TIIOI r1, '°°: In; m] = [M = Mx]

where [M : MX] is the index of MX in M. But

IMI

[MzMx] : lMxl

 

Q(m, pn)

N[r0' r1, 00., In; m]

and the proof is complete.

The results of this chapter may be summarized in the
following Class Equation for m x m matrices over R/an

under row equivalence.

 

2 ‘ ,
(xn)m = j} ggj T[ro,r1,--:,r ; m] p(rogr1,---,r ; m)
ro+r1+‘ ' °rn=m

An example of this equation is provided in Chapter V.

CHAPTER IV
THE EXTENSION TO R/Ra WHERE a = P131 P2

Let R be a principal ideal domain. The assumption
is still in effect that the number of elements of R/Ra
is finite for a in R. The problem now is to extend

the results of Chapters II and III to the general case,

32 pkak,

al

R/Ra, where a is composite, say a = p1 p2

4.1 A Variation of the Chinese Remainder Theorem

The following result, which is an adaptation of the
Chinese Remainder Theorem, will be useful in the general
case.

Let M be the complete matrix ring of order m over
R and let Mab"Ma’ and Mb be the matrix rings of order

m over R/Rab, R/Ra, and R/Rb, respectively, where a and

 

 

b are relatively prime, (a, b) = 1.
Proposition 4.1 There is a ring isomorphism A
A : Mab > Ma X Mb

'which sends the matrix [Xij] to the pair of matrices

b
([xij], [xi.]) where

J
a
_ b
xij _ xij mod b.

57

58

Proof: Consider the following diagram

\

n!
x <---—- 3

Ma Mb
where p and q are the natural homomorphisms onto the

quotient rings and p' and q' are the projections of the

product ring onto its factors. Define 5

 

B : M > Ma x Mb
by B([xij]) = (ptxijl. qlxijl)
_ a b
- ([xij] I [X13] )

The map B is a ring homomorphism onto Ma x Mb' It is
clear that B preserves addition. To check multiplication,

let T = [tij] and S = [sij] be elements of ,M and
b

T = [t?.] , s = [5a 1 , T = [t3.] , s . [s.

a 13 a ij b ij b '1 their

1]
respective images under p and q,

It remains to verify that

B(TS) = (Tasa. Tbsb)
m
The product TS = [rij] where rij = kil tikskj'
Consider
p(TS) = p([rij])

m
p([f tikskjl)

59

m
a a
[f tikskj]
=TaSa.

Similarly, q(TS) = T thus

b Sb'

B(TS) (p(Ts). q(TS))

(TaSa, TbSb)

and B is a ring homomorphism into Ma x Mb'

The image of B, Im B, consists of all the elements

of the product ring, since consider a pair ([sij], [tF.])

13
for sij and tij in R, because (a, b) = 1, aij and
bij 'can be found such that

s.. — t.. = a.. a + b.. b.
13 13 13 13

Therefore, take

x.. = s.. - a.. a
13 13 13
= t.. + b.. b
13 13
Then
B([x..]) = ([s?.] [t§.]). Thus B is onto.
13 13 ' 13
Finally, consider the kernel of B,
ker B = {[x..]| a divides x.. and b divides x..}
l] 1] 13 I
since (a, b) = 1, this kernel consists of matrices [xij]

with xij an element of Rab.

By the Fundamental Theorem of Ring Homomorphisms there

exists an isomorphism A

 

x : M/ker B > Im B.

60

But M/ker B = Mab and Im B = Ma x Mb and the proof is

complete.
. a1 a2 ak .

Thus, if a = p1 p2 °-- pk is the canonical de-
composition of a into a product of primes of R, then,
extending Proposition 4.1 in a natural manner, there exists
a ring isomorphism ,

k
> w M = M x M X --- x.M .
1 ai 31 32 3k

P
pi pg 2 pk

 

F: Ma

4.2 The Extension of the Fuller Canonical Form

It will first be illustrated how the Fuller Canonical

Form may be extended to R/Ra.

Proposition 4.2 If A is a left associate of B
over R/Ra, then A is a left associate of B over

a1 ak

R/Rpk where pk divides a. Conversely, if a = p1 ...pk
a.
and A is a left associate of B over R/Rpil for every

i , 1.: i :.k, then A is a left associate of B over

R/Ra.

nggfz Let U be unimodular over R/Ra and HA = B.
Then (|U|, a) = 1, hence (|U|, pk) = 1 for pkla, and
U is thus unimodular over R/Rpk. Hence A is a left
associate of B over R/Rpk.
On the other hand, if for each prime power divisor
of a there exists a unimodular matrix Ui with

a.
U A E B mod pil , then by Proposition 4.1, there exists

61
a matrix U over R/Ra such that

P(U) = (U1, U2, ---. Uk)

From the isomorphism established in Proposition 4.1 it

follows that UA = B over R/Ra and U is unimodular.
For the converse to be valid, it is clearly necessary

to have A a left associate of B for every prime power

divisor of a, for consider:

Example 6

Let R = Z and a = 6, then over Z/Z3,

2 O

O 1
is a left associate of

1 0

0 1

However, this is not the case over Z/ZG since 2 is
not a unit of Z/ZG .
Thus, by PrOposition 4.2, row equivalent matrices over

R/Ra are row equivalent over R/Rpil for each prime power

a.
1 O 0
factor pi of a. Hence, for a given row equivalence

class C;_ over R/Ra there corresponds a row equivalence

a.
class Ca over R/Rp.l and for each such class C over
i 1 31
pi pi
a

R/Rpil there is a canonical representative, the Fuller

canonical matrix C a .
i
Pi

62
Therefore, by Proposition 4.1, there exists a matrix
Ca over R/Ra such that
1‘(ca) = (c .---, c ).

a
911 ak
This matrix will be row equivalent to each matrix of the

a..
class (Ba since it is row equivalent over R/Rpil for

each prime power divisor of a. This matrix, Ca will be
called the canonical matrix of the given class. 'This
canonical matrix Ca will not be easy to describe, but it
will be unique because for each residue class the canonical
representative is unique.

flag

It is easy to see then that the function forhtotal

number of canonical matrices is multiplicative in its
modulus. Altering the notation slightly, if p(m, a)
is the number of canonical matrices over R/Ra and

a

a a k
a = p11 p22 .... pk ’ then

ak

p(m,.) = p(m.p?1>p(m.p§2> p(m.pk ) .

4.3 Extensions of Counting Formulas

It has already been observed (Section 3.1) that the
number of unimodular matrices over R/Ra is multiplicative
in its modulus, i.e. if (p,q) = 1, then Q(m,pq) =
Q(mip)Q(m,q) -

It remains to convince oneself that the counting func-

tion for the number of matrices which fix a canonical matrix

63

is multiplicative. But this is not difficult to see, sup-

a a
pose a = p11 p22 --- pk and that Ui is a unimodular

matrix Ci over R/Rpil. By Proposition 4.1, there exists
a unique unimodular matrix U and canonical matrix C

over R/Ra with

1"(U)=(U1,U2, Uk)
P(C) = (C1, C2, °°'a Ck).

Moreover, since Uici = C1 for every i, UC = C. Thus
to count the choices for U , it is necessary only to count
the choices for each Ui’ but this is determined from the
last chapter.

Therefore, the counting formulas for R/an may be

extended to R/Ra where pn divides a.

CHAPTER v
AN EXAMPLE: MATRICES OF ORDER 2 OVER z/Zpn

To illustrate some of the earlier formulas, to demon-
strate some of the techniques (Theorem 3.4), and to serve
as a partial check, this chapter is provided. Its object

of concern will be 2 x 2 matrices over Z/an. It is

4
clear that the total number of matrices will be (pn) —
p4n and the number of unimodular matrices will be

n n 4 1 l
Q(Z:p ) = (p ) (1 - §)(1 --2)

5.1 Total Number of Canonical Forms

By a direct count of the choices for the matrix

k
a

l
P I

the total number of canonical matrices will be computed.
Note that, if 1 Z.k, then there are pl.k choices for
a and 1 choice for b ; and, if k 2.1 + 1 then 1

pk-(l+1) choices for b. Allowing k

choice for a and
to vary from 0 to n, the following table gives the num-

ber of canonical matrices for each choice of k.

64

65

 

 

k No. of Matrices, 0.: 1.2 n
n
0 2 pk
k=0
n
1 ,2 pk"1 + 1
k-1
n _ 1
2 2 pk 2 + 2 pk
k-2 k=o
n _ 2
3 2 pk 3 + 2 pk
k=3 k=o

 

 

 

 

 

n-1 Z + 2 p
k=n-1 k=0
n—l
n 1 + 2 pk
k=o
n k in+1 _ 1
Using the fact that Z x = 1 , and
k=o x -

summing the entries in the table, the total number of

canonical matrices, p(2,n), becomes

n+1 k _ 1 n k _ 1
P(2:n) Z E—-:—T'+ .2 E——:—I—

k=1 p k=1

n+1 _ 1 n k _ 1
p + 2 2 ‘E—————
p - 1 k=1 p - 1

n-1 k
— 1) + 2p( 2 p ) - 2n
_ ~ =0
p - 1

(pn+1

66

‘ n
(pn+1-- 1) + 2[p(%:-}-) - n]

(p-l)

 

By rearranging and summing, p(2, n) may also be

written as

k

p(2, n) = (2n — 2k + 1)p .

IIMD

k 0
This second formulation gives rise to an interesting ob-

servation. Consider the function

 

Fn(x) =

and its derivative

F$(x) = (n - 1) xn-'2 + --- + 1.
Then,

n n-1

p(ztn) = p Fr'1+1(E1>') + p FAQ?)-

5.2 The Number of Matrices which Fix a Canonical Matrix

This section will provide an example of the techniques
of Theorem 3.4. Consider the canonical matrix of Section

5.1,

a

1
P

The problem is to determine the number of matrices X,

x11 x12

X21 X22

67

such that XC E C mod pn . Equivalently, determine Xij'

satisfying the system

k k
()1) Xllp + X121) 5 p
(2) xlla + xlzp : a n
3 k mod p
( ) X21? + Xzzb = b
l ' l
(4) X21a + Xzzp E p o

This requires three cases, each dependent on the relation

between k and 1.

Case I If k < 1, then b = O and a = Ap ,

since d(a) :.k. Equation (1) implies

xllpk 5 pk mod pn
x11 E 1 mod pn-k.
From equation (2),
xlla + x12p1 a a mod pn
Xizp 5 (X11 ' 1)a mod Pn
E (Bpn'k) (A19k )
E 0 mod pn ,

implying x12 E 0 mod pn-l.

By (3), x21pk a 0 mod pn and, thus, x21 E 0
mod pn-k.
Finally, (4),

n-k k
(Cp )(Ap ) + x22p

ll
'U

1 “ 1 mod pn

H
'0

mod pn- .

H!
H

x22

68

Case II If k = 1,
pk o
C = k
P
and similar to (I),
X11 E 1 mod pn-k x12 E 0 mod pn-1
x21 E 0 mod pn_k x22 E 1 mod pn-l.
1+1
Case III If k > 1, then a = O and b = Ap .
From (2),
x12p E 0 mod pn
x12 E 0 mod pn-
Then (1) becomes
XiiPk + fiizb 5 Pk mod Pn
k n-l 1+1 k n
X11? + (39 )(AP ) E P mod P
x11 E 1 mod pn-k.
_ n-k _ n-l
Analogously, x21 = 0 mod p , x22 = 1 mod p .
For all three cases,
x11 5 1 mod pn-k x12 5 0 mod pn-l
x21 5 0 mod pn-k x22 E 1 mod pn-l.

Counting the choices for each xij’ there are

pk pk p1 p1 = p2k p21 matrices which fix the canonical

matrix C over Z/an. Clearly, this agrees with Theorem
3.4.
To determine the number of unimodular matrices which fix

C there are three cases, r = 0, r = 1, r = 2-
n n n

69
Case I If rn = 0, then neither k nor 1 is
equal to n, and each of the above matrices is unimodular

since they are congruent to

1 0
mod p .
O 1
Case 11 If rn = 1, say k = n, then x11 must
be a unit of Z/an, since modulo pn-l
x11 0
x E
x21 1

Therefore, there are ¢(pn) choices for x11, where ¢
is the Euler ¢-function, and pn choices for x21. Con-
sequently,

n n l l 21 n n 1
¢(p)ppp=p p[p(1--§)]
21 2 - 1
‘p pn[E-E'—]

matripes fix the canonical matrix.

Case III If rn = 2, then

 

0 0

O O

and all unimodular matrices, p‘n(1 — %)(1 - $3) in number,
fix C.

These results agree with Section 3.2.

70

5.3 Calculation of p(ro, r1, -°°, r ; 2)

By direct calculation,

p(O: OI °°°I 0! r

l’ k'
1 if k = 1
pk-1 (Lg—E) If k z. 1 + 1
where r1 = 1, rk = 1.

By Corollary 2.10,

p(m, 0,: o, 0,r o o; 2) =0 0

l k rk~rl
where rk = r1 = 1.
If k = 1, then Q = Q = 1.
rk 1:1
If k 1.1 + 1, then Qr = 1 and
l
r m
k
Q = [A ]
rk k r

k

= (pk'1‘1>1 (L—E, : 1;)

k-l 1
- p (Lg-fl

and the results agree.

5.4 The Calculation of T[ro, r1, °--, rn; 2] and the

Class Equation

Three cases, In = 0, rn = l and rn = 2, are needed

to determine T = T[O,---, r1, 0 --- O, O --- O: 2].

rk,

71

 

 

Case I If rn = 0,
9124.221
T ‘ N
where N = N[O, ---, 0,rl,0, "', 0,rk,O,---,0; 2], thus
4 1 1
P n(1 - —Q(1 ' '3)
T — p p .
2k? 2I’
P P
Case II If rn = 1,
4 1 1
p “(1 - ->(1 - -2)
T = 2k 51 I
p p (1 --)

Case III Finally, if rn = 2, then

Letting P = p(o,---o,r o °'°,O,r o -o-,o; 2),

ll I

these results may be summarized as,

 

 

 

Case Value of TB
r = 1
k 4n .l _‘l .
(1) r1=1 p (1-p)(1 pz) k-1(1+1)
2k 21 p p
k > 1 - p p
r = 0
n

k = 1
<2) rk = 2 [p‘m‘ku --:;><1 - 12)] [11

p
n = o
(3) {In = 1 ”'Zkfl - 3- ) “‘k 1 + l)
rk = 1 P p2 p ( p
(4) r = 2 [1] [1]

 

 

 

 

72

The class equation (Section 3.3)

 

 

 

n m2 ‘:> ‘j
(x ) = 1 T[ro,r1,---,rn;m] p(ro,r1,---,rn;m)
r0+r1+---+rn=m
for the case Z/Zpn and matrices of order 2 becomes
4n > fl
p = A T[r0,r1,'°°,r ; 2] p(ro,r1,°",rn; 2).

 

ro+r1+'°'+rn=2 D

To illustrate the behavior of the right side of the
above equation; the sum with appropriate values of T and
P will now be computed.

The 4 cases given in the table on page 71 are
treated by the sums 21, 22, £3, 24.

Consider the first case where rk = 1, r1 = 1, k > 1

and r = 0:
n

 

(1) 21 = Z TE
n>k>l
4n 1 1
- p (1'- P)(1- 52) k-l 1
' 2k 21 p (1 + E)
n>k>l p p
= (p2-1) Z [p4n-k-31-2 _ p4n-k-3l-4]
n>k>l
— —1
= (p2_1)n22 “Z [p4n-k-3l-2 _ p4n-k-3l-4]
1:0 k=l+1
The following lemma is now useful.
Lemma
r+t
s-k s-k-2 s-r s-r-1 s— +t -1 s- +t -2
2 (p - p ) = p + p - p (r ) -p (r )

k=r

73
ggggg: Observe the behavior of the exponents.
Separate the sum into two parts, one with odd exponents,
one with even exponents. Each part is a telescoping sum
and collapses.
Now apply the lemma with s = 4n - 31 - 2, r = l + 1,

and r + t = n - 1.

11-2
- 4n—4l—3 4n-4l—4 an—ai-z 3 -31—3
21 - (p2-1) 2 [p + p - p - p n

1=o

]

The summs 22 and 23 will be treated together.

22+23= ZTB+Z TE
n>1 n>l
r =0 r =1
n n

n>l P P
2 -2l 1 n—l 1
+ len (1'52)][ (1+—)1
n>l
n-1 4n-41-2 4n-4l-3 3n-31-2 3n-31-3
‘ (92-1) 2 [p - p + p + p 1
=0

Combining 21 with 22 23,

21 + Z2 + 23 = (92 - 1){p2 - p + p + 1}

11-2

4n—4l-4 4n-4l-2
(p )

+ P
l=0

where the first summand arises from the case 1 = n - 1
and in the second sum cancellation between 21 .and 22 + 23

occurs. Thus,

21 + Z2 + 23 = (pa-1)(1+pz+p‘+p6+°--+p4n'4+p‘n-2)

411-1

P

74
Finally, since 24 = 1,

p4n = 2 TE = 21 + 22 + 23 + 24

which is the desired result.

As an illustration, consider:

Example 7 Let R = Z, p = 5, m = 2, n = 2,
that is, 2 x 2 matrices over Z/Z52

Denote T[ro, r1, r2; 2] by Tror1r2

p(ro: r1: r2: 2) by prorlrz

Then, the Class Equation becomes

(52) = E : T[ro, r1, r2; 2] p(ro. r1, r2; 2)
ro+r1+r2=2

= T200 P200 + T110 P110 + T101 P101 + T020 P020

+ T011 P011 + T002 P002-

Evaluating by the preceding table,

390625

300000[1] + 12000[6] + 600[30]

+ 480[1] + 24 [6] + 1[1].

 

 

Further,
2 _
(2 2) _ (53 - 1) + 2[5(§ _ i) - 2]
p ' ' ‘ (5 - 17

= 45.
Thus for m = 2 over Z/Z52 there are 390625 matrices
separated by row equivalence into p(2,2) = 45 classes.
For each class the distribution is as follows:
(1) 1 class of type [2, 0, 0; 2] containing 300000
matrices (this class contains all the unimodular

matrices).

75

(2) 6 classes of type [1, 1, 0; 2], each containing
12000 matrices.

(3) 30 classes of type [1, 0, 1; 2], each containing
600 matrices.

(4) 1 class of type [0, 2, 0; 2], containing 480
matrices.

(5) 6 classes of type [0, 1, 1; 2], each containing
24 matrices.

(6) 1 class of type [0, 0, 2; 2],(the zero matrix)
containing 1 matrix.

If the reader is interested in further results for

2 x 2 matrices, consult [14],[16],[20] and [22].

CHAPTER VI
CONCLUDING REMARKS

It is worthwhile to remark on other matrix and/or com-
binatorial problems which arose during the work on this
thesis.

(I) This research dealt with the counting of certain
equivalence classes of matrices over R/Rm. For some
purposes, two matrices might be put into the same class if
they differtonly by a permutation of rows and/or columns.
Counting these equivalence classes seems to be a very dif—
ficult problem. This problem with additional restrictions
is discussed by A. W. Tucker, A Combinatorial Equivalence

of Matrices in Tenthygymposium in Applied Mathematics

 

published by the American Math. Society. It was suggested
to the author in Referee's Report Unimodular Matrices in
Integers Modulo m [9].

It is conjectured by the author that a possible approach
is to observe that row and column permutations are induced
by permutation matrices operating on the right and left of
the matrix. Also, it is well known that, if G is a per-
mutation group acting on a set X, then the number of equi-
valence classes on X (number of orbits) induced by G is
N where
(1) N = 7&7. Z F(g) (Frobenius-Burnside)

96G

76

77
where |G| is the order of G and F(g) equals the
number of elements of X left fixed by 9.
Thus, in the above situation, one has two permutation
groups G and H acting on the set of matrices X with

the property
g(xh) = (gx)h g e G, h e H, x e X.

Therefore, it may be possible to develop a formula analogous
to (1) and apply it for the case of the two permutation
groups. A detailed discussion of the use of (1) as a
counting device is given in N. G. DeBruijn's, Polya's Theopy
of Counting in Applied Combinatorial Mathematics (John

Wiley and Sons) edited by E. F. Beckenbach.

(II) It is well known that over a PID, matrices are
row equivalent to a certain canonical form (see [6],
Matrices with Elements in a Principalpgdeal Ring). The
question arises, if one allows operations on the right by
permutation matrices, what is the resulting canonical
matrix? This canonical matrix would lie between the Hermite
row equivalence form and the canonical matrix under equi-

valence operations.

(III) This thesis dealt more with the generalization
of the theory over finite fields than with properties of
PID's. And in this respect, results for matrices over a
finite field were found to extend nicely. There is also
considerable literature available concerning enumeration

problems of this type over finite fields (see Bibliography,

78
Part C), with little of this being extended ([11], [15] and
[19]). This would seem to be an extensive source of new
counting problems over residue classes of rational integers

or of PID's.

BIBLIOGRAPHY

The bibliography is presented in three sections.

The initial part concerns those books, papers and com—
munications which dealt directly or provided background for
the material in this thesis.

The second section presents a partial summary of the
results of matrices over rational integers and residue
classes of rational integers. The emphasis is on those
articles published since Taussky's 1960 survey [22].

Since this thesis was more a generalization pf the
theory over finite fields than based on the properties of
principal ideal domains, the third section contains an
extensive bibliography concerning matrices over finite
fields. >It should be noted that the approach is from the
aspect of matrix theory and not linear groups. Consequent—
ly, Dickson's Lipear Gnams is the only reference on linear

groups and other articles, such as Artin's, The Orders of

 

Linear Groups, are not included.

Part A

[1] Artin, E. Geometric Algebra. New York: Interscience.
1957-

[2] Fuller, L. E. A Canonical Set for Matrices over a
Principal Ideal Ring modulo m. Canadian J. Math
7, 54-59 (1955).

[3] Hall, M., Jr. Combinatorial Theory. Massachusetts:
Blaisdell, 1967.

79

80

 

[4] Leavitt, W. On Matrices with Elements in a Princi al
Ideal Ring. Bull. Amer. Math. Soc. ‘55, 117-1I8
(1949).

[5] MacMahon, P. A. Combinatory Analysis. New York:
Chelsea (1915).

[6] MacDuffee, C. C. An Introduction to Abstract Algebra.
New York: Dover((reprint) (1966).

The Theory of Matrices, Berlin: Springer-Verlag
(1933).

Matrices with Elements in a Princi al Ideal Rin .
Bull. Amer. Math. Soc. 39, 564-584 (1933).
[7] Marcus, M. and H. Minc. A Survey of Matrix Theory

and Matrix Inequalities. Boston: Allyn and
Bacon (1964).

 

 

[8] Riordan, J. An Introduction to Combinatorial Analysis.
New York: John Wiley (1958).

 

[9] Stewart, B. M. The Class Equation with ReSpect to
Row Equivalence of Matrices over a Finite Field
(Personal Communication).

Unimodular Matrices in Integers mod m. (Personal
Communication).

[10] Zariski, O. and P. Samuel. Commutapive Algebra, Vol. I.
New York: D. Van Nostrand (1958).

Part B Matrices over Rational Integers and Residue
Classes of Rational Integers.

[11] Brawley, J. V. Similar Involutory Matrices (modpn).
Amer. Math. Monthly 13, 499-501 (1966).

[12] Dade, E. C. and O. Taussky. Some New Results Con-
nected with Matrices of Rational_1ntegers. Proc.
Sympos. Pure Math. Vol. VIII, 78-88. ProvidenCe:
Amer. Math. Soc. (1965).

 

[13] Faddeev, D. K. On the Equivalence of Systems of
Integral Matrices(Russian). Izv. Akad. Nauk.
SSSR Ser. Mat. g9, 449-454 (1966).

[14] Foster, L. L. On the Characteristic Roots of the
Product of Certain Rational Integer Matrices of
Order Two. Pacific J. Math. .18, 97-110 (1966).

 

[15]

[16]
[17]

[18]
[19]
[20]

[21]

[22]

Part C

[23]

[24]

[25]

81

Hodges, J. H. .IdempptenEMaErices (mod pa). Amer.
Math. Monthly 1;, 276-278 (1966f?

A Determinantal Congruence Related to Bilinear
Forms (mod'gij Math. Z. 33, 65-69 (1966).

Representations by Bilinear Forms (mod pa).

Ann. Math. Pura. Appl. (47 ii, 93-99 (1966).

Some Integral Matrix Equations. Portugal Math.
33, 55-66 (1964).

Jacobson, B. and R. J. Wisner. 'Matrix.Number Theory
;, Factorization of 2 x 2 Unimodular Matrices.
Publ. Math. Debrecen 33, 67-72 (1966).

 

Levine J. and R. R. Korfhage. Automorphisms of Abelian
Groups Induced by Involutory Matrices, General
Modulus. Duke J. Math. 33, 631-654 (1964).

Pall, G. and O. Taussky. Scalar Matrix uadratic
Residues. Mathematika 33, 94-96 (1965).
Reiner, I. The Matrix Congruence_x2 E I mod a.
Amer. Math. Monthly 31, 773—774 (1960).
Rosenfeld, A. ‘A Note on Matrix Quadratig_Residues.

Amer. Math. Monthly 14, 804-810 (1967).

 

 

 

 

Suprunenko, D. A. On Conjugacy of Matrices Over
Ring of Residues. (Russian). Dokl. Akad. Nauk.
BSSR 3, 693-695 (1964). ’

Taussky. O. (A Survey Article with Extensive Biblio-
graphy) Matrices of Rational Integers. Bull Amer.
Math. Soc. '33, 327-345 (1960).

Ideal Matrices I, Arch. Math. ‘33, 275-282 (1962).
ideal Matrices 1;. Math. Ann. 150, 218-225(1963).

The Literature on Matrices over a Finite Field
(emphasis on enumeration).

Berlekamp, E. R. Distribution of Cyglic Matrices in
a Finite Field Duke Math. J. 33, 45-48 (1966).

Boros, F. On Matrices in a Finite Field (Romanian)
Lucrar. Sti. Inst. Ped. Timisoara Mat. Fix.
(1961), 41-47.

Brawley, J. V. Enumeration of Canonical Sets by Rank.
Amer. Math. Monthly 22, 175-177 (1967).

82

[26] Brenner, J. L. G-circulant Matrices over a Figldgf
~Prime Characteristic. IllInois J. Math. ‘1, 174-
179 (1963).

[27] Carlitz, L. Note on a Conjecture of Andre Weil. Proc.
Amer. Math. Soc. 5, 5-9 (1953).

 

A Problem Involving Quadratic Forms in a Finite
Field. Math. Nach. 11, 135- 142 (1953).

A Reciprocity Formula for Weightedgguadratic
Partitions. Math Scand. 1, 286- 288 (1953).

 

 

Some Special Equations in a Finite Field. Pacific
J. Math. 3, 13-24 (1953).

 

Weighted Quadratic Partitions over a Finite Field.
Canadian J. Math. 5, 317- 323 (1953).

Invariant Theory of Systems of Equations in a
Finite Field. J. D'Analyse Math. 3, 382e413

(1953/54].

Pairs of Quadratic Equations in a Finite Field.
Amer. J. Math. .13, 137-154 (1954).

 

Representations by.Skew Forms in a Finite Field.
Archiv. Math. ‘3, 1-3 (1954).

 

Representations byggu uadratic Forms in a Finite
Field. Duke Math. J. 21, 123- 138 (1954).

 

The Number of Solutions of some Special Equations
in a Finite Field. Pacific J. Math. .4, 207-217

(1954).

A Note on Nonsingular Forms in a Finite Field.
Proc. Amer. Math. Soc. .1, 27-29 (1956).

Solvability of Certain Eguations in a Finite Field.
Acta. Arith. 7, 389-397 (1962).

Simultaneous Representations in Quadratic and

_—

Linear Forms over GF[g,x]. Duke Math. J. 33,
259-270(1963).

 

 

Classes of Pairs of Commuting Matrices over a

Finite Field. Amer. Math. Monthly 70, 192- 195
,(1963). [Note also: A Correction for "Classes

of Pairs of Commuting Matrices over a Finite Field."
Amer. Math. Monthly 11, (1964)] .

 

83

A Note on_guadrics over a Finite Field. Duke
Math. J. 33, 453-458 (1966).

Restricted Product of the Characteristic Poly-
nomials of Matrices over a Finite Field. Illinois
J. Math. .11. 128 - 133 (1967).

[28] Carlitz, L. and J. H. Hodges. Representations by
Hermitian Forms in a Finite Field. Duke Math. J.
33, 393-406 (1955).

Distribution of Bordered Symmetric, Skew and
Hermitian Matrices in a Finite Field. J. ffir
Mathematik 195, 192-201 (1956). -

Distribution of Matrices in a Finite Field.
Pacific J. Math. 3, 225-230 (1956).

 

[29] Daykin, D. E. Distribution of Bordered Persymmetric
Matrices in a Finite Field. J. Reine Angew. Math.
203, 47-54 (1960).

 

On the Rank of the Matrix f(A) and the Enumeration
of Certain Matrices over a Finite Field. J.
London Math. Soc. 33, 36-42 (1960).

On Linear Congruences over a Finite Field. Am.
Math. Monthly 13, 637-642 (1963).

[30] Dickson, L. E. Linear Groups. New York: Dover
Reprint (1958).

 

[31] Hodges, J. H. Representations by Bilinear Forms in
a Finite Field. Duke J. Math. 33, 497-509 (1955).

 

Exponentialggums for Symmetric Matrices in a
Finite Field. (Math. Nachr. 33, 331-339 (1955).

 

Weighted Partitions for General Matrices over a
Finite Field. Duke Math. J. 22, 545-552 (1956).

 

Exponential Sums for Skew Matrices in a Finite
Field. Arch. Math. '1, 116-121 (1956).

Weighted Partitions for Symmetric Matrices in a
Finite Field. Math. Zeitschr. 33, 13-24 (1956).

 

The Matrix Equation AX_- B in a Finite Field.
Amer. Math. Monthly .Q3, 243-244 (1956).

 

Some Matrix Equations over a Finite Field. Ann.
Mat. Pura.-App1. 22, 245-250 (1957).

84

Distribution of Bordered Matriceg‘in a Finite
Field. J. Reine Angew..Math. 198, 10—13 (1957).

 

Weighted Partitions for Hermitian Matrices oveg
a Finite Field. Math. Nachr. '31, 93-100 (1958).

 

The Matrix Equation X2 f l_= 0 over a Finite Field.
Amer. Math. Monthly 33, 518-520 (1958).

Scalar Polynomial Equations for Matrices over a
Finite Field Duke Math. J. 33, 291-296 (1958).

Some Determinantal Equations over a Finite Field.
Math. Z. 13, 355-361 (1959).

 

Some Polynomial Equations for Determinants over a
Finite Field. Monat. Math. 33, 322-329 (1962).

Generalized Weighted m-th Power Partitions over
a Finite Field. Duke Math. J. ‘33, 405-412 (1962).

 

A Note on Systems of Matrix Equations over a Finite
Field . Portugaliae Math. ‘33, 99-106 (1962).

A Bilinear Matrix Equation over a Finite Field.
Duke Math. J. 13;, 661-666 (1964).

Simultaneous Pairs of Linear and_guadratic Matrix
Equations over a Finite Field. Math. Zeitschr.
.§$. 38-44 (1964).

Determinantal Equations Related to Hermitian Forms
over a Finite Field. Monatsh. Math. ‘33, 215-224
(1965).

A Symmetric Matrix Equation over a Finite Field.
Math. Nachr. 39, 221-228 (1865).

The Matrix Equation AXC = B over a Finite Field.
Riv. Mat. Univ. Parma 3, 79-81 (1965).

A Skew Matrix Equation over a Finite Field. Arch.
Math. ‘31, 49-55 (1966).

A Hermitian Matrix Equation over a Finite Field.
Duke Math. J. 33, 123-129 (1966).

Some Pairs of Matrix Equations over a Finite Field.
Scripta. Math. '31, 289-301 (1966).

Comments on InvolutoryiMatrices. Amer. Math.
Monthly 13, (1966).

85

[32] Korfhage, R. R. and J. Levine. Automorphisms of
Abelian Groups Induced by Involutory Matrices.
Duke Math. J. 33, 631-646 (1962).

Automorphisms of Abelian Groups Induced by In-
volutory Matrices Modulo p > 2. Duke Math. J.
30, 161-170 (1963).

[33] Sah, C. A Note on Hermitian Forms over Fields of
Characteristic 2. Amer. J. Math. .33, 267-270
(1964).

Section

THE APPENDIX

I An Example:

 

Section

order 3 over

The Canonical Matrices of
Z/sz.

II The Field Case

 

Section

III Tables for p(ro, r1, ---, r ; m), m 2,5.

 

Section

IV An Example:

Extension to General Modulus

86

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

-.m E o1 u «a 0 OJ #3 o o: 1.3 o o.
o «a o Amy an o c He o o Hm o
0 Adv Hm Amv o Hm o o an o o HAL
1mm 0 GJ 1 He 0 ol 1% o m. ind o e1
Aumv cm 0 Adv em 0 o em 0 o «a o
Ffimv 0 eat .I o 0 Ho! F o o Hal _IAamv :3 ohm.
lam o o1 I em 33 on use o o: 1 e o o:
o «m o o «a o Amv He o c He o
Adv Anmv em 0 Ammv emu Anmv Adv em Adv Adv em
I I .I I l I L
1% o o: i «a e on He o o: 1% o m.
o .e o knee am e Ame om o o am e
r o as .31 Lee o om [E 0 can u o e at.
"ACOADHmom map How mmofloso xm mmumoflpcfl :Axmv= pom . o mamsmc .COHUHmom
map How mofiono mco mmumoflpcfl =o= Hogan: who .pmumoflocfl mm ma ucmsmam Hmcomm

IHU msav «QN\N Eon mucmsmam £0H3 m HwUHo mo mmofluume Hmoflcocmo $39

 

mamamxm Gd H cospomm

87

88

 

 

m + «mm + MQN

o
0..

«Q + «m
H + m
H + m

H + m

 

 

 

 

 

0‘

0‘

O.

HNCNH

O

.R + mm + New + adv + «an

~va
..anw
sHVQ
.ovm

~0vm

 

 

 

 

 

 

«m + mm + «m

H+Q+Nnm

 

 

Am
Am
H n Am
H n An
Am

 

 

II
N
O“)
V

AmmL

 

 

 

Section II The Field Case

The residue class R/an when n = 1, under the
finiteness assumption, is a finite Galois field GF(qs) of
x = q5 elements. It is worthwhile to note how the count-
ing and recursion formulas specialize to n = 1. These
formulas are known from the study of finite projective
geometries (See [1], [3]) and it was The Class Equation
with Respect to Row Equivalences of Matrices over a Finite
Field by B. M. Stewart [9] which gave rise to this thesis.
The formulas below plus additional results are found in [9];
however, the choice of notation is consistent with this
paper.

The function p(m,1) becomes the total number of

Hermite canonical forms and p(ro, r1; m) counts the num-

ber of canonical matrices of rank r0. Then

m
p(m.1) = Z p(ro. r1; m) = Z p(ro, m-ro; m)
By letting,
r1'1 r1_ r1
5 : L-l ’ S : 1
r0 xr0_ 1 0

then (Proposition 2.5)
r1-1

F(r0v r1-1; m) = Sr P(ro‘1v r1; m).
o .

That is, multiplication of the number of canonical matrices

r -1
of rank r0 — 1 by Sr1 gives the number of canonical
o

89

90
matrices of rank r0. Similarly,

m

Tr=2£r_-:_l_l T0=1
O X0_1

and

P(r0v r17 m) = T p(ro-l. r1; m-l),

ro
from Proposition 2.6.
The number of non—singular matrices of order m is
m-1 m i
Q(m,1) = w (x - x ).
i=0
If T[ro, r1: m] is the number of matrices row

equivalent to a canonical matrix of rank r0, i.e.

type [r0, r1; m], then (Proposition 3.7)

g(m. 1)

T[ro, r1; m] =
Xrorl Q(rlll)

Finally, the class equation

2
xm = Z T[r0, r1; m] p(ro, r1; m)

ro+r1=m -
Example (B. M. Stewart [9])

If x = 3 and m = 3, then the class equation is

39 = 1(1) + 26(13) + 624(13) + 11232(1).
Thus over GF(3), there are 39 = 19683 matrices of order
3. These are separated by row equivalence into p(3,1) =
28 classes. The distribution by classes is as follows:

(1) 1 class of rank 0 containing 1 matrix,

(2) 13 classes of rank 1 each containing 26 matrices,

91
(3) 13 classes of rank 2 each containing 624
matrices,
(4) 1 class of non-singular matrices containing
11232 matrices.
It was stated in Section 2.3 that if n = 1 then
p(m,n) could be defined recursively. This will now be
shown.

Assertion: p(m+1, 1) = 2p(m,1) + (Xm-l) p(m—l, 1)

where p(1,1) = 2 p(2,1) = 3 + x.
Proof:
p(m+1,1) = 2 p(ro, r1; m+1)
r0+r1=m+1
\—_—1

= 2...; [p(ro-l. r1; m) + Xr°p(ro,r1-1: m)] (PrOp. 2.3)
:0 +r 1=m+1

:;"“ ‘ r
2 ...; P(ro: r1; m) + :L__J (X 0’1) p(ro. r1; m)

ro+r1=m r0+r1=m

-——1
2 p(m,1) + 2 , (xm - 1) p(ro-l, r1;m-1)
ro+r1=m

(Def. of p(m,1); Prop. 2.6)

2 p(m,1) + (xm — 1) p(m-1,1).

Unfortunately, this procedure does not suffice for n > 1.

p(ro,r1,ra.r3;xn)

and various choices of

Tables for

Section III

 

r2, r3.

r1,

r0,

 

 

 

 

 

 

 

 

 

 

 

 

H Avx+mx+nx+x+Hvex Aux+HVAvx+mx+ux+x+Hvex H m
Aux+HvAvx+mx+ux+x+Hvox Avx+nx+ux+x+vax
H Amx+nx+x+vax Anx+HVAnx+x+vax Amx+nx+x+vax H v
H Aux+x+vax Aex+x+Hvux H m
a I u e
H E H H Ax+Hvx H m
o u mH u HH
mHmn3 H H H
E
m H. m N H O H.H
AE “O .NH .0 .ova .N mHQme
H Avx+mx+ux+x+HVAmx+Hv wa+mx+mx+x+HVAux+Hv vx+mx+ux+x+H H m
vx+nx+ux+x+H
H mx+ux+x+H Aux+x+HVAux+Hv mx+ux+x+H H w
H ax+x+H ux+x+H H m
HH l E H OH H v_H+H H N
o u «H u «H H H H
E
m v m N H o HH

AE no .0 .HH .ouvm .H mHQMB

92

 

 

 

 

 

 

93

Avx+mx+ux+x+HvAux+x+HVAux+Hvux Avx+mx+ux+x+HVAux+Hv m
Avx+mx+mx+x+HVAmx+Hv Aex+mx+ux+x+HVAnx+x+HVAnx+Hvux
«H I N I E u eH Aux+x+HVAux+Hv Amx+mx+x+HVAux+x+Hvx Amx+x+HVAnx+Hv w
OHMH
N H HH NN+X+H NX+X+H m
mHmnz E
m m H o «H

AB no .nH .N .ova .v mHQmB

 

¢x+mx+ux+x+H wa+mx+ux+x+HVAmx+x+vax vx+mx+ux+x+H m

Avx+mx+ux+x+HVAnx+ux+x+Hme Avx+mx+ux+x+HvAmx+ax+x+vax

mx+mx+x+H Amx+mx+x+HVAax+x+Hvux

 

 

 

 

 

«H I H I E u oH Amx+mx+x+HvAnx+x+Hvax mx+ux+x+H v
oueH
ux+X+H Aux+x+HVAx+Hvx Nx+X+H m
HNHH
meLB x+H x+H N
E
v m m H o «H

AE “O .NH .H .ova .m mHQme

94

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Table 5. p(ro, 0, 0, r3; m)
r30 1 2 3
In
where
1 1 1 r1=r2=0
ro=m-r3
2 1 x2(1+x2) 1
3 1 x4(1+x+x2) x4(1+x+x3) 1
Table 6. p(ro, 1, 0, r3: m)
’53 o 1 2
m where
r1 = 1 r2 - 0
2 1+x x(1+x) r0 = m - 1 - r3
3 1+x+x2 x3(1+x)(1+x+x2) x2(1+x+x2)
Table 7. p(ro, 0, 1, r3; m)
‘3 o 1 2
m where
r1=0r2=1
2 x(1+x) 1+x r0 = m - 1 - r3
3 x2(1+x+x2) x3(1+x)(1+x+x2) 1+x+x2

 

 

fi—

 

95

Table 8. p(ro, 1, 1, r3: m)

 

 

 

r3
0 1 2
m where
r = r = 1
3 x(1+x)(1+x+x2) x(1+x)(1+x+x2) r: = m2_ 2 _ r3
4 x2(1+x+x2)(1+x+x2+x3) x2(1+x+x2)(1+x+x3+x3)
x4(1+x)(1+x+x2)(1+x+x2+x3)

 

 

 

Table 9. p(ro, 0, 2, r3; m)

r3

 

 

 

 

 

 

O 1 2
m ‘where
r1 = 0 r2 = 2
3 x2(1+x+x2) 1+x+x2 r = m - 2 - {1‘
4 x4(1+x+x2)(1+x2) (1+x2)(1+x+x2)
x4(1+x+x2)(1+x+x2+x3)
Table 10. p(ro, 2, 0, r3; m)
‘3 o 1 2
m where
r1=2 r2=0
3 1+x+x2 x2(1+x+x2) r0 = m - 2 - r1q
r

 

 

4 (1+x2)(1+x+x2) x4(1+x+x2)(1+x+x2+x3) x4(1+x2)(1+x+x2)

 

 

 

Section IV An Example: Extension to General Modulus

 

This section will provide an example of the extension to
the general modulus for the case of matrices of order 2
over Z/Z2, Z/Z3 and Z/Z6.

The canonical matrices of order 2 over z/z6 are
diSplayed by the following table.

Canonical Matrices of order 2 over z/zZ

 

 

 

 

1 1 1 o 1 o- o o o o
o o o o o 1 o o o 1
$3, 1 o] E 3] [1 o] [:1 o- [:4 o] [4 o]
\
N
E) o o o o o 3, o o o 3
3 1 1 1 1 1 4 1 4') 4 4 4 4
>
O
N 9 o o o o o o 3 o o o 3
g 1 2 1 5 1 2 1 2 4 2 4 2
H
0 o o o o o o o 3 o o o 3
m :' ’ " '—
° 1 o 1 3 1 o 1 o 4 o 4 0
U)
‘33 o 1 o 4 _o 4 o 1 o 4 o 1
H _ . _
4‘; o o 3 3 3 o 3 o o o o o
2
,4 o o o o o o o 3 o o o 3
m '— ‘ - -—
U . F"
S o o 3 3 3 o 3 o o o .o o
0
g o 1 o 4 _o 4 o 1 o 4 o 1
U

 

 

 

An example will now be provided illustrating the trans-
formation of a matrix A into its canonical matrix C by

multiplication on the left by a unimodular matrix Q. It is

96

97
hoped that this will illustrate the discussion in Chapter IV.
Let M2, M3 and M6 denote matrix rings of matrices

of order 2 over Z/Z2, Z/Z3 and Z/Z6, respectively.

Let 1 be the ring isomorphism

 

 

 

% : M2 x M3 > M6
Let
1 0 1 0 1 0
02 = A2 = C2 =
1 1 1 1 0 1
and
2 1 1 1 1 1
Q3 2 A3 = C3 = I
1 _2 2 0 0
then Q.A. E C. mod i for i = 2,3. Now
i i i _
r5 4
A(Qz: Qa) =
1 1
1 4
X(A2, A3) =
_5 5.1
and
1 4
x(cz, ca) =
0 3

The theory requires that
X(QZI 03) A(Azl A3)

x(QzAzt QaAa)

A(Czl C3)

98

and, clearly, this is the case since

mod 6