Checking if a system of linear equations admits a positive solution

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.

2 Answers

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.

• Thanks a lot! Is there a possibility of doing this when the dimensions of a are not known a priori? – Peter Jun 26 '19 at 16:04
• If you can't specify the matrix, it's hard to see what kind of answer you might expect to see. – bill s Jun 26 '19 at 16:08
• 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. – Peter Jun 26 '19 at 16:10

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:

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