<s>[INST] Gordan's lemma by using Farkas' lemma Gordan's lemma states: Let $A \in \mathbb{R}^{m \times n}$. Then exactly one of the following two systems has a solution:
\begin{align*}
  \text{I:}\quad &\exists x \in \mathbb{R}^n: Ax < 0, \\
  \text{II:}\quad &\exists y \geq 0, y \neq 0: A^Ty = 0.
\end{align*}
There are different proofs. But I want to prove it with the following hint:
Write system I as $Ax + \mathbf{1}s \leq 0$ with $s \in \mathbb{R}, s > 0, \mathbf{1} = (1,1,...,1 )^T \in \mathbb{R}^m$ and apply Farkas' lemma. Does anyone have an idea how to prove this with the hint?
 [/INST] \begin{align*}
 &\exists x \in \mathbb{R}^n: &&Ax < 0\\
 \Leftrightarrow\ &\exists x \in \mathbb{R}^n, s\in\mathbb{R}: &&Ax + s\mathbf{1} \leq 0, &&s > 0 \\
 \Leftrightarrow\ &\exists
 \begin{pmatrix}
  x\\
  s
 \end{pmatrix}
 \in\mathbb{R}^{n+1}: &&
 \begin{pmatrix}
  A &\mathbf{1}
 \end{pmatrix}
 \begin{pmatrix}
  x\\
  s
 \end{pmatrix}
 \leq 0,
 &&
 \begin{pmatrix}
  0 &1
 \end{pmatrix}
 \begin{pmatrix}
  x\\
  s
 \end{pmatrix}
 >0\\
 \Leftrightarrow\ &\exists
 \begin{pmatrix}
  x\\
  s
 \end{pmatrix}
 \in\mathbb{R}^{n+1}: &&
 \begin{pmatrix}
  -A &-\mathbf{1}
 \end{pmatrix}
 \begin{pmatrix}
  x\\
  s
 \end{pmatrix}
 \geq 0,
 &&
 \begin{pmatrix}
  0 &-1
 \end{pmatrix}
 \begin{pmatrix}
  x\\
  s
 \end{pmatrix}
 <0\\
 \overset{(F)}{\nLeftrightarrow}\ &\exists y'\in\mathbb{R}^{m}: &&
 \begin{pmatrix}
  -A^T \\-\mathbf{1}^T
 \end{pmatrix}
 y'=
 \begin{pmatrix}
  0\\
  -1
 \end{pmatrix},
 &&
 y'\geq 0\\
    \Leftrightarrow\ &\exists y'\in\mathbb{R}^{m}: &&
   \begin{pmatrix}
    A^T \\ \mathbf{1}^T
   \end{pmatrix}
   y'=
   \begin{pmatrix}
    0\\
    1
   \end{pmatrix},
   &&
   y'\geq 0\\
 \Leftrightarrow\ &\exists y'\in\mathbb{R}^{m}: &&
 A^Ty'=0,\ \mathbf{1}^Ty'=1,
 &&
 y'\geq 0\\
 \overset{(*)}{\Leftrightarrow}\ &\exists y\in\mathbb{R}^{m}: &&
 A^Ty=0,\ y\neq 0,
 &&
 y\geq 0
\end{align*}
$\overset{(F)}{\nLeftrightarrow}$: Farkas' Lemma
$\overset{(*)}{\Leftarrow}$: For $y\in\mathbb{R}^m$ with $A^Ty=0$, $y\neq 0$, $y\geq0$ we have $\mathbf{1}^Ty \gneq 0$. Choose $y':= \left(\mathbf{1}^Ty\right)^{-1}y\in\mathbb{R}^m$, then we have $A^Ty'=0$, $\mathbf{1}^Ty'=1$, $y'\geq 0$.
</s>