# Relationship between a basis for a free abelian group of rank $n$ and a basis for a subgroup of the same rank

I was looking for an elementary proof of the following assertion:

Let $n\in \mathbb{N}$ and let $G$ be a free abelian group of finite rank $n$. Let $H\subset G$ be a subgroup of rank $n$. Then $G$ has a generating set $\left \{\beta_1,\cdots ,\beta_n\right \}$ such that (for appropriate integers $d_i$) $\left \{d_1\beta_1,\cdots ,d_n\beta_n\right \}$ is a generating set of $H$.

I found a proof which does not convince me. I suspect there must be some errata which I cannot find, or maybe I am just not understanding the proof. It goes as follows:

We can prove this by induction on $n$. This is rather clear for $n=1$, so assume the result for $n-1$.

For any basis $\alpha_1,\cdots ,\alpha_n$ of $G$ look at all elements $h\in H$ which, when expressed in this basis, have positive coefficient of $\alpha_1$. Of all possible bases and elements of $H$ choose these which make this coefficient the least possible, say equal to $d_1$. We claim that every element of $H$ has every coefficient with respect to this basis divisible by $d_1$. We ﬁrst prove this for $h$: if $h$ had a coeﬃcient $a$ of $\alpha_i$ not divisible by $d_i$, then we could write $a = qd_i + r$, $0 < r < d_i$. But then if we replaced the basis $\alpha_1,\cdots ,\alpha_n$ with $\alpha_1+q\alpha_i,\cdots ,\alpha_n$ (easily seen to be another basis), then we easily see the coefficient of $\alpha_i$ would be $r$, so rearranging the basis would contradict the choice of $d_1$. Hence $\beta_1 = \frac{\alpha_1}{d_1}\in G$.

Similarly, we establish that for every $h_0 \in H$, the coeﬃcient of $\alpha_1$ is divisible by $d_1$, say it’s $qd_1$. Then $h_0 − qh$ is contained in the group $G_1$ generated by $\alpha_2,\cdots ,\alpha_n$. Let $H_1 = H\cap G_1$. Also, let $H_0$ be the group generated by $\alpha_1$. It follows that $H = H_0\oplus H_1$. By induction, there is a basis $\beta_2,...,\beta_n$ for $G_1$ and integers $d_2,\cdots ,d_n$ such that $d_2\beta_2,\cdots ,d_n\beta_n$ are a basis for $H_1$. Then $\beta_1,\cdots ,\beta_n$ and $d_1,\cdots ,d_n$ work for $G$ and $H$.

1) I think we did not prove that "every element of $H$ has every coefficient with respect to this basis divisible by $d_1$", but "$h$ has every coefficient with respect to this basis divisible by $d_1$ and the other elements of $H$ have their first coefficient divisible by $d_1$". Am I right?

2) What is the meaning of $\beta_1=\frac{\alpha_1}{d_1}$? We are in an abelian group, we cannot divide by natural numbers, unless the element was originally multiplied by $d_1$, right?

3) Why is $H=H_0\oplus H_1$? We had defined $H_0$ to be the group generated by $\alpha_1$. Why it is even a subgroup of $H$? This makes no sense to me.

As I said, maybe I am just not understanding the proof, but I think there must be some errata which I do not know how to fix. I would like to have the complete corrected proof. Any help would be appreciated.

• You might find a proof of this in the context of free $\Bb{Z}$-modules. – G Tony Jacobs Nov 11 '17 at 16:43
• Thank you, but I am not looking for another proof. I am trying to understand this one. – solomeo paredes Nov 11 '17 at 16:47
• Yes, that’s why I posted this as a comment, and not as an answer. Even if you don’t find it helpful, another reader might. :) – G Tony Jacobs Nov 11 '17 at 16:48
• I'm looking over this more carefully, and I think you're right that there are some problems. Where did you find this proof? – G Tony Jacobs Nov 12 '17 at 16:09
• Thank you very much, I was worried because noone answered. :( This is exercise 27(b) of the second chapter of Dr. Daniel Marcus' book on Number Fields, and I found the solution of all exercises of the first two chapters here: wojowu.files.wordpress.com/2016/10/number-fields-solutions.pdf – solomeo paredes Nov 12 '17 at 18:41

1) What we have shown is that, for every element of $H$, the coefficient of $\alpha_1$ is a multiple of $d_1$. We don't know anything about the other coefficients of $h$, as is clear from an example:

Let $G$ be $\Bbb{Z}\times\Bbb{Z}$, let $H$ be generated by $(3,0)$ and $(0,4)$, let $\alpha_1=(1,0),\alpha_2=(0,1)$, and $h=(3,4)=3\alpha_1+4\alpha_2$. Clearly, we have $d_1=3$, and the second coefficient of $h$ has nothing to do with that.

2) I think you're right, that $\frac{\alpha_1}{d_1}$ is incoherent. We should be setting $\beta_1=\alpha_1$.

3) At this point, it looks like we want to let $H_0$ be generated by $d_1\alpha_1$, not by $\alpha_1$. I think the author got the first basis element for $H$ and the first basis element for $G$ confused, which would also explain the strange quotient in your second question.

• For the first one: remember that we had chosen both $h$ and the basis so that the first coefficient is minimized (the basis, in this sense, is an ORDERED basis). Therefore the basis $\left \{\alpha_1,\alpha_2\right \}$ is not a valid one, instead we should choose the basis $\left \{\alpha_2,\alpha_1\right \}$. In this sense, I suspect that the assertion that ALL coefficients are divisible by $d_1$ is a true assertion (in your example, $d_1=1$). Am I right? – solomeo paredes Nov 12 '17 at 19:05
• Ah, good point. Let me alter my example. – G Tony Jacobs Nov 12 '17 at 19:06
• Hrmm. No, I've got to think about that part more. Choosing over all possible bases of $H$ is more complicated. – G Tony Jacobs Nov 12 '17 at 19:08
• That doesn't even make sense. If we're writing elements of $H$ in terms of the basis of $G$, why does it matter which basis of $H$ we have in mind? Either way, see my edit. – G Tony Jacobs Nov 12 '17 at 19:13
• It is still a wrong example. $H$ is fixed to be $<(3,0),(0,4)>$. Once $H$ is fixed, we have to choose $h$ and the basis of $G$ properly. For example, your basis $\left \{(1,0),(0,1)\right \}$ is not a good one, because $\left \{(-1,0),(1,1)\right \}$ is a better one for the $h$ you chose (we again obtain $d_1=1$). – solomeo paredes Nov 12 '17 at 19:22