1
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .