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.
 A: 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]$.
