Basic Feasible Solution

Let be a matrix and
Let be a Basic Solution to .
We say that is a basic feasible solution if
i.e. for all where is the Support of

Theorem

Let be the convex set:

where has rank .
A point is an Extreme Point of
if and only if
is a Basic Feasible Solution.

Proof

Let be a BFS with Support and Basis .
Suppose:

where and
i.e. and
Let and be Supports of and respectively.
For all we have and thus
so
and thus both and are Basic Solutions with Basis .
They are thus unique and
so is an Extreme Point of .

Suppose is an Extreme Point of .
Let be the Support of .
Suppose for some vector with support
Then we can find small enough such that:

(we can do this as by definition)
But now we have
so by definition of Extreme Point
and thus .
Hence we have proven that the columns of are Linearly Independent
so is a Basic Solution and
so is a BFS.