6
$\begingroup$

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

What about special case below:

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

$\endgroup$
4
  • $\begingroup$ 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 ). $\endgroup$ Commented Sep 20, 2014 at 14:38
  • $\begingroup$ 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). $\endgroup$
    – WimC
    Commented Sep 20, 2014 at 16:47
  • $\begingroup$ 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$... $\endgroup$
    – daw
    Commented Sep 20, 2014 at 19:25
  • $\begingroup$ @WimC Does the link prove the lemma, as phrased by OP, immediately? Please see here: math.stackexchange.com/questions/2732541/… $\endgroup$
    – Pachirisu
    Commented Apr 11, 2018 at 17:11

1 Answer 1

2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .