Farkas lemma, proof of

We begin by showing that at least one of the systemshas a solution.

Suppose that system 2has no solution. Let $S$ be the cone in ${ℝ}^n$ generated by nonnegative linear combinations of the rows $a_1,\mathrm{\dots },a_m$ of $A$. The set $S$ is closed and convex. Since system 2 is unsolvable, the vector $c$ is not in $S$; therefore, there exist a scalar $\alpha$ and $n$-column vector $x$ such that the hyperplane $x^{T}v=\alpha$ separates $c$ from $S$ in ${ℝ}^n$. This hyperplane can be selected so that for any point $v\in S$,

$$x^T{c}^T>\alpha >x^T{v}^T.$$

Since $0\in S$, this implies that $\alpha >0$. Hence for any $w\ge 0$,

$$\alpha >x^T{(wA)}^T=wAx=\sum _{i=0}^m{w}_i{(Ax)}_i.$$

Each ${(Ax)}_i$ is nonpositive. Otherwise, by selecting $w$ with $w_i$ sufficiently large and all other $w_j=0$, we would get a contradiction.We have now shown that $x$ satisfies$Ax\le 0$ and $cx={(cx)}^T=x^T{c}^T>\alpha >0$, which means that $x$ is a solution of system 1. Thus at least one of the systems is solvable.

We claim that systems 1 and 2 are not simultaneously solvable. Supposethat $x$ is a solution of system 1 and $w$ is a solution of system 2. Thenfor each $i$, the inequality $w_i{(Ax)}_i\le 0$ holds, and so $w(Ax)\le 0$.However,

$$(wA)x=cx>0,$$

a contradiction. This completes the proof.