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.