Skip to main content
Mathematica

Return to Question

added 135 characters in body
Source Link
florin
florin
  • 2.2k
  • 8
  • 13

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.

Here's a second example, where all the methods offered are in difficulty

ST = {{-1, 0}, {0, 1}, {1, -1}, {-2, 1}, {1, -1}}
nu=NullSpace[ST // Transpose]

The null-space contains two positive vectors out of three ({{1, 1, 0, 0, 1}, {-2, -1, 0, 1, 0}, {1, 1, 1, 0, 0}})

The

HermiteDecomposition[nu][[2]]
(*{{1, 0, 0, -1, -1}, {0, 1, 0, 1, 2}, {0, 0, 1, 0, -1}}*)

discovers a third vector. The script I offered has 5 arbitrary constants instead of three, and after playing around with substituting values and reducing size yields another answer {0,1,2,1,0}. The problemimpressive algorithm of @Daniel Lichtblau does not seem to strive for minimality. So, the question of offering a script which works alwaysfor this seemingly elementary problem remains open :)

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.

Here's a second example, where all the methods offered are in difficulty

ST = {{-1, 0}, {0, 1}, {1, -1}, {-2, 1}, {1, -1}}
nu=NullSpace[ST // Transpose]

The null-space contains two positive vectors out of three ({{1, 1, 0, 0, 1}, {-2, -1, 0, 1, 0}, {1, 1, 1, 0, 0}})

The

HermiteDecomposition[nu][[2]]
(*{{1, 0, 0, -1, -1}, {0, 1, 0, 1, 2}, {0, 0, 1, 0, -1}}*)

discovers a third vector. The script I offered has 5 arbitrary constants instead of three, and playing around with substituting values yields another answer {0,1,2,1,0}. The problem of offering a script which works always remains open :)

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.

Here's a second example, where all the methods offered are in difficulty

ST = {{-1, 0}, {0, 1}, {1, -1}, {-2, 1}, {1, -1}}
nu=NullSpace[ST // Transpose]

The null-space contains two positive vectors out of three ({{1, 1, 0, 0, 1}, {-2, -1, 0, 1, 0}, {1, 1, 1, 0, 0}})

The

HermiteDecomposition[nu][[2]]
(*{{1, 0, 0, -1, -1}, {0, 1, 0, 1, 2}, {0, 0, 1, 0, -1}}*)

discovers a third vector. The script I offered has 5 arbitrary constants instead of three, and after playing around with substituting values and reducing size yields another answer {0,1,2,1,0}. The impressive algorithm of @Daniel Lichtblau does not seem to strive for minimality. So, the question of offering a script for this seemingly elementary problem remains open :)

added 361 characters in body; edited title
Source Link
florin
florin
  • 2.2k
  • 8
  • 13

Finding A script for finding a basis of positive vectors in the kernel of a matrix which is minimal in some sense?

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.

Here's a second example, where none ofall the methods offered workare in difficulty

ST = {{-1, 0}, {0, 1}, {1, -1}, {-2, 1}, {1, -1}}
NullSpace[STnu=NullSpace[ST // Transpose]

The null-space contains two positive vectors out of three ({{1, 1, 0, 0, 1}, {-2, -1, 0, 1, 0}, {1, 1, 1, 0, 0}})

The

HermiteDecomposition[nu][[2]]
(*{{1, 0, 0, -1, -1}, {0, 1, 0, 1, 2}, {0, 0, 1, 0, -1}}*)

discovers a third vector. The script I offered has 5 arbitrary constants instead of three, and playing around with substituting values yields another answer {0,1,2,1,0}. The problem of offering a script which works always remains open :)

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.

Here's a second example, where none of the methods offered work

ST = {{-1, 0}, {0, 1}, {1, -1}, {-2, 1}, {1, -1}}
NullSpace[ST // Transpose]

The null-space contains two positive vectors out of three ({{1, 1, 0, 0, 1}, {-2, -1, 0, 1, 0}, {1, 1, 1, 0, 0}})

A script for finding a basis of positive vectors in the kernel of a matrix which is minimal in some sense?

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.

Here's a second example, where all the methods offered are in difficulty

ST = {{-1, 0}, {0, 1}, {1, -1}, {-2, 1}, {1, -1}}
nu=NullSpace[ST // Transpose]

The null-space contains two positive vectors out of three ({{1, 1, 0, 0, 1}, {-2, -1, 0, 1, 0}, {1, 1, 1, 0, 0}})

The

HermiteDecomposition[nu][[2]]
(*{{1, 0, 0, -1, -1}, {0, 1, 0, 1, 2}, {0, 0, 1, 0, -1}}*)

discovers a third vector. The script I offered has 5 arbitrary constants instead of three, and playing around with substituting values yields another answer {0,1,2,1,0}. The problem of offering a script which works always remains open :)

A new matrix where none of the methods work
Source Link
florin
florin
  • 2.2k
  • 8
  • 13

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

Here's a second example, takewhere none of the methods offered work

Fm=ST = {{-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,12, 1},
    {0,0,0,1,-1, -1}};
xx = Array[x, 6];
x = xxNullSpace[ST /. FindInstance[{xx . Fm == 0, xx >= 0}, xx, Integers,/ 4]Transpose]

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) andnull-space contains two positive vectors out of three (0,1,1,1,0,1{{1, 1, 0, 0, 1}, {-2, -1, 0, 1, 0}, {1, 1, 1, 0, 0}})

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)

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.

Here's a second example, where none of the methods offered work

ST = {{-1, 0}, {0, 1}, {1, -1}, {-2, 1}, {1, -1}}
NullSpace[ST // Transpose]

The null-space contains two positive vectors out of three ({{1, 1, 0, 0, 1}, {-2, -1, 0, 1, 0}, {1, 1, 1, 0, 0}})

added 50 characters in body
Source Link
florin
florin
  • 2.2k
  • 8
  • 13
I added a new example, showing that FindInstance does not guarantee independence
Source Link
florin
florin
  • 2.2k
  • 8
  • 13
Source Link
florin
florin
  • 2.2k
  • 8
  • 13