18 312 Algebraic Combinatorics Lionel Levine Lecture 22 Lecture date May 3 2011 Notes by Lou Odette This lecture Smith normal form of an integer matrix linear algebra over Z 1 Review of Abelian Groups Z modules Recall that given a ring R with 1 an R module is an Abelian group written additively with a map R M M scalar multiplication with R the scalars and M the vectors satisfying r m1 m2 rm1 rm2 r sm rs m 1m m which is analogous to a vector space over R with the difference that we may lack multiplicative inverses in R by contrast with a vector space over a field If G is an group we have a map Z G G n g 7 g g z if n 0 n times 0 g 7 0 n g 7 g g if n 0 z n times so we admit scalar multiplication by integers but not anything else In particular any abelian group has the structure of a Z module Now say G is an Abelian group finitely generated from generators g1 gn Then there is a surjective group homomorphism f Zn G taking basis elements to the generators f ei gi X X f ci ei ci gi i n i n 22 1 Let K be a kernel of f the subgroup of Zn s t X X ci gi 0 in G ci gi K ker f i n i n Definition 1 A group G is torsion free if g G g 6 0 and n Z n 6 0 we have ng 6 0 Example 2 Z and Zn are torsion free but Z nZ is not torsion free since ng 0 for all g Z nZ Note that if G is torsion free then it is infinite or zero since with g G and g 6 0 then g 2g 3g are distinct since otherwise ig jg i j g 0 By the Fundamental Theorem of Finitely Generated Abelian Groups FTFGAG any finitely generated abelian group G has the form G Zr Z n1 Z Z nk Z 1 where r 0 is unique but the n1 nk 1 are not necessarily unique Example 3 Z6 Z4 Z2 Z3 Z4 Z2 Z12 since Zm Zn Znm for m n by the Chinese remainder theorem There are two ways to get uniqueness 1 require that all the ni are prime powers 2 or require n1 n2 n3 nk We consider the second of these today Lemma 4 Any subgroup K Zn satisfies K Zr for some r n Note that unlike subspaces of a vector space is it possible to have r n and K 6 Zn For example 2Zn Zn while is it still the case that 2Zn Zn In this sense abelian groups are more interesting than vector spaces 22 2 Now since K Zn K Zr for some r n pick a basis x1 xr K so that X ci xi ci Z K i r and define L Zr Zn ei 7 xi so that G Zn K Zn Image L Zn LZr P We can think of L as an r n matrix and each xi j n ai j ei for i r where the ai j are the matrix entries of L We can extend L to Zn i e L Zn Zn by setting ei 7 0 for i r add zero columns So far we have seen how defining an abelian group G via generators and relations leads to an n n matrix L such that G Zn LZn where n is the number of generators The question that Smith normal form address is given a group in this form Zn LZn how do we express it in the factored form 1 Example 5 Let L 2 1 1 2 G hg1 g2 i and 2 G Z 2 1 1 2 22 3 2g1 g2 0 g1 2g2 0 Z2 3 a 0 b 1 2 a 1 b 1 1 0 a b 0 1 1 2 3 4 5 a 1 b 0 2 Figure 1 This figure illustrates G Z2 LZ2 where LZ2 consists of the points 2a b 2b a for a b Z as marked by the symbol on the grid The remaining symbols represent elements in the respective equivalence classes The points enclosed by the box represent the members of all equivalence classes illustrating that G 5 So G Z 5Z Now consider the kinds of changes to L that don t change the isomorphism type of G One approach is to change the generators Example 6 Write the group G of example 5 using different generators G hh1 h2 i h1 g1 h2 3g1 g2 In general if H GLn Z where GLn Z is the set of n n matrices U with det U 1 so the inverse also is an integer matrix then since U Zn Zn G Zn LZn U Zn LZn Zn U 1 LZn In addition if V GLn Z since V Zn Zn Zn U 1 LZn Zn U 1 L V Zn Zn U 1 LV Zn Example 7 Write the group G of example 5 with different relations 2g1 g2 0 2g1 g2 0 g1 2g2 0 3g1 g2 0 22 4 Definition 8 An n n integer matrix S is in Smith Normal Form SNF if S is a diagonal matrix and uniqueness condition 2 is satisfied with the diagonal elements S i i di i e d1 d2 d3 dn di 0 i n Note that some di may be zero since any integer divides zero Theorem 9 An integer matrix L ai j i j n can be written as L U SV where S is in SNF and U V GLn Z invertible over the integers Moreover the non zero di on the diagonal of S are unique note gcd is non negative by definition d1 gcd ai j d1 d2 gcd ai j ak l ai l aj k i e the 2 2 determinants d1 dk gcd all k k minors of L d1 dn det L with G det L In terms of the group G if L has SNF S then G Zn LZn Zn SZn hg1 gn i di gi 0 i n hg1 i d1 g1 hgn i dn gn Z d1 Z Z dn Z in particular the rank of G is i di 0 if G is finite all di 0 then G d1 dn det L Note row and column operations don t change the gcd result since if n1 nk 6 0 noting that if m n 1 then c c0 Z s t cm c0 n 1 X gcd n1 nk min d 0 d ci ni for some c1 ck Z i n so L U SV 22 5 Example 10 Consider 1 3 1 L 3 1 3 Z3 LZ3 Z4 Z8 1 3 5 since d1 gcd ai j 1 d1 d2 gcd 8 0 8 0 4 12 8 12 4 4 d1 d2 d3 det L 32 2 …