# Intuitive self-contained proof of Farkas' Lemma

I've been studying the proof of Farkas' Lemma, and given my rather fuzzy memory of Linear Algebra, am having some trouble with it. One version of Farkas' lemma states:

For any convex cone generated by vectors $$a_1, a_2, ...a_m \in \mathbb R^n, C=\{x: x=\sum_{i=1}^m \alpha_ia_i,\alpha_i \geq 0\}$$, any point $$y \in \mathbb R^n$$ in the space

1. either belongs to the cone OR

2. there is a halfspace through the origin that contains the cone and does not contain $$y$$, i.e. there is a vector $$w \in \mathbb R^n$$ such that $$w^Ta_i \geq 0$$ for all $$1 \leq i \leq m$$ and $$w^Ty < 0$$.

I think I understand the first part of the proof -- namely that if (1) if true, then (2) cannot be true, because if both were true, then it means all of the following is true: $$Ax=y$$, $$w^TAx < 0$$, and $$w^TAx \geq 0$$ the latter of which is a contradiction. Please let me know if I've made any errors here.

The second part of the proof -- namely, if (1) is false then (2) must be true -- is where I'm having issues. I've read a few proofs, but most of them either appeal to a different theorem (i.e. separation lemma) or have explanations / notations that are too confusing. Is it possible to come up with a nice, self-contained, intuitive proof for Farkas' Lemma?

• I cannot remember any reeealy easy and intuitive proof of that part. Maybe one proof will be of interest to you -- Matousek and Gartner, in their book, "Understanding and Using Linear Programming", include a couple of demonstrations, including one using Fourier-Motzkin elimination, which is quite straightforward. – Jay Apr 7 '16 at 16:35