Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
4  
How about solving $Mx=0$, $x\ge 0$, $\sum x_i=1$. At least its an LP then. –  Anthony Quas Jan 15 '11 at 19:03

2 Answers 2

up vote 3 down vote accepted

@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}.$

share|improve this answer

Yes, it's called linear programming. As Anthony notes above, you'll have rephrase your question a bit to get it in this framework. If really just want any element of that orthant, you can minimize $\sum x_i$ with respect to the constraints $x_i\geq 1$ and $Mx=0$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.