Vtyjkyuk

Given a matrix $A$ in $mathbb R^mtimes n$, if I want to know whether or not there is an $x in mathbb R^n$ such that
$$
Ax > 0,
$$
(meaning all elements in $Ax$ are positive). Is there some easy way to verify whether or not such $x$ exists?

This can be done by iterating the simplex method. (Or your favorite method for solving linear programs.)

We want to know if the polytope $P = mathbf x : Amathbf x ge mathbf 0$ has an interior point. To do this, we will try to find $n+1$ affinely independent points in $P$, then average them.

Let $mathbf x^0 = mathbf 0$. This will be the first of our points. Then we iterate: to find $mathbf x^i$ when we've found $mathbf x^0, dots, mathbf x^i-1$, pick a vector $mathbf c$ such that $mathbf c cdot mathbf x^0 = dots = mathbf c cdot mathbf x^i-1 = 0$, and solve the LP maximizing $mathbf c cdot mathbf x$ over $P$. If this finds a point $mathbf x$ with $mathbf c cdot mathbf x ne 0$, let that be $mathbf x^i$. Otherwise, we know that $P$ has no interior point, because it is contained in the hyperplane $mathbf x : mathbf c cdot mathbf x = 0$.

Once we've gotten $n+1$ points $mathbf x^0, dots, mathbf x^n$, let $mathbf x = frac1n+1(mathbf x^0 + dots + mathbf x^n)$: this will be the interior point we're looking for. (It's an interior point of the convex hull of $mathbf x^0, dots, mathbf x^n$, so it's also an interior point of $P$.)

It's going to depend on the matrix $A$. For example, if $A$ is the all zero matrix, then the answer is no. If $A$ is full rank, then the answer is yes. In general the image of $A$ will be a subspace of $mathbbR^m$, and not all subspaces of $mathbbR^m$ intersect the set $; x_i > 0 ;forall i = 1,...,m$.

More concretely, the image of $A$ is the span of its columns. So, if $A$ contains a column where every entry is positive (or, equivalently if every entry is negative), then you know such a vector $x$ exists. Or, if you can find some linear combination of its columns such that each entry is positive, then you know again that such an $x$ exists.

edit: Added a more concrete method.

One way to find x for Ax>0 would be to solve an artificial problem:

• min y where (Ax + y)>0

If none of the y variables are in basis in the optimal solution of the artificial problem then a solution exists for Ax>0 where x>0.

For more information about finding a starting solution (or basic feasible solution) for the Simplex Method method please see Chapter Four: Starting Solution and Convergence on pp. 151 - 198 of "Linear Programming and Network Flows" [Fourth Edition] by Bazaraa, Jarvis and Sherali (2010).