Farkas Lemma proof

Question

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?

Answer 1

Presumably, to get show 2 implies 1 is false, $Ax = b$ implies $$ y^tAx = y^tb \\ $$ which is impossible if condition 2 is true and $x \ge 0$ since $y^tA \ge 0$ implies that the left hand is a conic combination of non-negative scalars and the rhs is strictly negative.

To show 1 implies 2 is false, we have $A^ty \ge 0$ implies $$x^tAy \ge 0$$ and if $Ax = b$ $$b^ty \ge 0$$ which contradicts the second part of condition 2.