From: mareg@primrose.csv.warwick.ac.uk () Subject: Re: Formula for an index of a subgroup Date: 21 Jan 2001 19:09:11 GMT Newsgroups: sci.math Summary: Computing index of a subgroup of a free abelian group In article <94ei8u$a4u$1@nnrp1.deja.com>, hale@mailhost.tcs.tulane.edu writes: >In article <94bll1$6pt$1@nnrp1.deja.com>, > Robin Chapman wrote: >> In article <94aueb$lvj$1@nnrp1.deja.com>, >> hale@mailhost.tcs.tulane.edu wrote: >> > In article <94a0q5$3i4$1@wisteria.csv.warwick.ac.uk>, >> > mareg@primrose.csv.warwick.ac.uk () wrote: >> > > In article <9493qq$2ag$1@nnrp1.deja.com>, >> > > ahmedfares@my-deja.com writes: >> > > >Let H be a subgroup of index d of Z^n. >> > > >Then the rank of H is also n, H is generated by n vectors >> > > >v1,v2,v3,...,vn. >> > > >If A is the matrix of rows v1,v2,v3,...,vn how it can be proved that >> > > >|det(A)| = d ? >> > > >> > > The fundamental theorem of finitely generated abelian groups says that >> > > you can diagonalize H by multiplying on the left and right by elementary >> > > matrices. The entries of the resulting diagonal matrix are the orders of >> > > the cyclic direct factors of Z^n/H, and so their product is |Z^n/H| = d. >> > > But elementary matrices have determinant one so result follows. >> > >> > I am not sure that this is completely correct. >> >> It is. The fundamental theorem states that there is a basis >> e_1, ..., e_n of Z^n (not necessarily the standard one) >> such that a_1 e_1, a_2 e_2, ..., a_n e_n span H for some >> positive integers n. The index is clearly a_1 a_2... a_n. >> As diag(a_1,...,a_n) is obtainable from A by pre- and post-multiplying >> by unimodular matrices, the result follows. > >Let me give a particular case in order to show where my doubts are. [example omitted] I could not really understand the source of your doubts from the example. The matrices involved when we apply the product of determinant rule det(ab) = det(a)*det(b) are simply square matrices with integer entries, so how could there possibly be a problem with that? Let me recap the whole thing, and then you can say which step you are not happy with. We have a free abelian group Z^n. We have a subgroup H , which is generated by m vectors v1, v2, .., vm. (We don't need to assume m=n yet.) We can now define an mxn matrix A of which the rows are the vectors vi. Now if we multiply A on the left by a unimodular integral matrix, then we are adding an integral multiple of one row of A to another, interchanging two rows, or multiplying a row by -1. It is clear that the rows of the resulting matrix still span the same subgroup H. If we multiply A on the right by a unimodular integral matrix, then we are performing the corresponding operations on the columns of A. The effect of this is to change the basis of Z^n that we are using. But the rows of the resulting matrix still span H, with respect to the new basis of Z^n. It is a theorem that we can reduce any integral matrix to a diagonal matrix with nonzero entries, in which each entry on the diagonal divides the next one down, by performing elementary row and column operations of this kind. The resulting diagonal matrix is said to be in Smith Normal Form. (Reducing a matrix in this way is a much-studied computer algorithm - it gives rise to practical difficulties because the integral entries can grow very rapidly in size if you are not careful, but that is not relevant here!) I have not assumed that m=n. But if m=n, then of course all of the entries are square, and the determinant of the resulting matrix in Smith Normal form is the same (or minus) the determinant of the original A. This is because unimodular matrices have determinant plus or minus 1. Derek Holt. ============================================================================== From: mareg@mimosa.csv.warwick.ac.uk () Subject: Re: Formula for an index of a subgroup Date: 23 Jan 2001 09:03:24 GMT Newsgroups: sci.math In article <94hvtd$14v$1@nnrp1.deja.com>, hale@mailhost.tcs.tulane.edu writes: >In article <94hlcg$hcp$1@wisteria.csv.warwick.ac.uk>, > mareg@mimosa.csv.warwick.ac.uk () wrote: >> I am not thinking of A as representing a map from G to H. >> I am just thinking >> of it as a matrix whose rows generate the subgroup H. > >As I mentioned before, I don't like to think of A as >a matrix with its rows being the generators of H. > >However, I felt sure that your method and my method would >be equivalent, although the terminology would be different. > >I also objected to quoting the proof of the fundamental >theorem to show that you could transform the matrix into >its standard form by using unimodular integral maps. Yes, I see that the two methods are equivalent. But I don't quote the proof of the fundamental theorem. On the contrary, I prove the result about transforming matrices directly, and use that to deduce the fundamental theorem. As a computational mathematician, I prefer that method of proof, because it provides a potentially efficient algorithm for finding the invariant factors of an abelian group. Proving the result using matrices is not hard. Swap rows and columns to bring the smallest nonzero entry d to the top left and make sure it is positive. If this entry does not divide all other entries in the first row and column, then by using elementary row/column operations and the euclidean algorithm, we can get a smaller positive entry than d. So we can assume d does divide all of first row and column, and then reduce the remainder of the first row and column to 0. Now, by induction on the degree of the amtirx, we can diagonalize the matrix, and then with a couple more operations we can ensure that each entry divides the next one down. The decomposition theorem for finitely generated modules over a (commutative) principal ideal domain can be proved in a similar way, but there you need an additional trick involving 2X2 matrices, because you do not necessarily have the euclidean algorithm available. Derek Holt.