# A math function similar to “LatticeReduce” for finding linear independent basis

We would like to ask a math function similar to "LatticeReduce" for finding linear independent basis. The input is a list of vectors $M=\{v_1,v_2,v_3,\dots\}$, with the following property:

There is a subset $O=\{w_1,w_2,w_3,\dots\}\subset M$, such that $O$ is a basis, i.e. linearly independent and span $M$, $$v_i=\sum_a c_{ia} w_a.$$ Moreover, the coefficients $c_{ia}$ are non-negative integers.

An explicit example is the following:

$$M=\left( \begin{array}{ccccc} 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 & 1 \\ 1 & 1 & -1 & 1 & -1 \\ 1 & 1 & 1 & -1 & -1 \\ 2 & -2 & 0 & 0 & 0 \\ 2 & 2 & 2 & 0 & 0 \\ 2 & 2 & 0 & 2 & 0 \\ 2 & 2 & 0 & 0 & 2 \\ 2 & 2 & -2 & 0 & 0 \\ 2 & 2 & 0 & -2 & 0 \\ 2 & 2 & 0 & 0 & -2 \end{array} \right),\quad O=\left( \begin{array}{ccccc} 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 & 1 \\ 1 & 1 & -1 & 1 & -1 \\ 1 & 1 & 1 & -1 & -1 \\ 2 & -2 & 0 & 0 & 0 \end{array} \right),$$ where $O$ is the first 5 rows of $M$ and $$M[[6]]=O[[1]]+O[[4]],\, M[[7]]=O[[1]]+O[[3]],\,\dots$$

In Mathematica form, the example is

m = {{1,  1,  1,  1,  1},
{1,  1, -1, -1,  1},
{1,  1, -1,  1, -1},
{1,  1,  1, -1, -1},
{2, -2,  0,  0,  0},
{2,  2,  2,  0,  0},
{2,  2,  0,  2,  0},
{2,  2,  0,  0,  2},
{2,  2, -2,  0,  0},
{2,  2,  0, -2,  0},
{2,  2,  0,  0, -2}};

May we know that how to write a function/program such that inputting such $M$, the program will output the desired $O$.

For this example the built-in function LatticeReduce works well. But we are not sure it always works.

-
(1) Would be helpful if your "example" was comprised of cut-and-pastable Mathematica input. (2) What is it about LatticeReduce that you are not sure always works? (3) Are you looking for a basis over Q or over Z? If over Q, just use RowReduce. – Daniel Lichtblau May 13 '14 at 14:33
Also there is LatticeReduce[DeleteCases[HermiteDecomposition[m][[2]], {0 ..}]] – Daniel Lichtblau May 13 '14 at 16:00
I should say I'm looking for a basis over N. LatticeReduce gives the basis over Z. – Tian Lan May 14 '14 at 2:29