Q:

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

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?

A:

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

