The Student Room Group

Index of a H in G, using matrices Z^n

I'm trying to answer the below question, for the proof I have started just by saying that G is generated by the standard basis e1,...en. Where ei is a column vector with 1 in the ith place and 0 elsewhere. Then I have said that H is generated by either equal to or less than n elements: e1,..,ek. I know that if G is finite(which assume it is) then index of H in G |G:h:| = |G|/|H|.
So this means it's n/r, however I can't prove that this is the determinant of the matrix. Maybe the method I am using isn't the best as I can't see a clear link.

Also in the application in the second part, i find det A = 4. How is this possible if Z3 has order 3? As i thought that the index of H in G must be smaller than G itself.

Reply 1
Zn\mathbb{Z}^n is infinite, it is ZZ...Z\mathbb{Z} \oplus \mathbb{Z} \oplus ... \oplus \mathbb{Z}.

You really need to remember that Zn\mathbb{Z}^n is different from Z/nZ \mathbb{Z}/n\mathbb{Z}.

My hint would be to consider the reduce echelon form of the matrix AA. I believe if AA is invertible in Q\mathbb{Q}, then AA is the identity matrix when it is column reduced? det(A)=n|\det(A)| = n where nn is a positive integer, and neine_i spans the group HH. So essentially, H=nZnH = n\mathbb{Z}^n, so Zn/H=n|\mathbb{Z}^n/H| = n .
(edited 8 years ago)
Ah okay, that's where I went wrong.

I understand that A is the identity matrix when in its reduced echelon form, is this just to say that det A is not equal to 0?

So what I am thinking is that we just let det a = n. I can't think of it algebraically but geometrically we say that spans since it is the 'area' of . Sorry I'm unsure how to explain this clearer..

Then the rest I am fine with, thanks a lot!
Original post by VincentCheung
Ah okay, that's where I went wrong.

I understand that A is the identity matrix when in its reduced echelon form, is this just to say that det A is not equal to 0?

So what I am thinking is that we just let det a = n. I can't think of it algebraically but geometrically we say that spans since it is the 'area' of . Sorry I'm unsure how to explain this clearer..

Then the rest I am fine with, thanks a lot!
You may be fine with it, but I am not at all convinced by your argument. You can't possibly "just let det A = n". And det A is not 0, but what is your logic for writing this and then saying "let det A = n" two lines later? :eek:
Reply 4
Original post by VincentCheung
Ah okay, that's where I went wrong.

I understand that A is the identity matrix when in its reduced echelon form, is this just to say that det A is not equal to 0?

So what I am thinking is that we just let det a = n. I can't think of it algebraically but geometrically we say that spans since it is the 'area' of . Sorry I'm unsure how to explain this clearer..

Then the rest I am fine with, thanks a lot!

I'm not exactly sure whether what I've written works, especially the Zn/H=n|\mathbb{Z}^n / H| = n part. I'm pretty sure that's wrong. But yes, if you get it into reduced echelon form AA', then A=nAA = nA' where AA' is the identity matrix. So detA=detnA=ndetA=n\det A = \det nA' = n\det A' = n.

By the way, if you do solve it do post the solution because I'm quite interested :tongue:
Okay thanks for the help, I will try!
Original post by DFranklin
You may be fine with it, but I am not at all convinced by your argument. You can't possibly "just let det A = n". And det A is not 0, but what is your logic for writing this and then saying "let det A = n" two lines later? :eek:


Sorry I meant |det(A)| is just a positive number, since being negative means that there are negative left cosets in the Zn and being 0 means there are no left cosets(clearly not true as H itself is a coset) so there must be a positive number of cosets of H in Zn. So with this we have at satisfied that there is a possibility for |detA| to be equal to |zn ​/H|. So that what i have to prove is just that the number of cosets of H is equal to this n that i have chosen
(edited 8 years ago)
Original post by VincentCheung
Sorry I meant |det(A)| is just a positive number, since being negative means that there are negative left cosets in the Zn and being 0 means there are no left cosets(clearly not true as H itself is a coset) so there must be a positive number of cosets of H in Zn. So with this we have at satisfied that there is a possibility for |detA| to be equal to |zn ​/H|. So that what i have to prove is just that the number of cosets of H is equal to this n that i have chosen
You can't choose n, so this makes no sense.

I dont want to me be mean, but reading your posts, I don't feel you have the slightest degree what's going on. They are riddled with misunderstandings, non-sequiters and faulty logic. I mean, starting from the top:

Of *course* |det A| is positive! *Anything* with modulus signs is going to be positive!
And of course det A is nonzero, because they've told you A is invertible.
But otherwise, could det A be negative? Absolutely.
I have absolutely no idea what you mean by -ve coset but I'm pretty sure it makes no sense in the context of Z^n.
And globally, I see absolute no evidence that you've actually used the fact that we're talking about det A. If the question asked exactly thesame thing but with trace A, I see no evidence you wouldnt use exactly the same argument.

Sorry, I know the rant above isn't helpful and I'm sure you're doing your best. But this is so far from a valid argu!Kent I don't even know where to start.
Original post by DFranklin
You can't choose n, so this makes no sense.

I dont want to me be mean, but reading your posts, I don't feel you have the slightest degree what's going on. They are riddled with misunderstandings, non-sequiters and faulty logic. I mean, starting from the top:

Of *course* |det A| is positive! *Anything* with modulus signs is going to be positive!
And of course det A is nonzero, because they've told you A is invertible.
But otherwise, could det A be negative? Absolutely.
I have absolutely no idea what you mean by -ve coset but I'm pretty sure it makes no sense in the context of Z^n.
And globally, I see absolute no evidence that you've actually used the fact that we're talking about det A. If the question asked exactly thesame thing but with trace A, I see no evidence you wouldnt use exactly the same argument.

Sorry, I know the rant above isn't helpful and I'm sure you're doing your best. But this is so far from a valid argu!Kent I don't even know where to start.


Haha to be honest I'm not that clear on much with this question.

Starting over, from one of my classmates has said to use the approach that since A is invertible we can use unimodular operations to reduce it to diagonal smith normal form D. Then |det A| = |det D| as unimodular row operations do not change the size of the determinant. So |detD| is just the diagonal elements(d1,d2,...,dn) of D multiplied together..

Then to show that the subgroup with generators d1x1,d2x2,...,dnxn in a free basis xi has index d1.d2...dn or infinite.

Although at this moment i'm unsure how to link them..
Original post by VincentCheung
Haha to be honest I'm not that clear on much with this question.
Repped for taking my rant in good spirt!

Starting over, from one of my classmates has said to use the approach that since A is invertible we can use unimodular operations to reduce it to diagonal smith normal form D. Then |det A| = |det D| as unimodular row operations do not change the size of the determinant. So |detD| is just the diagonal elements(d1,d2,...,dn) of D multiplied together..
This is fine; however it's not so clear to me that this is enough to say "it's enough to solve the original problem it for diagonal matrices D", (However, it should be said I've only ever skim read about Smith Normal Form, it wasn't covered in my lin alg. courses).

Then to show that the subgroup with generators d1x1,d2x2,...,dnxn in a free basis xi has index d1.d2...dn or infinite.
This should be straightforward - as I say, to my mind the issue is whether this is sufficient to answer the original question.

Although at this moment i'm unsure how to link them..
Link what, exactly?
So my friend gave me an explanation:

"You can try a concrete example, like n=2, standard basis and d_1=2, d_2=4. The so the generators for H are (2,0) and (0,4).The first generator gives you elements of the form (2n,0), the second gives you elements (0,4m) where n and m are integers. So now think of possible cosets (2n,4m)+(x,y) for integers x and y.Remember 2Z has two cosets in Z, and 4Z has 4 cosets, so you can convince yourself that H in this case has 8 cosets."


So using this and the same line of explanation..

A reduced into smith normal form is a diagonal matrix D, (d1,d2...,dn) on the diagonals (the elementary unimodular row/column operations) ensures that |detA| = |detD| which is just the product of the diagonal entries of D.

Now I look at each generator individual and find there is exactly di cosets for that generator. Then for the whole of H then this is just detA, I think this is enough?
Original post by VincentCheung
So my friend gave me an explanation:

"You can try a concrete example, like n=2, standard basis and d_1=2, d_2=4. The so the generators for H are (2,0) and (0,4).The first generator gives you elements of the form (2n,0), the second gives you elements (0,4m) where n and m are integers. So now think of possible cosets (2n,4m)+(x,y) for integers x and y.Remember 2Z has two cosets in Z, and 4Z has 4 cosets, so you can convince yourself that H in this case has 8 cosets."
Yes. (This is essentially trivial).

So using this and the same line of explanation..

A reduced into smith normal form is a diagonal matrix D, (d1,d2...,dn) on the diagonals (the elementary unimodular row/column operations) ensures that |detA| = |detD| which is just the product of the diagonal entries of D.
Yes, it ensures that the determinants match. However it is far less clear to me that it shows the subgroup generated by these diagonal entries has the same index as the subgroup generated by the columns of the original matrix. It's the kind of thing that feels like it ought to be true, but I'm not seeing any actual argument or justification here, you're just stating it as a fact. (One particular concern is that any argument based on "matrices with determinant +/-1 don't change the index of the subgroup" feels awfully close to circular logic to me).

Now I look at each generator individual and find there is exactly di cosets for that generator. Then for the whole of H then this is just detA, I think this is enough?
Again, things like "I look at each generator individual and find ... for that generator" doesn't really make sense to me. I can see what you're trying to do, but you are either missing out a heck of a lot of the argument, or you what you are saying is just plain wrong.

I don't know what kind of detail is expected, and it is possible that what you've written now would get the marks. However, given your previous postings, I am very dubious that you could actually fill in the detail. (It's perhaps worth pointing out that it's likely your examiners will have similar doubts).
Original post by DFranklin
However it is far less clear to me that it shows the subgroup generated by these diagonal entries has the same index as the subgroup generated by the columns of the original matrix.


Since we use elementary row operations it is the same as multiplying A by unimodular matrices. This is in smith normal form by invertibility of A. So H is also represented by the matrix D.



Again, things like "I look at each generator individual and find ... for that generator" doesn't really make sense to me. I can see what you're trying to do, but you are either missing out a heck of a lot of the argument, or you what you are saying is just plain wrong.



Erm to expand the argument I guess I would use induction. So for n = 1, we just have Z/d1Z, which has d1 cosets: H, H+1,... H+d1-1.

Then for the induction hypothesis n=k-1 we assume it has d1.d2...dk-1 cosets. So for n=k we have one more generator that last, the previous k-1 we use the induction hypothesis. The new one we then inspect the same as we did for the case of n=1, to find dk cosets in the kth generator. So we either have (d1.d2..dk-1) + dk or (d1.d2..dk-1). dk. We can just formulate a counterexample to show that the first case cannot be true so it must be that the second case is true and we're finished.


I'm not sure if induction is needed although i think it provides more than enough
Original post by VincentCheung
Since we use elementary row operations it is the same as multiplying A by unimodular matrices. This is in smith normal form by invertibility of A. So H is also represented by the matrix D.
You're missing my point. I have no issues with the idea that H = QDP for suitable matrices P, Q. But the question doesn't say anything about representations, or indeed, very much about matrices at all. No, it talks about using the columns of a matrix as a generator for a subgroup of Z^n.

So, again. It is not at all obvious to me that you have shown that the subgroup generated by the columns of H and the subgroup generated by the columns of D must have the same index.

Erm to expand the argument I guess I would use induction. So for n = 1, we just have Z/d1Z, which has d1 cosets: H, H+1,... H+d1-1.

Then for the induction hypothesis n=k-1 we assume it has d1.d2...dk-1 cosets.
What is "it" here?

So for n=k we have one more generator that last, the previous k-1 we use the induction hypothesis. The new one we then inspect the same as we did for the case of n=1, to find dk cosets in the kth generator.
Generator of *what*?

So we either have (d1.d2..dk-1) + dk or (d1.d2..dk-1). dk.
To me, this reads as "I don't actually understand this well enough to say if I should be adding d_k or multiplying by d_k here", so...

We can just formulate a counterexample to show that the first case cannot be true so it must be that the second case is true and we're finished.

I'm not sure if induction is needed although i think it provides more than enough
I disagree. I'm completely unconvinced by this. (And unlike my main objection, this is the bit I think is trivial to prove, so it's not like I don't know how to prove it, I just don't think you've even got close).
Original post by DFranklin
You're missing my point. I have no issues with the idea that H = QDP for suitable matrices P, Q. But the question doesn't say anything about representations, or indeed, very much about matrices at all. No, it talks about using the columns of a matrix as a generator for a subgroup of Z^n.

So, again. It is not at all obvious to me that you have shown that the subgroup generated by the columns of H and the subgroup generated by the columns of D must have the same index.


Oh I understand, I see what you mean by it seems like it should. Sorry, I'm unsure how to prove this..


What is "it" here?

Generator of *what*?

To me, this reads as "I don't actually understand this well enough to say if I should be adding d_k or multiplying by d_k here", so...

I disagree. I'm completely unconvinced by this. (And unlike my main objection, this is the bit I think is trivial to prove, so it's not like I don't know how to prove it, I just don't think you've even got close).


Sorry, 'it' is the index of the subgroup H(of Zk-1) in the direct sum of Z, k - 1 times.

The generator of the last column of H, So for the kth column of H in Zn

The add or multiple dk was to list the possibilities that could have happened given that we already have (d1...d_k-1) cosets of H in the first Zk-1, I guess you could jump straight to the conclusion once you have found d_n cosets of Z/dn​Z
Original post by VincentCheung
Oh I understand, I see what you mean by it seems like it should. Sorry, I'm unsure how to prove this..
I agree it "seems" like it should be true, but then the entire result "seems" like it should be true as well. (Arguing purely geometrically, H maps the n-dimensional hypercube with 2^n vertices {(a1,a2,...,an)}:ai{0,1}}\{ (a_1, a_2, ..., a_n) \} : a_i \in \{0, 1\} \} to a n-dimensional parallelogram of volume |det H|. If you imagine tiling Z^n with such parallelograms, it's fairly easy to see that a large cube containing K points (of Z^n) will contain approximately K / |det H| points that are generated by H. Conversely, I think it's reasonably straightforward to show that if you take the intersection of a subgroup of Z^n of index N with a large cube, then approximately 1/N of the points in the cube will be members of the subgroup. Putting these together, the result follows).

So part of my problem is that the proof relies on certain things being true that I consider not much less obvous than the thing you're trying to prove in the first place.

Sorry, 'it' is the index of the subgroup H(of Zk-1) in the direct sum of Z, k - 1 times.

The generator of the last column of H, So for the kth column of H in Zn
OK, this is much better. But this explanation is necessary, and you didn't give it before.

The add or multiple dk was to list the possibilities that could have happened given that we already have (d1...d_k-1) cosets of H in the first Zk-1, I guess you could jump straight to the conclusion once you have found d_n cosets of Z/dn​Z
This however, still makes no sense to me. I can't see any way you could end up in a situation where adding d_k makes sense.
Original post by DFranklin
I agree it "seems" like it should be true, but then the entire result "seems" like it should be true as well. (Arguing purely geometrically, H maps the n-dimensional hypercube with 2^n vertices {(a1,a2,...,an)}:ai{0,1}}\{ (a_1, a_2, ..., a_n) \} : a_i \in \{0, 1\} \} to a n-dimensional parallelogram of volume |det H|. If you imagine tiling Z^n with such parallelograms, it's fairly easy to see that a large cube containing K points (of Z^n) will contain approximately K / |det H| points that are generated by H. Conversely, I think it's reasonably straightforward to show that if you take the intersection of a subgroup of Z^n of index N with a large cube, then approximately 1/N of the points in the cube will be members of the subgroup. Putting these together, the result follows).

So part of my problem is that the proof relies on certain things being true that I consider not much less obvous than the thing you're trying to prove in the first place.


Okay I see another way to approach the problem, thank you very much! I'm unsure if the proof that the columns of D still generate H is in the scope of the course however I will keep this in mind.


This however, still makes no sense to me. I can't see any way you could end up in a situation where adding d_k makes sense.


Exactly, so the only possibility is where only multiplying by d_k makes sense. Sorry I worded it badly... You can just ignore that I ever said that haha
(edited 8 years ago)

Quick Reply