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.

I have a set of (real) linear equations/inequalities and I want to know whether they have a solution, and to find at least one. The goal is to do this quickly. FindInstance seems rather slow -- it is possible that it's just the size of my problem, but I thought it could be done faster. In particular, since all my equations are linear, I thought I might try to see if LinearProgramming would be faster. Unfortunately, the function doesn't seem to take parameters the way I want it to: I have 0-1 matrices $M_1$, $M_2$, and seek a vector $x$ such that $M_1x = 0$ and $M_2x \geq 1$. The vector $x$ is however allowed to have negative entries. Any help for how to solve this problem is appreciated.

Edit: on request, here is an example of $M_1$ (in fact, it always looks like three identity matrices, though its size varies) and of $M_2$ (which has, to the best of my knowledge no nice pattern except that it has precisely 3 ones per row):

M1 = {{1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0}, 
      {0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0}, 
      {0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0}, 
      {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1}};

M2 = {{0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}, 
      {0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0}, 
      {0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0}};

I am looking for a real vector $x$ of length 12 (in this case) such that $M_1x = 0$ and each entry of $M_2x$ is at least 1.

share|improve this question
    
"I have a set of (real) linear equations/inequalities..." - where are they? –  J. M. Jun 5 '13 at 14:21
    
It's not a single specific set; different (but similar) equations arise depending on some parameters, which I want to be able to vary. The problem itself is rather obscure and I don't think attempting to explain it would help anyone to understand the question. I think I have put all the notable information about the constraints in the question. –  jona Jun 5 '13 at 14:26
    
Okay, but gives us some code/examples to work with; it's hard to help if you've nothing definite to supply. –  J. M. Jun 5 '13 at 14:28
1  
I find there are no solutions to this particular problem. –  b.gatessucks Jun 5 '13 at 15:36

1 Answer 1

To ensure ${\boldsymbol{\mathrm M}}_1 \cdot {\boldsymbol{x}} = \boldsymbol{0}$, $\boldsymbol x$ must lies in the null space of ${\boldsymbol{\mathrm M}}_1$:

ns = NullSpace[M1];
x = MapIndexed[c[#2[[1]]] #1 &, ns] // Total

For the constraint $\left({\boldsymbol{\mathrm M}}_2 \cdot {\boldsymbol{x}}\right)_k \geq 1, (k=1,2,3)$, we can use Reduce to invesgate it:

Reduce[And @@ Thread[M2.x >= 1]]

False

So there is no solution for your example.

Edit

For cases where there do exist solutions, we can get instances as following. Here we take the M1 in original question and

M2 = {{1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1},
      {0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0},
      {0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0}};

for example.

After obtaining x as described above, we continue with

cond = Reduce[And @@ Thread[M2.x >= 1]]
coeffSet = FindInstance[cond, Union[Cases[x, c[_], ∞]], Reals, 5]
x /. coeffSet

enter image description here

To verify the solutions we found:

SetAttributes[c, NHoldAll]
Column[{M1.x, N[M2.x]}] /. coeffSet

enter image description here

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.