2
$\begingroup$

Is there a version of Gordan's Theorem in which $Ax=0$ has been replaced by $Ax=b$? That is, I want a condition (possibly including conditions on $A$) for when $Ax=b$ has a solution $x \neq 0$, for $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}_+^m \setminus \{0\}$

Gordan's Theorem says that for all $A \in \mathbb{R}^{m \times n}$ we have $ \text{either} \quad \exists x \in \mathbb{R}_+^m\setminus{0} \centerdot Ax = 0, \quad\text{or}\quad \exists y\in\mathbb{R}^n\centerdot A^\top y > 0, $$

In particular, I cannot apply Farkas' Lemma to my problem because I want a condition with non-zero solutions.

$\endgroup$
4
  • $\begingroup$ What is the role of $b$ in all this? Maybe there is a misprint? $\endgroup$ May 20, 2011 at 14:53
  • $\begingroup$ I am conjecturing that he wants $Ax = b$ or $A^t y > b^t...$ $\endgroup$
    – Igor Rivin
    May 20, 2011 at 15:03
  • $\begingroup$ So $A$ is square and $m=n$? $\endgroup$ May 20, 2011 at 15:08
  • $\begingroup$ I'm looking for a version on Gordan's Theorem (stated) in which $Ax=0$ is replaced by $Ax=b$. $\endgroup$
    – bandini
    May 20, 2011 at 16:20

3 Answers 3

4
$\begingroup$

All these results follow from the duality theory of linear programming.

Let $e$ be the vector in $R^n$ with all entries 1.

$Ax = b$, $x \ge 0$, $x \ne 0$ is solvable iff the problem P:

maximize $e^T x$ subject to $Ax = b$, $x \ge 0$

is unbounded. This implies that the dual problem D:

minimize $b^T y$ subject to $A^T y \ge e$

is infeasible, which is equivalent to saying that $A^T y > 0$ is unsolvable. However, it is possible for both problems P and D to be infeasible, so you don't have "if and only if". What's special about $b=0$ is that in that case you know that the problem P is feasible, namely $x=0$ is a feasible solution.

$\endgroup$
2
$\begingroup$

This certainly won't work when $A=0$ and $b\neq 0$. In that case, $Ax=b$ has no solution and $A^{T}y>0$ has no solution.

Another counterexample to consider is $A=[1\;\; -1; -1\;\; 1]$ and $b=[2; 1]$. In this case, $Ax=b$ has no solution and $A^{T}y>0$ has no solution.

There's a related theorem of the alternative that is easy to prove: Either $Ax=b$, $x \geq 0$ has a solution (which would be nonzero if $A$ and $b$ are nonzero), or $A^{T}y \geq 0$, $b^{T}y<0$ has a solution, but not both. It's easy to prove this using LP duality.

$\endgroup$
0
$\begingroup$

What you want is Farkas' theorem, see http://eom.springer.de/m/m130240.htm

$\endgroup$
2
  • $\begingroup$ Not quite: Farkas' theorem allows for x=0. Gordan's theorem is a variant of Farkas with the added constraint that x is non-zero (the exact statement can be obtained by replacing $b$ with $0$ in the statement above). My question is whether Gordan's theorem (or something similar) remains true when we replace $0$ with $b$. $\endgroup$
    – bandini
    May 20, 2011 at 16:49
  • $\begingroup$ The link to eom.springer.de is broken, but the article can now be found at encyclopediaofmath.org/wiki/Motzkin_transposition_theorem. $\endgroup$ Jul 23, 2022 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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