Farkas' Lemma is given as follows
Let $\pmb A\in\mathbb R^{m\times n}$ and $\pmb b\in\mathbb R^m$. Then exactly one of the following two assertions is true:
1.1. There exists an $\pmb x\in\mathbb R^n$ such that $\pmb A\pmb x=\pmb b$ and $\pmb x\ge 0$
1.2. There exists a $\pmb y\in\mathbb R^m$ such that $\pmb A^\top\pmb y\ge \pmb0$ and $\pmb b^\top\pmb y<0$
A variant of Farkas' Lemma is given as follows
Let $\pmb A\in\mathbb R^{m\times n}$ and $\pmb b\in\mathbb R^m$. Then exactly one of the following two assertions is true:
2.1. There exists an $\pmb x\in\mathbb R^n$ such that $\pmb A\pmb x\le\pmb b$
2.2. There exists a $\pmb y\ge 0$ such that $\pmb A^\top\pmb y= \pmb0$ and $\pmb b^\top\pmb y=-1$
I'm confused about how to get $\pmb A^\top\pmb y=\pmb 0$ in 2.2.
I've read several proofs online, but none of them can help me understand it. For example,
this proof constructs $\pmb A'=
\begin{bmatrix}\pmb A&-\pmb A&\pmb I\end{bmatrix}$ and $\pmb x'=\begin{bmatrix}\pmb x^+\\\pmb x^-\\\pmb s\end{bmatrix}\ge \pmb 0$. If there is no $\pmb x$ such that $\pmb A'\pmb x'\le \pmb b$, following Farkas' Lemma, there exists $\pmb y\ge 0$ such that $\pmb y^\top\pmb A'\ge\pmb 0$ and $\pmb y^\top\pmb b<0$. Then it derives $\pmb y^\top\pmb A=\pmb 0$ because $\pmb y^\top\pmb A\ge \pmb 0$ and $-\pmb y^\top\pmb A\ge\pmb 0$. But from $\pmb y^\top\pmb A'\ge \pmb 0$, I can only get $\pmb y^\top\pmb A – \pmb y^\top\pmb A + \pmb y^\top\ge \pmb 0$. How can I get "$\pmb y^\top\pmb A\ge \pmb 0$ and $-\pmb y^\top\pmb A\ge\pmb 0$"?
Best Answer
If there is no $\pmb x \in \mathbb{R}^n$ such that $\pmb A\pmb x \leq \pmb b$, then there is no $\pmb x \geq \pmb 0$ such that $\pmb A'\pmb x' = \pmb b$. Following Farkas' Lemma, there exists $\pmb y\in\mathbb R^m$ such that $\pmb A'^\top \pmb y \ge\pmb 0$ (1) and $\pmb y^\top\pmb b< 0$ (2). Note that (1) is equivalent to $\pmb A^\top \pmb y \geq \pmb 0$ (3), $-\pmb A^\top \pmb y \geq \pmb 0$ (4) and $\pmb y \geq \pmb 0$ (5). Combining (3) and (4) gives $\pmb A^\top \pmb y = \pmb 0$. From (2) you get $\pmb y^\top\pmb b = -1$ because you can always rescale $\pmb y$.