Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

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

3 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
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$. –  bandini May 20 '11 at 16:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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