# Proof of Modified Farkas lemma: $y\ge0,A^Ty=0,y^Tb<0$ or $Ax\le b$ has a solution

The proof of Farka's lemma is known.

An important corollary of Farkas lemma is stated as
Modified Farkas Lemma. Let $$A$$ be an $$m\times n$$ matrix with values in $$R$$ and $$b\in R^m$$. Then exactly one of the following holds

1. $$\exists x\in R^n$$ such that $$Ax\le b$$
2. $$\exists y\in R^m,y\ge0$$ such that $$A^Ty=0,y^Tb<0$$.

Attempt. Verification that both do not hold together is trivial. Suppose 2 does not hold. Then, $$\not\exists y\ge0,y\in R^m$$ such that $$A^Ty=0,y^Tb<0$$. We need to show that 1 necessarily holds.

Construct $$\hat A_{(n+1)\times m}=\begin{pmatrix}A^T\\b^T\end{pmatrix},\hat b_{(n+1)\times 1}=\begin{pmatrix}0\\\vdots\\0\\-1\end{pmatrix}$$. Applying Farkas lemma on this, we get

• $$\exists z\ge 0,z\in R^m$$ such that $$\hat Az=\hat b$$, or
• $$\exists w\in R^{n+1}$$ such that $$\hat A^T w\ge0,w^T\hat b<0$$

The first implies that $$\exists z\in R^m,z\ge0$$ such that $$A^Tz=0,b^Tz=-1<0$$ which is a contradiction since 2 does not hold. Hence, $$\exists w\in R^{n+1}$$ such that $$\hat A^T w\ge0,w^T\hat b<0$$.

How do I proceed from here?

We have $$\exists w\in R^{n+1}$$ such that $$\hat A^Tw\ge\boldsymbol{0}$$ and $$w^T\hat b<0$$. Since, $$w\in R^{n+1}$$ we write it in the form $$w=\pmatrix{w_0\\\lambda},\quad w_0\in R^n,\lambda\in R.$$ We get $$\pmatrix{A,b}\pmatrix{w_0\\\lambda}\ge0\Rightarrow Aw_0+\lambda b\ge0\quad\text{and}\quad\pmatrix{w_0,\lambda}\pmatrix{\boldsymbol{0}\\-1}<0\Rightarrow\lambda>0\\\Rightarrow A\left(\frac{-1}{\lambda}w_0\right)\le b$$
Taking $$x=\frac{-1}{\lambda}w_0$$, we get that $$\exists x\in R^{n}$$ such that $$Ax\le b$$.