How to verify whether or not there exists a vector $x$ such that $Ax > 0$?

Question

Given a matrix $A$ in $\mathbb R^{m\times 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?

Answer 1

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 $\mathbb{R}^m$, and not all subspaces of $\mathbb{R}^m$ intersect the set $\{(x_1,...,x_m) \in \mathbb{R}^m\; |\; 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.

Answer 2

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 : A\mathbf 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 = \frac1{n+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$.)

Answer 3

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).

Answer 4

This is an elaboration on LinAlg's comment on my answer.

Using the simplex method, solve the optimization problem of maximizing $t \in \mathbb R$ subject to $$A \mathbf x - t \mathbf 1 \ge \mathbf 0$$ (where $\mathbf 0, \mathbf 1$ are the constant vectors). I say "maximize" but actually you can stop as soon as $t>0$.

• If there is a solution with $t>0$, then $A \mathbf x > \mathbf 0$ at that solution, because $(A \mathbf x)_i \ge t > 0$ for all $i$.
• Conversely, if there is any $\mathbf x \in \mathbb R^n$ with $A \mathbf x > \mathbf 0$, then by setting $t$ to be the smallest component of the vector $A\mathbf x$, we get a solution to $A \mathbf x - t \mathbf 1 \ge \mathbf 0$ with $t > 0$.