I am trying to prove the Farkas Lemma using the Fourier-Motzkin elimination algorithm.
From Wikipedia:
Let A be an $m \times n$ matrix and $b$ an $m$-dimensional vector. Then, exactly one of the following two statements is true:
- There exists an $x \in \Bbb R^n$ such that $Ax = b$ and $x \ge 0$.
- There exists a $y \in \Bbb R^m$ such that $A^Ty \ge 0$ and $b^Ty < 0$.
The first direction is quite easy. I assume that there is a vector $y$ and I found a contradiction.
To the other direction I have used the fourier-motzkin elimination to reduce the number of variables. I assume that $Ax \le b$ and I do one step from the algorithm. I create a new system $A'x' \le b'$. I know that there exist a non-negative matrix $M$ that is a linear combination of the new system to the original. I have followed the direction of repeating the algorithm $n$ times to eliminate all the variables and create the system: $0 \le b''$.
Now in order this system to be infeasible it must be that: $b''<0$. So I can assume that exist vector $y''$ such that $y''A''=0$ and also $y''b''<0$ because $b'<0$ and $y\ge 0$. Now I can prove that also there is a vector $y$ for the original system. But the repetition of $n$ steps seems to me a bit arbitrary. If I just do one step and create the system $A'x'\le b'$ how I can use it is infeasible?
Best Answer
As you note, $1\rightarrow \bar 2$ is straightforward:
$$ \begin{align} Ax &= b \\ x'A' &= b' \\ x'A'y &= b'y \\ \end{align} $$
Since $x\geq0$, it is impossible to simultaneously have $A'y\geq 0$ and $b'y < 0$.
For $\bar 1\rightarrow 2$, first note that $Ax = b, x\geq 0$ (the system that is infeasible due to $\bar 1$) is equivalent to $Dx \leq d$, where we define
$$ D = \left( \begin{array}{c} A \\ -A \\ -I \end{array} \right), d = \left( \begin{array}{c} b \\ -b \\ 0 \end{array} \right). $$
We can now apply Fourier-Motzkin Elimination (FME) on the system $Dx\leq d$, removing all variables $1, 2, \ldots, n$ in order. Define $U^i$ to be the matrix used to remove variable $i$ from the system of equations; I will use $U^i\geq 0$ to indicate that each entry in $U^i$ is non-negative. From FME we have $U^nU^{n-1}\ldots U^1D = 0$. Defining $U = U^nU^{n-1}\ldots U^1$ we have $UD = 0$; note that from $U^1\geq 0, U^2\geq 0, \ldots, U^n\geq 0$ we also have $U\geq 0$.
Because $Dx\leq d$ is infeasible, there must be some row $u'\geq 0$ of $U$ such that $u'D = 0'$ and $u'd < 0$. Letting $p\geq 0$ be the first $m$ elements of $u$, $q\geq 0$ be the next $m$ elements of $u$, and $r\geq 0$ be the last $n$ elements of $u$, we have:
$$ \begin{align} u'D &= 0' \\ \left( \begin{array}{ccc} p' & q' & r' \end{array} \right) \left( \begin{array}{c} A \\ -A \\ -I \end{array} \right) &= 0' \\ (p-q)'A &= r' \\ (p-q)'A &\geq 0' \\ A'(p-q) &\geq 0 \end{align} $$
and
$$ \begin{align} u'd &< 0 \\ \left( \begin{array}{ccc} p' & q' & r' \end{array} \right) \left( \begin{array}{c} b \\ -b \\ 0 \end{array} \right) &< 0 \\ (p-q)'b &< 0 \\ b'(p-q) &< 0 \end{align} $$
By setting $y = p-q$, we have used FME to construct a vector $y\in\mathbb{R}^m$ such that $A'y \geq 0$ and $b'y < 0$.