# Algorithm for finding a basis of a subgroup of a finitely generated free abelian group

Let $G$ be a finitely generated free abelian group. Let $\omega_1,\cdots, \omega_n$ be its basis. Suppose we are given explicitly a finite sequence of elements $\alpha_1,\cdots, \alpha_m$ of $G$ in terms of this basis. Let $\alpha_i = \sum_j a_{ij} \omega_j, i = 1,\cdots,m$. Let $H$ be the subgroup of $G$ generated by $\alpha_1,\cdots, \alpha_m$. It is well-known that $H$ is a free abelian group of rank $\le n$.

My question Is there algorithm for finding a free basis of $H$ from the data $a_{ij}, 1 \le i \le m, 1\le j \le n$? If yes, what is it?

Remark My motivation for the above question is as follows. Let $K$ be an algebraic number field degree $n$. Let $\mathcal{O}_K$ be the ring of algebraic integers of $K$. Let $\omega_1,\cdots,\omega_n$ be its integral basis. Suppose we are given explicitly a finite sequence of elemements $\mu_1,\cdots, \mu_r$ of $\mathcal{O}_K$ in terms of this basis. Suppose not all of these elements are zero. Let $I$ be the ideal of $\mathcal{O}_K$ generated by $\mu_1,\cdots, \mu_r$. It is well-known and easy to see that $I$ is a free $\mathbb{Z}$-submodule of $\mathcal{O}_K$ of rank $n$. I would like to know how to find a free basis of $I$ as a $\mathbb{Z}$-module.

• This can be helpful mathoverflow.net/questions/101536/… – user52045 Nov 18 '13 at 22:51
• It's the Hermite Normal Form you need for this. That does exactly what you want. It finds a canonical free basis for the subgroup, so it can also be used for testing two such subgroups for equality. – Derek Holt Nov 19 '13 at 9:09

Let $x_1,\cdots, x_m$ be a sequence of elements of $G$. We denote by $[x_1,\cdots,x_m]$ the subgroup of $G$ generated by $x_1,\cdots, x_m$.
We use induction on the rank $n$ of $G$. Suppose $n = 1$. Then $\alpha_1 = a_{11}\omega_1,\cdots, \alpha_m = a_{m1}\omega_1$. We may suppose that not all of $\alpha_i$ are zero. Let $d =$ gcd$(a_{11},\cdots,a_{m1})$. There exist integers $c_1,\cdots,c_m$ such that $d = c_1a_{11} + \cdots + c_ma_{m1}$. Then $d\omega_1 = c_1\alpha_1 + \cdots + c_m\alpha_m \in H$. Clearly $d\omega_1$ is a basis of $H$.
Suppose $n \gt 1$. If $H \subset [\omega_1,\cdots,\omega_{n-1}]$, we are done by the induction assumption. So we suppose not all of $a_{1n},\cdots,a_{mn}$ are zero. Let $d =$ gcd$(a_{1n},\cdots,a_{mn})$. Let $a_{in} = b_id$ for $i = 1,\cdots,m$. There exist integers $c_1,\cdots,c_m$ such that $d = c_1a_{1n} + \cdots + c_ma_{mn}$. Let $\beta_n = c_1\alpha_1 + \cdots + c_m\alpha_m$. Then $\gamma_i = \alpha_i- b_i\beta_n \in [\omega_1,\cdots,\omega_{n-1}]$ for $i = 1,\cdots, m$. Since $[\gamma_1,\cdots,\gamma_m] \subset [\omega_1,\cdots,\omega_{n-1}]$ and $[\omega_1,\cdots,\omega_{n-1}] \cap [\beta_n] = 0, [\gamma_1,\cdots,\gamma_m]\cap [\beta_n] = 0$. Hence $H = [\gamma_1,\cdots,\gamma_m] + [\beta_n]$ is a direct sum and we are done by applying the induction assumption on $[\gamma_1,\cdots,\gamma_m]$.