Given the two systems below for an $m \times n$ matrix $A$:
(Sy 1): $Ax = 0, x \geq 0, x \neq 0$
(Sy 2): $A^Ty > 0 $
I seek to prove: (Sy 1) is consistent $\Leftrightarrow$ (Sy 2) is inconsistent.
I figured out how to prove Q $\Rightarrow $ P by proving the contrapositive ($\neg$P $\Rightarrow$ $\neg$ Q).
Sketch Proof for $\neg$P $\Rightarrow$ $\neg$ Q: Let (Sy 1) be inconsistent, then $0 \notin K = \{Ax: x \geq 0, x \neq 0\}$.
Separation Theorem 1 states: Let $X$ be a closed convex set in $\mathbb{R}^n$. If $p \notin X$, then for some $p \neq 0$ we have: $\langle v, p \rangle < \inf_{x \in X}\langle v, x \rangle$.
Since $K$ is a closed convex set, then by Separation Theorem 1, $\exists y$ such that \begin{eqnarray} \langle y, 0 \rangle = 0 & < & \inf_{x \geq 0, x \neq 0}\langle y, Ax \rangle \end{eqnarray}
Since $x \geq 0, x\neq 0$, then $\inf \langle y, Ax, \rangle = y^TAx = (A^Ty)^Tx > 0$. We must now verify that $A^Ty > 0 $.
If not true, then for some index $i$, $(A^Ty)_i \leq 0$. Pick $x \in \mathbb{R}^n$ to be the vector with coordinate $x_j = \lambda \delta_{ij}$. Then: \begin{eqnarray} \langle y, Ax\rangle = \sum_{j = 1}^{n}(A^Ty)_jx_j = \lambda(A^Ty)_{i} \end{eqnarray} As $\lambda \rightarrow \infty$, then $\lambda(A^Ty)_{i} \rightarrow -\infty$ if $(A^Ty)_i < 0$ or $\lambda(A^Ty)_{i} = 0 $ if $(A^Ty) = 0$.
Thus $\langle y, Ax \rangle \leq 0 = \langle y, 0\rangle$. This is a contradiction, thus $A^Ty > 0$. Q.E.D.
Now I seek to prove P $\Rightarrow $ Q. However, I am stuck. I tried to mimic something similar to my proof for $\neg$P $\Rightarrow$ $\neg$Q.
I let (Sy 1) be consistent, which meant $0 \notin S(A) = \{x: x\in \text{Ker}(A), x\geq 0, x \neq 0\}$. However, I did not seem to get very far. Any suggestions on how I should go about it?
Thank You for taking the time to read this. I appreciate any suggestions or feedback you give me. Take care and have a wonderful day.
Suppose for contradiction that $Q$ and not $P$. Ie, that both are consistent. Then there exists $x,y$ such that $A^t y > 0$ and $Ax = 0$, $x \neq 0$, $x > 0$. Then we have: $$\sum \text{ of products of non negatives (not all 0) } = \sum_i A^ty_i \cdot x_i=\langle A^t y, x \rangle = \langle y, Ax \rangle = 0$$ As $A^ty_i > 0$, and $x \neq 0 \implies \exists i$ such that $x_i \neq 0$. A contradiction. Hence $P \implies Q$.