# When does an under-specified linear sy stem have a unique solution?

by Erel Segal-Halevi   Last Updated January 11, 2019 12:20 PM

Consider the system of two equations with three real variables $$x,y,z$$: $$a_{11}\cdot x + a_{12} \cdot y + a_{13} \cdot z = b_1 \\ a_{21} \cdot (1-x) + a_{22} \cdot (1-y) + a_{23} \cdot (1-z) = b_2$$ where $$x,y,z\geq 0$$.

Since there are less equations than variables, this system may have infinitely many solutions. My question is: is there a simple condition on $$b_1,b_2$$ (as a function of the coefficients $$a_{ij}$$), that guarantees that this system has a unique solution?

Tags :

For example if you have that $$a_{11},a_{12},a_{13}>0$$ and $$b_1=0$$ your only solution for the first equation is $$x=y=z=0$$ that is a solution for the second equation if and only if

$$b_2=a_{21}+a_{22}+a_{23}$$

So in the case in which $$\begin{cases} b_1=0\\ b_2=a_{21}+a_{22}+a_{23} \end{cases}$$

your only solution is $$x=y=z=0$$

The geometric idea is no difficult. Your system of equations represent the locus of the intersection of two planes related by your equations but in general in $$\mathbb{R}^3$$ the intersection of two planes is the empty set or a plane (if the two planes are equal) or a line. There is not the case in which the intersection is one single point. But In your case you must consider also the condition $$x,y,z\geq 0$$ so you can consider $$b_1,b_2$$ such that the two different planes intersect them in a line and that line passes on the origin and its intersection with the locus $$x,y,z\geq 0$$ is only the origin. In this case your only solution will be the origin.

In general the answer is no: you are looking for a solution $$x\geq0$$ to the problem $$Ax=b$$. Suppose there is no vector $$y$$ (of right size) such that $$A^Ty>0$$ (1). Then by the dual version of Gordan's lemma there exists some $$z>0$$ such that $$Az=0$$. Therefore in this case, either there is no solution $$x\geq0$$, or $$x\geq0$$ produces $$Ax=b$$, and then $$A(x+z)=b$$ with $$x+z\geq0$$, so you have at least two solutions. Since your $$A$$ is completely arbitrary, you have cases satisfying (1).