Let $A$ be an $m × n$ matrix. Recall that Gordan’s lemma states that the system $$\{d : Ad < 0\}$$ is inconsistent if and only if the system $$λ ≥ 0 ∈ R ^m , λ \not= 0, A ^T λ = 0$$ is consistent.
- Show that the consistency of the second system is equivalent to the statement that $0 ∈ C$
- Use a separation argument to prove that $\{d : Ad < 0\} = ∅$ if and
only if $ 0 \notin C$, thereby proving Gordan’s lemma
Proof so far
$\Rightarrow$ Let $C$ be the convex hull of the rows of $A$, that is, $C = co(a_1 , . . . , a_m ) ⊆ E$,where $a_i$ is the ith row of $A$. Suppose the second system is consistent. We want to show that $0 \in C$. If $A^{T}=[a_1,a_2,...,a_m]$. Then $A^{T}\lambda=\sum_{i=1}^{m}a_i\lambda_i=0$. Therefore $0 \in C$