Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer 1

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.