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



Find a lattice basis given too many points
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](https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_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.


