Skip to main content
2 of 6
I added a new example, showing that FindInstance does not guarantee independence
florin
  • 2.2k
  • 8
  • 13

Finding a basis of positive vectors in the kernel of a matrix

The kernel to the left of the matrix

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

may be generated by {0, 0, 1, 1, 1},{2, 1, 0, 2, 1}, as easily checked

{0, 0, 1, 1, 1} . Nm
{2, 1, 0, 2, 1} . Nm

I need a script which finds a positive (nonnegative) basis for arbitrary integer valued matrix. For now, I am working with

tx = Table[x[i], {i, 5}];Solve[Thread[tx . Nm == 0], tx]

and then searching with pencil for an answer. I tried things like adding positivity conditions

Solve[Join[Thread[tx . Nm == 0], Thread[tx >= 0]], tx]

or

FindInstance[Join[Thread[tx . Nm == 0], Thread[tx > 0]], tx, 2]

but they don't seem to advance me, so I'm asking for help. For a second example, take

Fm={{-1,1,1,0,0,0},{-1,1,0,0,0,1},{1,-1,-1,0,0,0},{0,0,1,-1,1,0},{0,0,0,-1,1,1},{0,0,0,1,-1,-1}};
xx = Array[x, 6];
x = xx /. FindInstance[{xx . Fm == 0, xx >= 0}, xx, Integers, 4]

yields {337, 0, 337, 0, 0, 0} and {275, 0, 275, 0, 0, 0}, which represent both (1,0,1,0,0,0), so no independence. The answer I'm after should include also (0,0,0,0,1,1) and (0,1,1,1,0,1)

florin
  • 2.2k
  • 8
  • 13