# Version of Farkas Lemma

In lecture we had this version of Farkas lemma:

Let $$A\in \mathbb{R}^{m\times n}$$, $$b\in \mathbb{R}^n$$. The system $$Ax\leq b$$ has no solution $$\Leftrightarrow$$ $$\exists y\in \mathbb{R}^m_+$$ so that $$A^ty=0 \quad \text{and} \quad b^ty >0$$

I tried understanding that with an example and came up with $$A= \begin{pmatrix} 1&-1 \\ -1&1\end{pmatrix}$$, $$b= \begin{pmatrix} -1\\-1\end{pmatrix}$$. That system obviously has no solution for $$x$$ but it seems like I can't find a fitting $$y$$ so that both two conditions are true.

What am I missing? Or is the lecture version of Farkas lemma incorrect?

• Should that be $A^ty = 0$ and $b^t y \color{red}< 0$ instead? This Wikipedia page indicates that that is the case. Commented Sep 22, 2021 at 14:18
• @BenGrossmann Yes! It's probably a typo then. Commented Sep 22, 2021 at 14:23
• – glS
Commented Jul 11, 2022 at 10:11

As is noted in the comments, it seems that the culprit is a typo. The correct version of Farkas' lemma is that $$Ax \leq 0$$ fails to have a solution iff there exists a $$y \in \Bbb R_{+}^m$$ such that $$A^ty = 0$$ and $$b^ty \color{red} < 0$$.