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.