# Is there an elementary proof of Farkas Lemma that does not use convex analysis or hyperplane separation theorem?

Is there any elementary proof of Farkas lemma which does not use convex analysis and hyperplane separation theorem?

If the Matrix $A$ is invertible, then there is obviously a unique vector $x$, such that $Ax=b$, is it hard to show that either $x$ is non-negative or there is a vector $y$ such that $y^tA \geq 0$ and $y^t b<0$?

• Good question! Most literature has a bad preference for brevity against algorithmicity. I remember finding such a proof but my writeup is fairly long and unreadable. On the other hand, I suspect that the proof in Schrijver's "Theory of linear and integer programming" is elementary. The idea is to perform induction on the dimension using Fourier-Motzkin elimination ( en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination ). Commented Sep 20, 2014 at 14:38
• Here is a short and self-contained proof. Apply this result to the set $\{v_1,\ldots,v_{n+1}\} \subset \mathbb{R}^n$ where $v_k$ is the $k$-th column of $A$ for $k\leq n$ and $v_{n+1}=-b$. Not sure if this fits your requirements (it uses a convexity argument).
– WimC
Commented Sep 20, 2014 at 16:47
• The auxiliary lemma that is proven there is itself some kind of a separation theorem :) If $0$ is not in the convex hull then there is a vector separating $C$ and $0$...
– daw
Commented Sep 20, 2014 at 19:25
• @WimC Does the link prove the lemma, as phrased by OP, immediately? Please see here: math.stackexchange.com/questions/2732541/… Commented Apr 11, 2018 at 17:11

For this special case, there is a very simple solution. Let $e_1,\ldots,e_n$ be the canonical basis of $\mathbb{R}^n$.
If $A$ is invertible then the unique soultion for $Ax=b$ is $A^{-1}b$.
If the vector $A^{-1}b$ has a negative entry then exists $e_i$ such that $e_i^tA^{-1}b<0$.
Now, since $A$ is invertible there exists $y$ such that $y^tA=e_i^t\geq 0$.
Finally, $y^tb=y^tAA^{-1}b=e_i^tA^{-1}b<0$.