Given a matrix $M$, I want to find a nontrivial vector in the kernel of $M$ that also lies in the first orthant, if such a vector exists. That is, I want to simultaneously solve


$$Mx = 0$$
$$x \geq 0$$
$$x \neq 0$$


I'm having trouble phrasing this problem in a way that can be efficiently solved numerically. One approach I've tried is to solve


$$\min\_x \|Mx\|^2\quad s.t. \quad x\geq 0, x\_i = 1$$


using nonnegative least squares for every $i$, and looking for solutions whose minimum is 0. If the minimum is positive for every $i$, the original problem had no solution. Unfortunately, in addition to being inefficient (I have to do $\dim x$ solves), standard least squares packages are having great difficulty converging for this approach.


Is there a better way to solve this problem?



finding an element of a vector subspace contained in the first orthant
@Ben's answer is within $\epsilon$ of correct. The problem with it is that (depending on how you interpret the constrains $x\_i \geq 1$) there might be no solution with either a specific $x\_{i\_0} > 0,$ or *all* $x\_i>0,$ and as in the original question, cycling through all the indices is inefficientInstead you use Gordan's theorem (see <http://en.wikipedia.org/wiki/Farkas_lemma>, "further implications"), which says that the OP is equivalent to the existence of a solution to $M^t y < 0,$ which is equivalent to 
$M^t y \leq -\mathbf{1}.$


