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

Question

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.

Answer 1

$\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$

Answer 2

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

Answer 3

Here is a proof of Stiemke's Lemma using Farkas lemma.

---

Stiemke's Lemma. Let $A$ be an $m\times n$ real matrix. Then one and only one of the following two statements holds :

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

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

---

Proof. If (1) and (2) both holds, then $p^\top Ax=0$ and $p^\top Ax>0$, contradiction. Suppose (2) does not hold. Then $$A^\top p\geq 0, \quad 1^\top A^\top p=1 \quad \quad (3)$$

has no solutions $p\in\mathbb R^m$. Let

$$B=\begin{bmatrix} A^\top & -A^\top & -I_n \\ 1^\top A^\top & -1^\top A^\top & 0_{1\times n} \end{bmatrix}$$

be $(n+ 1)\times (2m+n)$. Then

$$Bz=\begin{bmatrix} 0_{n\times 1} \\ 1 \end{bmatrix}$$

has no solutions $z=\begin{bmatrix} z_1 \\ z_2 \\ z_3 \end{bmatrix}\in\mathbb R ^{2m+n}$ with $z\geq 0$, for otherwise

$$A^\top (z_1-z_2)=z_3\geq 0, \quad \quad 1^\top A^\top (z_1-z_2)=1 $$ contradicting $(3)$ with $p=z_1-z_2$. By Farka's lemma applied to $B$ and $\begin{bmatrix} 0_{n\times 1} \\ 1 \end{bmatrix}$, there exists $x=\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}\in\mathbb{R}^{n+1}$ such that $B^\top x\geq 0$ and $x^\top \begin{bmatrix} 0_{n\times 1} \\ 1 \end{bmatrix} =x_2<0$. Replacing $x$ by $-x$ we get $B^\top x\leq 0$ and $x_2>0$. Replacing $x$ by $\frac{1}{x_2}x$ we get $B^\top x\leq 0$ and $x_2=1$. Then

$$B^\top x=\begin{bmatrix} Ax_1 +A1 \\ -Ax_1+A1 \\ -x_1 \end{bmatrix}\leq 0$$

which implies $A(x_1+1)=0$ and $x_1\geq 0$. Hence $(1)$ holds with $x:=x_1+1$.