# Stiemke’s Theorem from Farkas' Lemma or Gordan’s theorem

Let me introduce some notations first. For any two points $$x=\left(x_{i}\right)$$ and $$y=\left(y_{i}\right)$$ in $$\mathbb{R}^{n}$$, we define

• (1) $$x\geq y$$ if $$x_{i}\geq y_{i}$$ for $$i=1,2,\cdots,n$$

• (2) $$x>y$$ if $$x\geq y$$ and $$x\ne y$$

• (3) $$x\gg y$$ if $$x_{i}>y_{i}$$ for $$i=1,2,\cdots,n$$

Now I want to prove Stiemke's Lemma: Let A be an $$m\times n$$ real matrix, $$x\in\mathbb{R}^{n}$$. Then the system of linear equations $$Ax=0$$ has a positive solution $$x\gg0$$ if and only if the system of linear inequalities $$A^{\top}p>0$$ has no solution $$p\in\mathbb{R}^{m}$$.

Another equivalent statement is that: Let $$A$$ be an $$m\times n$$ real matrix. Then one and only one of the following two statements is correct :

• (1) $$Ax=0$$ has a solution $$x\gg0$$.

• (2) There exists $$p\in\mathbb{R}^{m}$$ such that $$A^{\top}p>0$$.

Now I want to prove Stiemke's Lemma using either Farkas–Minkowski' Lemma or Gordan’s theorem or Hyperplane separating Theorem. (This is what I have got).

(Weak Hyperplane Separation Theorem) Let $$A$$ and $$B$$ be nonempty and convex subsets of $$\mathbb{R}^{n}$$. If $$A$$ and $$B$$ are disjoint, then $$A$$ and $$B$$ can be separated by a hyperplane.

(Strong Hyperplane Separation Theorem) Let $$A$$ and $$B$$ be disjoint nonempty and convex subsets of $$\mathbb{R}^{n}$$. If $$A$$ is closed and $$B$$ is compact, then $$A$$ and $$B$$ can be strictly separated by a hyperplane.

(Farkas–Minkowski'Lemma) Let $$A$$ be an $$m\times n$$ real matrix, $$b\in\mathbb{R}^{m}, x\in\mathbb{R}^{n}$$. Then one and only one of the following two statements is correct :

• (1) $$Ax=b$$ has a nonnegative solution $$x\geq0$$

• (2) There exists $$p\in\mathbb{R}^{m}$$ such that $$p^{\top}A\geq0$$ and $$p^{\top}b<0$$.

(Gordan’s theorem) Let $$A$$ be an $$m\times n$$ real matrix. Then one and only one of the following two statements is correct :

• (1) $$Ax=0$$ has a solution $$x>0$$ with $$x\in\mathbb{R}^{n}$$.

• (2) There exists $$p\in\mathbb{R}^{m}$$ such that $$A^{\top}p\gg0$$.

How can I prove Stiemke's Lemma from the previous four lemmas? Here states that we can construct the proof readily from that of Gordan’s theorem. But I can not see how to do it? I think we need to use the Strong Hyperplane Separation, but the proof in Gordan’s theorem only needs weak Hyperplane Separation. Thanks in advance.

Your Weak Hyperplane Separation Theorem $$\Rightarrow$$ Theorem 2 $$\Rightarrow$$ Theorem 13 (Stiemke) (see this paper).