# Techniques for solving linear inequalities

For $$n$$ real variables $$x_1, \ldots, x_n$$, I have a bunch of inequalities of form $$2 x_i > x_j + x_k$$ or $$2 x_i < x_j + x_k$$, where $$i,j,k$$ are distinct. My goal is to determine whether this set of inequalities has a solution (the bonus question is to find a solution). It's important that inequalities are strict (otherwise, $$x_1=x_2=\ldots=x_n$$ is a solution).

For every instance, I can feed it to an LP-solver, and get an answer. However, I'm doing it to get an insight into a broader problem, so I'm wondering if there is a humanly-understandable way to check if a solution exists (and possibly find it). I tried to understand the simplex method for this case and didn't get any insights, but maybe it's just me.

There seems to be a relation to "non-negative vector dependence". Namely, if we write every constraint in form $$c_i < 0$$, and there exist $$\alpha_1, \alpha_2, \ldots$$ such that

• $$\alpha_i$$ are non-negative and not all $$\alpha_i$$ are $$0$$, and
• $$\sum_i \alpha_i c_i \equiv 0$$,

then no solution exists (since we can sum up the inequalities with coefficients $$\alpha_i$$ and get $$0 < 0$$).

Examples:

1. $$2x_2 < x_1 + x_3$$ is clearly solvable.
2. $$2x_1 < x_2 + x_3$$, $$2x_2 < x_1 + x_3$$ is solvable by taking a sufficiently large $$x_3$$.
3. $$2x_1 < x_2 + x_3$$, $$2x_2 < x_1 + x_3$$, and $$2x_3 < x_1 + x_2$$ is not solvable: by summing these inequalities, we get $$2 (x_1 + x_2 + x_3) < 2 (x_1 + x_2 + x_3)$$. In this case, the inequalities are non-negatively linearly dependent.

If it somehow simplifies the problem, then a more restrictive version of the problem assumes additional constraints $$x_1 < x_2 < \ldots < x_n$$ (again, important that inequalities are strict). In this case, there seems to be some relation to balanced bracket sequences. Namely, assume that $$+1$$ corresponds to an opening bracket, and $$-1$$ corresponds to a closing bracket. Then there is a contradiction if we can write a balanced bracket sequence using a non-negative combination of the constraints.

Examples: consider 4 variables.

1. Constraint $$2x_2 > x_1 + x_3$$ corresponds to a vector $$(-1,2,-1,0)$$, corresponding to a sequence ')' + '((' + ')' + '' = ')(()', which is not balanced, so no contradiction here.
2. On the other hand, constraint $$2x_1 > x_2 + x_3$$ corresponds to a vector $$(2,-1,-1,0)$$, corresponding to a sequence '((' + ')' + ')' + ''=''(())', which is balanced, and hence there is a contradiction.
3. Constraint $$2x_2 > x_1 + x_4$$ and $$2x_3 < x_1 + x_4$$ correspond to vectors $$(-1,2,0,-1)$$ and $$(1, 0, -2, 1)$$. Summing these vectors, we get $$(0, 2, -2, 0)$$ corresponding to sequence '' + '((' + '))' + '' = '(())', which is balanced, and hence there is a contradiction.
• Have a look at Fourier–Motzkin elimination, that could be done "by hand" Commented Mar 25, 2023 at 16:51
• Thanks! Not sure if it'll lead anywhere (since the number of inequalities grows super-exponentially), but looks like it's worth a try. Commented Mar 25, 2023 at 17:41
• The formulation is a bit ambiguous: are all inequalities of the same type, or you have both types mixed? Commented Mar 26, 2023 at 0:00
• @fedja, Mixed, see the very last example Commented Mar 26, 2023 at 1:33