A short alternative to Gordan

The nicely named “theorem of the alternative” of Paul Gordan states the following

If V \subset \mathbb{R}^n is a linear subspace then either V contains a vector with positive coordinates or the orthogonal complement V^{\perp} contains a non-zero vector with non-negative coordinates.”

These options are mutually exclusive, hence the name of the theorem. Gordan gave a proof of this in 1873 which involved a very clever inductive argument. I just thought of a self contained very short proof of this theorem. In fact I will prove an equivalent statement

If v_1, \dotsc, v_n \in \mathbb{R}^k then either there is a vector v \in \mathbb{R}^k such that the inner product \langle v, v_j \rangle is positive for all j \in \{1, \dotsc, n\} or the convex hull C of v_1, \dotsc, v_n contains the origin.”

The equivalence can be seen as follows. Let M be the n \times k matrix with v_j as its rows. Then the columns of M span a subspace V \subset \mathbb{R}^n and this transforms the second statement into the first and vice versa.

Now let v \in C have minimal norm. If |v| = 0 then C contains the origin. If |v| > 0 and w is any point in the convex hull then the line segment from v to w lies in C and contains no point with smaller norm than v. So for all t \in (0,1] we have

\dfrac{|(1-t) v + t w|^2 - |v|^2}{2t} = \langle v, w \rangle - |v|^2+ \dfrac{t}{2}|w-v|^2 \geq 0.

This implies that \langle v, w \rangle \geq |v|^2 > 0 and in particular this holds for all w \in \{v_1, \dotsc, v_n \}. Done!

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s