What is the intuition behind Gordan's theorem?

Question

Gordan's theorem:

Exactly one of the following has a solution:

1. $y^TA > 0$ for some $y \in \mathbb R^m$
2. $Ax = 0$ ;$ x \geq 0$ for some non-zero $x \in \mathbb R^n$

I am not looking for the proof. I am looking for a way to wrap my head around the idea/intuition of this result.

Thanks.

Answer 1

Here's one way to look at it.

The first condition can be written as $ A^T y > 0$. Gordan's theorem says that either the range of $ A^T $ intersects the positive orthant, or the null space of $ A $ intersects the nonnegative orthant (at a point other than the origin).

Because the null space of $ A $ and the range of $ A^T$ are orthogonal complements of each other, this result seems geometrically plausible.

Answer 2

Consider the column vectors $a_i$ of $A$ and look at the theorem geometrically:

1. $y^TA>0$ translates into $y^Ta_i>0$ for every $i$, which means that the angle between $y$ and each $a_i$ is less than $\pi/2$.
2. $Ax=0$ with $x>0$ translates into $x_1a_1+\cdots x_na_n=0$ with $x_i\geq0$ (not all equal to $0$), which means that $0$ is in the convex cone formed by the $a_i$.

Now the theorem says: either we can find a vector which has less than $\pi/2$ angle with each $a_i$ or $0$ is in the convex cone of the $a_i$.

As a toy model we can think about the case of two vectors $u,v$ in a plane. If their angle $(u,v)$ is less than $\pi$, then we can always put a vector $y$ in the middle of the arc between them in such a way that the angles $(u,y)$ and $(v,y)$ are less than $\pi/2$. In this case the cone of $u,v$ does fill a "triangular" region wich falls short of being a half plane. Because of that, there is no way of achieving $0$ by means of a nonnegative (but nonzero) linear combination of $u$ and $v$, which allows to stretch the vectors but not to flip them. On the other hand, suppose that the angle $(u,v)$ is $\pi$. Then their cone is a half plane, $v=-u$, and the positive combination $1\cdot u+1\cdot v$ is $0$ (so $x=(1,1)$). In this case, if we put a vector $y$ in the middle of the arc between $u$ and $v$, we either get the angles $(u,y)<\pi/2, (v,y)>\pi/2$ (say), or $(u,y)=\pi/2=(v,y)$.

So, the intuition would be the following: imagine the cone of the $a_i$ as a flower blossoming. Then either the flower is not that much open, and you can place a stick inside its receptacle to help sustain all the petals with strings, with less than $90^\circ$ between the stick and each petal; or the flower is that much open that an insect could slide through one petal to another, going through the center of the receptacle, and without leaving the "inside" of the flower.

Answer 3

This is basically an application of the Hyperplane separation theorem. Take a look at the proof of Gordan's theorem here, where the hyperplane theorem is used.