Gordan's Theorem with $Ax=b$

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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