# Farkas lemma, proof of

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

Suppose that system 2
has no solution. Let $S$ be the cone in ${\mathbb{R}}^{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 ${\mathbb{R}}^{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. Suppose that $x$ is a solution of system 1 and $w$ is a solution of system 2. Then for 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.

Title | Farkas lemma, proof of |
---|---|

Canonical name | FarkasLemmaProofOf |

Date of creation | 2013-03-22 14:12:51 |

Last modified on | 2013-03-22 14:12:51 |

Owner | CWoo (3771) |

Last modified by | CWoo (3771) |

Numerical id | 13 |

Author | CWoo (3771) |

Entry type | Proof |

Classification | msc 15A39 |