Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a list of vectors, I want a linear combination with positive coefficients that produces a final vector with only positive values (EDIT: this final vector is unknown; any positive vector is viable). If it's known that such a solution exists, any suggestions on an algorithm to find such a combination?

share|cite|improve this question
This can be expressed as a linear program. – copper.hat Jul 3 '13 at 18:59
Just to make sure I understood, are you trying to solve $\sum_k \alpha_k v_k = b$, where $\alpha_k \ge 0$? Or are you trying to see if the convex cone generated by the vectors intersects the interior of the positive quadrant? – copper.hat Jul 3 '13 at 19:10
Where b is unknown, yes. Any positive a that produces a positive b is acceptable. (editing question for clarity) – akroy Jul 3 '13 at 20:22
Solve $\min_{\alpha,x} \{ \alpha | -e_k^T A x -\alpha \le 0, x \ge 0 \}$. If the minimum is $<0$ then a solution exists, otherwise it doesn't. – copper.hat Jul 3 '13 at 20:39
It's known that a solution exists, I'm curious how to find it. (out of curiosity, what does that expression actually represent? What is the e_k there?) – akroy Jul 3 '13 at 21:10

Put all vectors in the list as columns of the matrix $A$ and the result vector as a the column-vector $\vec{b}$. You seek such $\vec{x}$ that $A \vec{x} = \vec{b}$.

You can now solve the problem by Gaussian Elimination.

share|cite|improve this answer
The OP needs the constraint $x \ge 0$ as well. – copper.hat Jul 3 '13 at 19:09
I need x>=0, and I don't know the resultant vector (will edit question to be more clear) – akroy Jul 3 '13 at 20:20

Your Answer


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.