$\mathbf {Stiemke's \,\,Lemma.}$ Let $A$ be an $m\times n$ real matrix. Then one and only one of the following two statements holds:
(1) $A{\mathbf x}=0$ has a solution ${\mathbf x}\gg 0$.
(2) There exists ${\mathbf y}\in\mathbb R^m$ such that $A^T{\mathbf y}>0$.
$\mathbf {Proof.}$ (The proof mimics that of Gordan's theorem given here.) Let us denote the inner products (dot products) ${\mathbf x}\cdot{\mathbf y}(={\mathbf x}^T{\mathbf y})$ in $\mathbb R^n$ by $\langle {\mathbf x,\mathbf y\rangle}$. Denote by ${\rm Ker}\,A:=\{{\mathbf x}:A{\mathbf x}=0\}$ and ${\rm Ran}\,A:=\{A{\mathbf x}:{\mathbf x}\in \mathbb R^n\}\subset \mathbb R^m$ the kernel space and range space of $A$, respectively. Notice that ${\rm Ker}\,A=({\rm Ran}\,A^T)^\perp$, or equivalently, $({\rm Ker}\,A)^\perp={\rm Ran}\,A^T$.
If (1) and (2) both hold, then
$$
0<\langle {\mathbf x},A^T{\mathbf y}\rangle=\langle A{\mathbf x},{\mathbf y}\rangle=0,
$$
a contradiction. So, suppose (1) does not hold. Define the following two convex substes of $\mathbb R^n$:
$$
S_1:={\rm Ker}\,A,\quad S_2:=\{{\mathbf x}:{\mathbf x}\gg 0\}.
$$
By the hypothesis, $S_1\cap S_2=\emptyset$. Therefore, there is a hyperplane that separates $S_1$ and $S_2$, i.e., there is a nonzero vector ${\mathbf z}\in \mathbb R^n$ (orthogonal to the plane) such that $\langle {\mathbf z},{\mathbf x}\rangle \le 0$ for all ${\mathbf x}\in {\rm Ker}\,A$ and $\langle {\mathbf z},{\mathbf w}\rangle \ge 0$ for all ${\mathbf w}\in S_2$. Since ${\rm Ker}\,A$ is a linear space, we have in fact $\langle {\mathbf z}, {\mathbf x}\rangle = 0$ for all ${\mathbf x}\in {\rm Ker}\,A$. This means that ${\mathbf z}\in ({\rm Ker}\,A)^\perp$. By the preceding observation, it means that ${\mathbf z}\in {\rm Ran}\,A^T$, or there is a vector ${\mathbf y}\in \mathbb R^m$ such that ${\mathbf z}=A^T{\mathbf y}$. From the condition $\langle {\mathbf z},{\mathbf w}\rangle \ge 0$ for all ${\mathbf w}\in S_2$ we see that ${\mathbf z}=A^T{\mathbf y}>0$. That is, (2) holds. The proof is completed. $\square$
Best Answer
For this special case, there is a very simple solution. Let $e_1,\ldots,e_n$ be the canonical basis of $\mathbb{R}^n$.
If $A$ is invertible then the unique soultion for $Ax=b$ is $A^{-1}b$.
If the vector $A^{-1}b$ has a negative entry then exists $e_i$ such that $e_i^tA^{-1}b<0$.
Now, since $A$ is invertible there exists $y$ such that $y^tA=e_i^t\geq 0$.
Finally, $y^tb=y^tAA^{-1}b=e_i^tA^{-1}b<0$.