# Prove that exactly one of the systems has a solution

Let $$A$$ be an $$m$$x$$n$$ matrix, $$B$$ $$l$$x$$n$$ matrix and $$c\in R^n$$. Prove that exactly one of the systems has a solution:

i)$$Ax\leq0,\:\: Bx=0,\:\: c^Tx>0,\:\: x\in R^n$$ ii)$$A^Tp+B^Tq=c,\:\:p\geq0,\:\:p\in R^m,\:\:q\in R^l$$

It's easy to prove that neither can be true at the same time by simply transposing and multiplying by x ii) and the other way around, but how do I show that exactly one must be true?

The hint which does not make much sense to me is to take $$q=r-s$$ where $$r,s\geq0$$.

• The hint allows you to only have nonnegative variables in problem (ii) and be exactly in the situation of Farkas' lemma. – Michal Adamaszek Dec 13 '19 at 12:50

Suppose $$(ii)$$ has a solution, then $$(i)$$ can't have a solution.

Now suppose $$(ii)$$ doesn't have a solution, then the following problem is not feasible:

$$\min 0$$ $$A^Tp + B^Tr-B^Ts = c$$ $$p \ge 0$$ $$r \ge 0$$ $$s \ge 0$$

Let's consider it's dual.

$$\max c^Tx$$ $$Ax \le 0$$ $$Bx \le 0$$ $$-Bx \le 0$$

Check that it is feasible and conclude that it is unbounded and that should help you to conclude that $$(i)$$ has a solution.