Suppose we have an $m$x$n$ matrix $A$, with $m\lt n$, and an $m$x$1$ vector $b$. Are there existence and uniqueness conditions characterizing nonnegative solutions of the system of linear equations $Ax=b$? i.e. When is there an $x\geq 0$ such that $Ax$=$b$?

I'm sure it is a very well-known result I'm after here but I can't seem to find the answer easily. Any references would be helpful. This (http://www.jstor.org/pss/1968384) looks related but it is not free.

  • $\begingroup$ I guess that the examples discussed in mathoverflow.net/questions/23990 perfectly match your question. $\endgroup$ – Wadim Zudilin Jun 30 '10 at 14:24
  • $\begingroup$ And I can't understand the meaning of "uniqueness" in this case: you simply hav to check whether $\operatorname{rank}(A)=m$. $\endgroup$ – Wadim Zudilin Jun 30 '10 at 14:29
  • $\begingroup$ I think it may be different - I put no constraints on $b$, and I am not interested in integer solutions. $\endgroup$ – Adam Clarridge Jun 30 '10 at 18:52
  • $\begingroup$ Also, if rank($A$)$=m$, then since we have the constraint on $x$ I don't think we are guaranteed any solutions (in the unconstrained case we are guaranteed infinitely many). $\endgroup$ – Adam Clarridge Jun 30 '10 at 19:10
  • $\begingroup$ I checked the jstor article you mentioned and it does not contain any terribly useful information for this question. It does not address uniqueness, only feasibility. It gives a procedure for checking feasibility, but it is not a simple criterion anyway. The paper is old (1926) and much work has been done on LP since then. So if you just wanted to check feasibility, you'd be better off with modern methods, anyway. $\endgroup$ – Noah Stein Jul 2 '10 at 16:04

The following work seems to be exactly what you want.

M. Wang, and A. Tang. Conditions for a Unique Non-negative Solution to an Underdetermined System.
in Proc. of Allerton Conference , Monticello, Illinois, Sep. 2009.

Here is the link: http://networks.ece.cornell.edu/meng/pub/Allerton09.pdf

  • $\begingroup$ That looks interesting, but it seems to only address the compressed sensing problem where one expects the solution to be sparse (i.e. have few nonzero values). That was not the case in the question raised here. $\endgroup$ – Noah Stein Jul 2 '10 at 16:10

Perhaps this should be a comment but it is too long.

The classic result used for existence is (Farkas' Lemma), though this gives a non-existence condition rather than an existence condition. It says given any such problem there is another such problem associated with it and exactly one of them has a solution. It is equivalent to the separating hyperplane, linear programming duality, and minimax theorems.

As for uniqueness, I do not know of a direct characterization. Given a specific such system one can determine uniqueness by trying to minimize and maximize each coordinate over the feasible set. The min and max are equal for all coordinates if and only if the solution is unique (in fact one could get away with solving $n+1$ LPs rather than $2n$). But this doesn't give a directly applicable analytic condition.

Finally, it is worth noting in reference to Wadim's comment, that uniqueness can be a subtle issue for linear programs. In particular, it is possible that the affine subset defined by the equations has positive dimension, but intersects the positive cone in a single point. For example, consider the homogeneous equation $x_1 + \ldots + x_n = 0$. This has one nonnegative solution, the zero solution. No matter how many linearly dependent or independent homogeneous equations you add, this will still be true. So the rank of A does not determine uniquness.

  • $\begingroup$ Could someone tell me why the link won't appear? $\endgroup$ – Noah Stein Jun 30 '10 at 19:17
  • $\begingroup$ @Noah, it does now. $\endgroup$ – Wadim Zudilin Jun 30 '10 at 22:43
  • $\begingroup$ Thanks. So replacing the apostrophe in the url with %27 was what was needed? I want to be able to do it myself in the future. $\endgroup$ – Noah Stein Jul 1 '10 at 1:21
  • $\begingroup$ I use the html syntax. Please start editing your file, see the source, and then cancel editing; this will show you how does it normally work. $\endgroup$ – Wadim Zudilin Jul 1 '10 at 8:39
  • $\begingroup$ The apostrophe should be normally replaced with %27, that's true as well. $\endgroup$ – Wadim Zudilin Jul 1 '10 at 8:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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