Fix a discrete addition subgroup in $\mathbb{R}^n$. Given a finite spanning set, how can one find a group basis?

## 1 Answer

Fix a $d$-dimensional discrete addition subgroup $L\subset \mathbb{R}^n$. Call the spanning elements $v_1,\dots, v_k\in L$ and the matrix whose columns are these $v$'s as $V\in \mathbb{R}^{n\times k}$. We seek a group basis $b_1,\dots,b_d\in L$.

Two solutions. I have tried the first one since it is readily implementable.

The LLL algorithm is strong enough to perform this reduction.

Affix $I_{k\times k}$ to the top of $V\in \mathbb{R}^{n\times k}$ forming $V^\ast \in \mathbb{R}^{(n+k)\times k}$. Run the LLL algorithm on the columns of $V^\ast$ using the seminorm that equals the norm of the bottom $n$ components. The nonzero last-$n$-components of the LLL-reduced vectors will form a basis for the desired subgroup. The first $k$ components give coordinates for this basis in terms of input vectors $V$.

(Or also, form $V^\ast$ by instead affixing $\varepsilon \cdot I_{k\times k}$. For $\varepsilon$ small enough, the LLL algorithm with the usual norm does the same thing.)

Johannes Buchmann and Michael Pohst. Computing a lattice basis from a
system of generating vectors. In *European Conference on Computer Algebra*,
pages 54–63. Springer, 1987.

Run an exhaustive *Simultaneous Integer Relations Algorithm* on $V\in \mathbb{R}^{n\times k}$, the matrix whose columns are $v_1,\dots, v_k$. This algorihtm finds a matrix $R\in \mathbb{Z}^{k\times r}$ of all, say, $r$ independent integer relations for the input vectors, i.e. $VR=0\in \mathbb{R}^n.$ Now run the *S. I. R. A.* on $R'$ to find a matrix $S\in \mathbb{Z}^{k\times r^\ast}$. Columns of $VS$ form the desired basis.

5more comments