Prove that for every matrix $A \in \mathbb{R}^{m \times n}$ exactly one of the following statements is true:
- $\exists x \in \mathbb{R}^n : Ax > 0$
- $\exists y \in \mathbb{R}^m : A^T y = 0 \wedge y \geq 0 \wedge y \neq 0$
I tried writing a linear program and its dual and then I tried to use the [b][u]complementary slackness property[/u][/b].
I wrote the linear program as: max $0^Tx$ $Ax \geq 0 $ $x \geq 0 $
Should I have defined a different linear program? How can I solve this problem?
You don't need complementary slackness, Farkas' Lemma for a system of linear inequalities does all the work.
Farkas' Lemma: For $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$, the system $Ax \le b$ has a solution if and only if there is no vector $u \in \mathbb{R}^m$ with $u \ge 0$, $u^tA = 0^t$ and $u^tb < 0$.
Now statement 2. is equivalent to: $\exists \varepsilon > 0$ (where $\varepsilon \in \mathbb{R}^m$) such that the system $A^Ty = 0, y\ge \varepsilon$ has a solution.
We can rewrite this as: $\exists \varepsilon>0$ s.t. the system $\begin{pmatrix} A^t\\-A^t\\-Id \end{pmatrix}y \le \begin{pmatrix} 0\\0\\-\varepsilon \end{pmatrix}$ has a solution.
By Farkas' Lemma, this is equivalent to: $\exists \varepsilon > 0$ s.t. the system $u\ge 0, u^t\begin{pmatrix} A^t\\-A^t \\-Id \end{pmatrix}^t= 0, u^t\begin{pmatrix} 0\\0\\-\varepsilon \end{pmatrix}<0$ does not have a solution, which is equivalent to:
$\exists \varepsilon > 0$ s.t. $\not \exists u_1,u_2,u_3 \ge 0: Au_1-Au_2-u_3 = 0, u_3^t\varepsilon \neq 0$.
This is equivalent to: $\not \exists u_1,u_2,u_3 \ge 0: A(u_1-u_2) = u_3, u_3 \neq 0$, which is equivalent to:
$\not \exists x: Ax \neq 0 \iff \not \exists x: Ax > 0$.
This completes the proof.