1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.