1
$\begingroup$

How can I use Mathematica to check if a system of the form $A x > 0$ admits a solution $x\geq 0$ where $A$ is a $m \times n$ matrix and $x \in \mathbb{R}^n$. All inequalities are to be understood componentwise. Thanks a lot!

An example of such a matrix $A$ would be $$A = \left( \begin{array}{cccc} -1 & -1 & 1 & 1 \\ 1 & 0 & 0 & -1 \\ \end{array} \right)$$

The goal is to have a function that takes an arbitrary matrix a as an input and returns True or False depending on whether or not such a solution exists.

$\endgroup$
1
$\begingroup$

You can also look at it in general:

mat = Array[a, {3, 2}];
vec = Array[x, 2];
Reduce[mat.vec > 0 && vec >= 0]

This gives a fairly verbose description of the relationships between the a[i,j] that must hold in order the the inequality to be fulfilled.

For your specific example

a = {{-1, -1, 1, 1}, {1, 0, 0, -1}};
vec = Array[x, 4];
Reduce[a.vec > 0 && vec >= 0]

x[4] >= 0 && x[1] > x[4] && x[3] > x[1] - x[4] && 0 <= x[2] < -x[1] + x[3] + x[4]

You get a nice concise answer. And if there is no answer, it simply returns False:

a = {{-1, -1, -1, -1}, {0, 0, 0, 0}};
vec = Array[x, 4];
Reduce[a.vec > 0 && vec >= 0]  

False.
$\endgroup$
  • $\begingroup$ Thanks a lot! Is there a possibility of doing this when the dimensions of a are not known a priori? $\endgroup$ – Peter Jun 26 '19 at 16:04
  • $\begingroup$ If you can't specify the matrix, it's hard to see what kind of answer you might expect to see. $\endgroup$ – bill s Jun 26 '19 at 16:08
  • $\begingroup$ I am looking for a function which just returns true false depending on whether or not a solution exists. Thanks again your answer is super helpful. $\endgroup$ – Peter Jun 26 '19 at 16:10
1
$\begingroup$

You can use FindInstance. I use Mathematica 12, in order to use both VectorGreater and PositiveReals:

FindInstance[
    VectorGreater[{A.x, 0}] && x ∈ Vectors[4, PositiveReals],
    x
]

{{x -> {5/4, 1/4, 1, 1}}}

When typeset in Mathematica, the above looks like:

enter image description here

$\endgroup$
  • $\begingroup$ Thanks a lot. That is a great solution. $\endgroup$ – Peter Jun 27 '19 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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