[Math] Existence/Uniqueness of Nonnegative Solutions of Linear Systems of Equations

linear algebralinear programming

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.

Best Answer

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.

Related Question