How to find out if $Aw \ge 0$ has a nontrivial solution $w \neq 0$? How do we find out if to a (not necessarily square) matrix $A$ there exists a vector $w \neq 0$ such that $A w \ge 0$? Is there a "simple" criterion in terms of the matrix $A$? (where $\ge 0$ is meant componentwise)
Edit:
To clarify: the standard form of a linear program is $max\{cx | x \ge 0, Ax\le b\}$, but I am not assuming that $w \ge 0$ or $ w \le 0$.
 A: Consider the linear program: maximize $w_1$, given $Aw\ge0$. (Here $w_i$ is the $i$-entry of $w$.) Standard LP technology will tell you if this problem has a feasible solution (and find it). If there is no solution, then any vector $w$ such that $Aw\ge0$ must have $w_1=0$. In this case look for the maximum of $w_2$ subject to the constraints $Aw\ge0$ and $w_1=0$. Continue in the obvious fashion.
The key point is that you can view your question as asking whether a certain LP has a feasible solution.
A: One can use the double description algorithm, and the method suggested by Chris Godsil to find out if the problem has a nontrivial solution:
A double description is a pair of matrices $(A,R)$ such that:
$Aw\ge0$ if and only if $w=Rx, x\ge 0$
The Minkowski theorem guarantes that such a double description always exists.
The algorithm computes such a double description.
See (https://pdfs.semanticscholar.org/b08b/ed1257fa4c8dacc1dce10772465c98d7bcae.pdf) for a reference.
Suppose now that we have a double description $(A,R)$, then one might formulate, as Chris Godsil pointed out, the problem:
Maximize $x_1$ subject to $ARx\ge 0, x \ge 0$. If there is a solution, then a nontrivial solution to the original problem exists $w=Rx$, otherwise continue with $x_2$ etc. If there is no solution for all $x_1,x_2,\cdots $ then the only solution is $w=0$.
