A variation of Farkas' Lemma Let $A \in \mathbb{R}^{m\times n}$ be given. Show that exactly one system has a solution.

*

*$\quad A x \geq 0, \quad A x \neq \mathbf{0}$


*$\quad A^T y = 0, \quad y > \mathbf{0}$
 A: Here's my attempt, it based on the proof here:
Notice that $(2)$ is equivalent to saying that $0$ is in the interior of the conic combination of the rows of $A$. Let's call this set $Q$:
$$Q = \text{int} \,\text{cone}\{a_1, a_2,..., a_n\}$$
Assume that $(2)$ does not hold. There are three cases:

*

*$0$ can be strictly separated from $Q$ by a hyperplane.

*$0$ can be separated from $Q$ by a hyperplane, but not strictly.

*$0$ cannot be separated, and $0$ must be in $Q$.

Case 3 is not possible, since this is a contradiction.
Case 2 is more general than case 1, so we show that for case 2:
We can separate $0$ from the set $Q$ since it is convex and $0$ is a single point. So, there exists an $\alpha$ and a $\beta$ such that:
$$\alpha^T0 \leq \beta$$
$$\alpha^Tz \geq \beta$$
for all $z \in Q$. This shows that $\alpha^Tz \leq 0$ for all $z \in Q$. For each row of $A$, $a_i$, we can choose a $z$ arbitrarily close to it. So, this implies that $A\alpha \geq 0$ so setting $x$ to $\alpha$ we have that $Ax \geq 0$.
Now to show that $Ax \neq 0$. Since $0 \not \in Q$, we have that for at least a single element $z$ of $Q$: $0 < \alpha^Tz = \alpha^T \left(\sum_i a_i \right)$ so that $\alpha^T a_i > 0$ for at least one $a_i$.
Now assume that $(2)$ does hold, so that $0 \in Q$. Then there is no separating hyperplane, meaning that for each $\alpha, \beta$ such that $\beta>0$, there is some $z \in Q$ such that $\alpha^Tz \leq \beta$. Since $\beta$ is arbitrary, we can take it arbitrarily close to $0$ so that we can always find a $z \in Q$ such that $\alpha^Tz \leq 0$. All that remains to show is that this implies that $\alpha^Ta_i \leq0$ for some $i$.
By the definition of $z$:
$$z = \sum_i \lambda_i a_i$$
for some set of $\lambda_i >0$. Then:
$$\alpha^Tz = \sum_i \lambda_i \alpha^T a_i \leq 0$$
Since all the $\lambda_i > 0$ then at least one of the $\alpha^Ta_i$ must be negative. So we are done.
