# Finding whether a solution exists to the given system of equations

Given $(a_1,b_1,c_1), (a_2,b_2,c_2),\ldots, (a_n,b_n,c_n)$

We need to decide if there exists non-negative coefficients:

$X = (x_1,x_2,\ldots,x_n)$

such that

$$x_1 a_1 + x_2 a_2 + \ldots + x_n a_n = x_1 b_1 + x_2 b_2 + \ldots + x_n b_n = x_1 c_1 + x_2 c_2 + \ldots + x_n c_n$$

How to do it efficiently?

The above problem is a part of my solution while solving the following ACM/ICPC problem

• You might want to take algorithms questions to cs.SE. – Raphael Apr 8 '12 at 14:27
• @mixedmath All he is requesting is nonnegativity. The knapsack problem requires nonnegative integers. If non integral solutions are allowed, this is not too difficult in theory (it is a linear programming feasibility problem). Some modification of the simplex algorithm should find a solution fairly rapidly. – deinst Apr 8 '12 at 17:33
• Oh, non-integers. Well that's just silly. Then this is far more reasonable, you're right. – davidlowryduda Apr 8 '12 at 23:30

Trivially, $x_i=0$ is a solution, so I assume the problem is to find a solution where at least one of the $x_i$ is positive.
First consider the equation $$\sum_{i=1}^n a_ix_i = \sum_{i=1}^n b_ix_i.$$ If $a_i=b_i$ for all $i$, then this is trivially satisfied, otherwise there is some $i$ where $a_i\ne b_i$. Assume w.l.o.g. that $a_1\ne b_1$. Then $$x_1=\sum_{i=2}^n \frac{b_i-a_i}{a_1-b_1}x_i.$$ Now consider the equation $$\sum_{i=1}^n a_ix_i = \sum_{i=1}^n c_ix_i.$$ which, upon substitution for $x_1$ becomes $$\sum_{i=2}^n\left(a_i+\frac{b_i-a_i}{a_1-b_1}a_1\right)x_i=\sum_{i=2}^n\left(c_i+\frac{b_i-a_i}{a_1-b_1}c_1\right)x_i.$$ If these are equal, the equation is trivially satisfied, otherwise there is some index where $$a_i+\frac{b_i-a_i}{a_1-b_1}a_1\ne c_i+\frac{b_i-a_i}{a_1-b_1}c_1.$$ Assume w.l.o.g. that this index is $i=2$ This will allow us to find $x_2$ in terms of the other $x_i$'s, $i>2$, say $x_2=\sum_{i=3}^n d_i x_i$, and we can substitute this into our equation for $x_1$, giving us an equation for $x_1$ in terms of $x_3,\ldots,x_n$, say $x_1=\sum_{i=3}^n e_i x_i$.
If all the $d_i$ or all the $e_i$ are negative, then obviously there is no solution. Or if one is nonpositive and the other is negative when it is 0, there is no solution. Otherwise, if for some $i$ both $d_i$ and $e_i$ are nonnegative, then setting $x_i=1$ is a solution. So there are indices $i$ where $d_i>0$ and $e_i<0$, and indices $j$ where $d_j<0$ and $e_j>0$. If there are such $i$ and $j$ so that $\frac{e_j}{-e_i}>\frac{d_i}{-d_j}$ then there is a solution, otherwise not.