MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
up vote 4 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|cite|improve this answer

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|cite|improve this answer

What you want is Farkas' theorem, see

share|cite|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

Your Answer


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.