6
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ I guess that the examples discussed in mathoverflow.net/questions/23990 perfectly match your question. $\endgroup$
    – Wadim Zudilin
    Commented Jun 30, 2010 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
    Commented Jun 30, 2010 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
    Commented Jun 30, 2010 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
    Commented Jun 30, 2010 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
    Commented Jul 2, 2010 at 16:04

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Could someone tell me why the link won't appear? $\endgroup$
    – Noah Stein
    Commented Jun 30, 2010 at 19:17
  • $\begingroup$ @Noah, it does now. $\endgroup$
    – Wadim Zudilin
    Commented Jun 30, 2010 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
    Commented Jul 1, 2010 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
    Commented Jul 1, 2010 at 8:39
  • $\begingroup$ The apostrophe should be normally replaced with %27, that's true as well. $\endgroup$
    – Wadim Zudilin
    Commented Jul 1, 2010 at 8:40
5
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\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
    Commented Jul 2, 2010 at 16:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .