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:

  1. There exists an $x \in \Bbb R^n$ such that $Ax = b$ and $x \ge 0$.
  2. 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?


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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.