INTEGRAL M AT RICES MORRIS NEWMAN U. S. Department of Commerce National Bureau of Standards Washington, D. C. ACADEMIC PRESS NewYorkand London 1972 COPYRIGHT 0 1972, BY ACADEMPIRCE SS, INC. ALL RIGHTS RESERVED NO PART OF THIS BOOK MAY BE REPRODUCED IN ANY FORM, BY PHOTOSTAT, MICROFILM, RETRIEVAL SYSTEM, OR ANY OTHER MEANS, WITHOUT WRITTEN PERMISSION FROM THB PUBLISHERS. ACADEMIC PRESS, INC. 111 Fifth Avenue, New York. New York 10003 United Kingdom Edition published by ACADEMIC PRESS, INC. (LONDON)L TD. 24/28 Oval Road, London NW1 LIBRAROYF CONQRESS CATALOO CARDN UMBER: 72-182628 AMS (MOS) 1970 Subject CIassifications: 15A21, 15A36,20H05, locos PRINTED IN THE UNITED STATES OF AMERICA Prefaoe Integral matrices, or matrices over rings, is a huge subject which extends into many different areas of mathematics. For example, the entire theory of finite groups could be placed in this category. It goes without saying then that the selection of material for a book with such a title must necessarily be limited, and a matter of personal preference. Since it is the matrix theory with its many applications and not abstract ring theory which is the primary concern of this book, the discussion for the most part has been limited to matrices over principal ideal rings. Chapter I provides the necessary background material for this subject. Chapters 11, 111, IV, and V are concerned with the various kinds of equivalence relationships that may be defined for matrices. Among other things, the classical theory of matrices over a field is developed in these chapters. Chapter VI is a self-contained presenta- tion of the Minkowski geometry of numbers. Its principal purpose is to make available the powerful methods of the subject to the theory of quadratic forms. Chapter VII presents the theory of matrix groups over principal ideal rings, with special attention to the congruence groups, which have assumed new importance because of the recent work of J. L. Mennicke, H. Bass, M. Lazard, and J.-P. Serre. Chapter xiii xiv PREFACE VIII discusses the classical modular group and certain generalizations, such as the free product of two cyclic groups. Chapter IX presents the elements of the theory of group representations, with applications to finite integral matrix groups. Chapter X is devoted to the study of the group matrix of a cyclic group, and Chapter XI to the theory of quadratic forms in n dimensions. Since matrix theory is the basic discipline of this book, a knowl- edge of the elementary properties of vector spaces over fields and matrices whose elements lie in a field is assumed. The reader must have no difficultyi n handling partitioned matrices, and must be familiar with the body of formal theorems relating to products of partitioned matrices, determinants of partitioned matrices, etc. Furthermore, ele- mentary facts about rank, systems of linear equations, eigenvalues and eigenvectors, adjoints, characteristic and minimal polynomials, Kronecker products, etc. are used freely. These are not proved here, but may be found in any of the classical texts on matrix theory, for example, MacDuffee [28] or Marcus and Minc [31]. An understanding of elementary group theory is also required, and the reader should be familiar with this subject. Good general references are Hall [13] or Zassenhaus [72]. At one point, however, a difficult theorem from group theory must be used. This occurs in Chapter VIII, where the Kurosh subgroup theorem forms the basis for the discussion of the classical modular group. Good expositions of this theorem may be found in Hall [I31 or Kurosh [23]. The alternative was to develop the subject from the geometric viewpoint; but this leads to difficulties of another type. There is no easy alternative. Free use of the concepts and results of elementary number theory is made everywhere, and the reader must be thoroughly familiar with this subject. Good elementary texts are Hardy and Wright [15] or Landau [24]. In addition the classical theory of algebraic numbers is used from time to time, and the reader should also be familiar with the rudiments of this subject. An elegant presentation may be found in Hecke’s book [16]. For simple expositions see Newman [52] or Pollard [59]. A one- or two-semester graduate course could be fashioned from this book very easily. The first five chapters would form the core of the course and could be covered in a semester. The next semester could Preface xv be devoted to special topics selected from the remaining chapters at the discretion of the instructor. Enough open problems and suggestions for research are mentioned to provide direction for further reading or for individual research. Aukno wlwigments The orgin of this book was a series of lectures delivered a number of years ago at the University of British Columbia, at the invitation of Marvin Marcus. Notes were taken then which served as a skeletal outline for the final work. Much of the author’s personal research was done jointly with Olga Taussky-Todd, and a good part of the book is devoted to an exposition of this joint work and to work done solely by her. Others to whom I am grateful for work done jointly, or for their own stimulating research, are M. Hall, M. I. Knopp, J. Lehner, I. Reiner, H. Ryser, and J. R. Smart. Finally, my deepest thanks go to Mrs. Doris Burrell for her painstaking efforts in typing the manuscript. xvii Chapter I Background Maferlal on Rlngs Although classical matrix theory is concerned with matrices over the ring of integers Z or over a field, there are definite advantages to be gained by adopting a more general approach and studying matrices over any principal ideal ring. The properties of principal ideal rings do not differ markedly from the properties of Z, and we will develop these in what follows. 1. Principal ideal rings Aprincipal ideal ring R is a commutative ring with no zero divisors and a unit element 1 such that every ideal is principal; that is, such that every ideal consists of the totality of multiples of a fixed element. It is not actually necessary to assume that R contains a unit element, since this is derivable from the other hypotheses. Examples of principal ideal rings are: (1) The ring of integers 2. (2) Any field F. 1 2 I BACKGROUND MATERIAL ON RINGS (3) The ring of polynomials F[x] in a single variable x, with coef- ficients from a field F. In what follows R will always denote a principal ideal ring, and F a field. 2. Units Let S be any commutative ring with a unit element 1. If a is any element of S such that a/3 = 1 for some other element /3 of S, then a is said to be a unit of S. The totality of units of S forms a multiplicative group, which we denote by S‘. In 2, for example, the units are 1, - 1 and, in any field F, the units are the nonzero elements. In F[x],t he units are the nonzero elements of F. An element a of S is said to be an associate of an element /3 of S, if a = BE, where e belongs to S’.I t is readily verified that this is an equivalence relationship over S, so that S decomposes into equivalence classes with respect to this relationship. The class containing 0 (the zero of S) consists of 0 alone, and the class containing 1 consists of S’. A set of elements of S, one from each equivalence class, is said to be a complete set of non associates. This will always be chosen so that 1 is the representative of its class. We now return to R. 3. Divisibility If a, /3 are any elements of R and /3 f 0, we say that /3 divides a (written 81a) if a = By, for some element y of R. We readily verify that B I a if and only if (B) 3 (a), where (y) is the principal ideal con- sisting of the totality of multiples of y, for any element y of R. The units are trivial divisors of any element of R. Also we note that if a, /3 are nonzero elements of R, then (a) = (8) if and only if a and j? are associates. Let a, /3 be any elements of R which are not both 0. A greatest common divisor of a and /3 is an element S of R such that S 1 a, S 18; and if y is any element of R which divides both a and 8, then y IS. It is immediate that any pair of greatest common divisors of a and B 4. Congruence and Norms 3 are associates. The fact that R is a principal ideal ring guarantees the existence of at least one greatest common divisor of a and j3. We let + (a, j3) denote the ideal consisting of the totality of elements pa vj3, where p, v run over R independently. We have Theorem 1.1. Let a, j3 be any elements of R which are not both 0. Let (a, b) = (a), say. Then 6 is a greatest common divisor of a and 8. Proof. Certainly, 6 f 0. Since a and j3 each belong to (S),+ 6 1v sa., and 6 I /3. Furthermore, elements p, v of R exist such that 6 = pa Hence if y is any divisor of a and 8, then y 16. Thus 6 is a greatest common divisor of a and j3 and the proof is complete. The preceding discussion may be generalized in obvious fashion. If al,a ,, . . . , a, are elements of R which are not all 0, the ideal (al, a,, . . . , a,) consisting of the totality of elements plal + p2a, + -. + &"a,, where p,,p 2,. . . , p,, run over R independently, is principal and equal to (S), say; and 6 is a greatest common divisor of a,, a,, . . . , a,. We write (a,, a,, . . . , a,) = 6 The conflict of notation will cause no confusion. It will be clear from the context whether we are referring to an ideal or to a ring element. Notice also that 6 may be replaced by any of its associates. If 6 is a unit we say that a,, a,, . . . , a, are relatively prime and write (al,a ,,. . . , a,) = 1 If we restrict 6 to lie in some complete set of nonassociates, then 6 is uniquely defined. We shall do this in what follows. 4. Congruence and norms Let p be any nonzero element of R. We say that a is congruent to modulo p (written a = j3 mod p) if p divides a - 8; or what is the same thing, if a - j3 belongs to (p). Once again, this is an equivalence relationship over R. A set of elements of R, one from each equivalence class, is said to be a complete set of residues modulo p. In order to complete the definition, a complete set of residues modulo 0 will be taken to be the whole ring R, and a = B mod 0 to mean that a = 8. 4 I BACKGROUND MATERIAL ON RINGS The number of equivalence classes (which may be infinite) will be denoted by N(p) (the norm of p), and is just the order of the quotient ring R/(p).F or example, if R = 2, then N(p) = I p 1 , and if R is a field, then N(p) = 1. The following result will be of later use: Theorem 1.2. Suppose that p, v are nonzero elements of R such that N(p),N (v) are finite. Then N(pv) is also finite, and N(pv) = N(p)N(v). Proof. Let p,, 1 I i I m = N(p), be a complete set of residues modulo p, and v,, 1 < j 5 n = N(v), a complete set of residues modulo v. We will show that the mn elements of R + pi, = p, pv,, 1 Ii I m, 1 I j I n is a complete set of residues modulo pv. Suppose that pf, = pk,m od pv, where 1 Ii, k < m, I j, I < n, Then certainly p,, = pk,modp, so that p, = p,modp. Hence i = k, and so pv, = pvl mod pv, so that v, = v, mod v. Hence j = I, and no two of the elements pu are congruent modulo pv. Now let a be any element of R. The+n for some i such that 1 i 5 m, a G p, mod p, so that a = p( pp for some element /I of R. Also for some j such that 1 _< j < n, p = v, mod v. It follows that a G p, + pv, mod pv. This com- pletes the proof. 5. The ascending chain condition Perhaps the most important single fact about any principal ideal ring is that it must satisfy the ascending chain condition: that is, if A, c A, c a * * is any infinite sequence of ideals, then for some positive integer k, - A, = A,,, = * * We state this as a theorem. Theorem 1.3. Any principal ideal ring R satisfies the ascending chain condition. Proof. Let A, c A, c *..