Basis

Let be an matrix.
A basis of is a set such that

• is invertible
  where is the submatrix of
  formed by taking -th column of when .

Let be a vector with Support
We say that has basis if

Lemma

Let be a Basis of and let
Then there exists a unique Basic Solution with basis to:

Proof

Define by and for .
This is a Basic Solution and unique by construction.

Lemma

Suppose has rank (i.e. all its rows are Linearly Independent)
Then for any Basic Solution , there exists a basis.

Proof

Suppose Basic Solution has Support .
Columns of are Linearly Independent by definition, so
Let be the space spanned by the columns of .
It has dimension (due to rank of being )
If the columns of span , then and thus
so is a Basis of

If the columns of do not span
then pick a column of not in with index
and form the set
Repeat this process until we arrive at a Basis.