Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
    
(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 at 14:33
    
Also there is LatticeReduce[DeleteCases[HermiteDecomposition[m][[2]], {0 ..}]] –  Daniel Lichtblau May 13 at 16:00
    
I should say I'm looking for a basis over N. LatticeReduce gives the basis over Z. –  Tian Lan May 14 at 2:29

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.