# Does conjunction of linear inequalities implies the summation of them

Let A and B represent two linear inequalities:

$$A : a_1 x_1 + ... + a_n x_n \geq k_1$$

$$B : b_1 x_1 + ... + b_n x_n \geq k_2$$

If A and B is unsatisfiable (does not have solution), does the following hold in general (the conjunction of two inequalities implies the summation of them )? If so, I am looking for a formal proof?

$$A \land B \implies A + B$$

$$𝑎_1𝑥_1+...+𝑎_n𝑥_n \geq𝑘1 \;\; \land \;\; 𝑏_1𝑥_1+...𝑏_n𝑥_n\geq 𝑘_2 \implies 𝑎_1𝑥_1+...+𝑎_n𝑥_n + 𝑏_1𝑥_1+...𝑏_n𝑥_n \geq 𝑘_1+𝑘_2$$

and then I would like to generalize the above theorem to summation of several inequalities.

My attempt: My intuition is that if A and B be unsatisfiable, there is a matrix of Farkas coefficient C such that the weighted sum of A + B would be zero, and leads to -1 > 0 contradiction. Since A and B are unsatisfiable, the conjunction would be false. Therefore $$\bot \implies \bot$$ which is a correct statement.

My question is how to generalise this proof for a system of linear inequalities $$A : \bigwedge \Sigma_{i=1}^{n} a_i x_i\leq k_i \;\; \wedge \;\; \bigwedge \Sigma_{i=1}^{n} b_i y_i\leq l_i$$

and

$$B: \bigwedge \Sigma_{j=1}^{n} a_j x_j\leq w_j \;\; \wedge \;\; \bigwedge \Sigma_{j=1}^{n} b_j y_j\leq z_j$$

• Your notation is not clear. Do you mean the following: IF $a_1x_1+...+b_1x_1+... \ge k_1+k_2$ THEN $a_1x_1+...\ge k_1$ AND $b_1x_1+...\ge k_2$. That would be false. – Chrystomath Oct 1 '19 at 11:10
• @Chrystomath I Edited and tried to make it clear. – SarA Oct 2 '19 at 9:37

This does not hold in general. Consider $$A: x > 2$$ and $$B: x > 4$$. Then $$A+B: 2x > 6$$ which is equivalent to $$x > 3$$. This cannot be written as some suitable combination of $$A$$ and $$B$$.

• sorry I Edited my question and added the assumption that two inEqualities are **unsatisfiable**(This system does not have solution) – SarA Oct 1 '19 at 11:32

It's still false, even with the unsatisfiability assumption.

Consider the inequalities \begin{align} -2x &> 2 \\ x & > 3 \end{align} Their sum is $$-x > 5$$ i.e., $$x < -5$$. But $$x < -5$$ does not imply that $$x > 3$$.

• Thanks for your reply. A typo in your reply is i.e., 𝑥<5; it should be 𝑥<-5 – SarA Oct 1 '19 at 11:42
• how about the reverse implication? do you have counter-example for that A /\ B implies A + B – SarA Oct 1 '19 at 11:46
• I've fixed that; thanks. As for the reverse implication ... I'm going to let you think about that. It'll be a good learning experience. – John Hughes Oct 1 '19 at 13:42
• if I multiply your 2nd inequality by 2 the summation will be 0 >8, the implication would be false implies false which is a correct statement. Am I right? – SarA Oct 1 '19 at 13:54
• Yes, that's true. But it's not what your question asked about. – John Hughes Oct 1 '19 at 13:56

Solution to third version of problem:

Write $$\mathbf{a}\cdot \mathbf{x}$$ for $$a_1x_1+\cdots+a_nx_n$$. Then each inequality is of the type $$\mathbf{a}\cdot \mathbf{x}\ge k$$. If you have a bunch of them, then you get for example \begin{align*} \mathbf{a}\cdot \mathbf{x}\ge k_1\\ \mathbf{b}\cdot \mathbf{x}\ge k_2\\ \ldots\\ \mathbf{g}\cdot \mathbf{x}\ge k_7 \end{align*}

Now from algebra, $$(\mathbf{a}+\mathbf{b})\cdot \mathbf{x}=\mathbf{a}\cdot \mathbf{x}+\mathbf{b}\cdot \mathbf{x}$$.

Proof \begin{align*}(a_1+b_1)x_1+(a_2+b_2)x_2+\cdots&=a_1x_1+b_1x_1+a_2x_2+b_2x_2+\cdots\\ &=(a_1x_1+a_2x_2+\cdots)+(b_1x_1+b_2x_2+\cdots),\end{align*}

So if $$\mathbf{a}\cdot \mathbf{x}\ge k_1$$ and $$\mathbf{b}\cdot \mathbf{x}\ge k_2$$ then $$(\mathbf{a}+\mathbf{b})\cdot \mathbf{x}\ge k_1+k_2$$.

Hence one can show your statement to be true by induction. For this, I'm going to use $$\mathbf{a}_1,\mathbf{a}_2,\ldots$$ for each collection of parameters instead of $$\mathbf{a},\mathbf{b},\ldots$$; they are not to be confused with the previous real number parameters $$a_1,a_2,\ldots$$. It is true for $$n=1$$ (and $$n=2$$ by the above), so if it is true for $$n$$ inequalities $$\mathbf{a}_1\cdot\mathbf{x}\ge k_1,\ldots,\mathbf{a}_n\cdot\mathbf{x}\ge k_n$$, and you're given $$n+1$$ inequalities, then

\begin{align*}(\mathbf{a}_1+\mathbf{a}_2+\cdots+\mathbf{a}_n+\mathbf{a}_{n+1})\cdot x&=(\mathbf{a}_1+\cdots+\mathbf{a}_n)\cdot x+\mathbf{a}_{n+1}\cdot x\\ &\ge(k_1+\cdots+k_n)+k_{n+1}\\ &=k_1+\cdots+k_{n+1} \end{align*}

• Thanks for your thorough explanation. The proof would be similar for the generalised version? Last part of my question where 𝐴: Σ𝑎𝑖𝑥𝑖≤𝑘 ⋀ Σ𝑏𝑖𝑦𝑖 ≤ 𝑙 and 𝐵: Σ𝑎𝑗𝑥𝑗 ≤ 𝑤𝑗 ⋀ Σ 𝑏𝑗𝑦𝑗≤𝑧𝑖 – SarA Oct 3 '19 at 8:13
• You don't need the generalized version of $(a+b)\cdot x=a\cdot x+b\cdot x$ for the rest of the proof. In the last set of inequalities, take $\mathbf{a}=\mathbf{a}_1+\cdots+\mathbf{a}_n$ and $\mathbf{b}=\mathbf{a}_{n+1}$. – Chrystomath Oct 3 '19 at 12:14

I don't see how the linear combination part is relevant. $$A \geq k_1, B \geq k_2 \rightarrow A+B \geq k_1+k_2$$ regardless of where $$A$$ and $$B$$ come from. This can be seem by

$$A \geq k_2$$ $$A-k_1 \geq 0$$ $$B+(A-k_1)\geq B \geq k_2$$ $$B+A \geq k_1+k_2$$