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 $


$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 $

  • $\begingroup$ 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. $\endgroup$ – Chrystomath Oct 1 '19 at 11:10
  • $\begingroup$ @Chrystomath I Edited and tried to make it clear. $\endgroup$ – 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$.

  • $\begingroup$ sorry I Edited my question and added the assumption that two inEqualities are **unsatisfiable**(This system does not have solution) $\endgroup$ – 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$.

  • $\begingroup$ Thanks for your reply. A typo in your reply is i.e., 𝑥<5; it should be 𝑥<-5 $\endgroup$ – SarA Oct 1 '19 at 11:42
  • $\begingroup$ how about the reverse implication? do you have counter-example for that A /\ B implies A + B $\endgroup$ – SarA Oct 1 '19 at 11:46
  • $\begingroup$ 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. $\endgroup$ – John Hughes Oct 1 '19 at 13:42
  • $\begingroup$ 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? $\endgroup$ – SarA Oct 1 '19 at 13:54
  • $\begingroup$ Yes, that's true. But it's not what your question asked about. $\endgroup$ – 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*}

  • $\begingroup$ Thanks for your thorough explanation. The proof would be similar for the generalised version? Last part of my question where 𝐴: Σ𝑎𝑖𝑥𝑖≤𝑘 ⋀ Σ𝑏𝑖𝑦𝑖 ≤ 𝑙 and 𝐵: Σ𝑎𝑗𝑥𝑗 ≤ 𝑤𝑗 ⋀ Σ 𝑏𝑗𝑦𝑗≤𝑧𝑖 $\endgroup$ – SarA Oct 3 '19 at 8:13
  • $\begingroup$ 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}$. $\endgroup$ – 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$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.