Bases and invertible matrices

Bases and Invertible Matrices

A basis is a set of vectors that can represent every vector in a space in a unique way.

An invertible matrix is a square matrix that can be reversed by multiplying with its inverse.

These ideas are central to simplex because every basic solution is built from a basis matrix.

Basis of a Vector Space

A set:

\[B=\{w_1,w_2,\ldots,w_n\}\]

is a basis of a vector space $V$ if every vector $v\in V$ can be written uniquely as:

\[v=\beta_1w_1+\beta_2w_2+\cdots+\beta_nw_n\]

The coefficients:

\[\beta_1,\beta_2,\ldots,\beta_n\]

are the coordinates of $v$ with respect to the basis $B$.

Two Requirements for a Basis

A basis must satisfy two conditions:

the vectors span the space
the vectors are linearly independent

So a basis is not just a collection that can build everything.

It must build everything without redundancy.

Canonical Basis

The canonical basis of $\mathbb{R}^n$ is:

\[\{e_1,e_2,\ldots,e_n\}\]

where:

\[e_1=(1,0,\ldots,0)\] \[e_2=(0,1,\ldots,0)\] \[\ldots\] \[e_n=(0,0,\ldots,1)\]

Every vector:

\[v=(v_1,v_2,\ldots,v_n)\]

can be written as:

\[v=v_1e_1+v_2e_2+\cdots+v_ne_n\]

Basis Matrix

A basis matrix is a square matrix formed by placing basis vectors as columns.

If:

\[B=\{w_1,w_2,\ldots,w_m\}\]

then the associated matrix is:

\[B=[w_1 \ w_2 \ \cdots \ w_m]\]

In linear programming, a basis matrix is formed by selecting columns from the constraint matrix $A$.

Basis Matrix in LP

Consider the standard-form LP:

\[\min c^Tx\]

subject to:

\[Ax=b\] \[x\ge 0\]

where:

\[A\in\mathbb{R}^{m\times n}\]

A basis matrix is formed by selecting $m$ linearly independent columns of $A$:

\[B = [A_{B(1)} \ A_{B(2)} \ \cdots \ A_{B(m)}]\]

Because $B$ has $m$ independent columns, it is an $m\times m$ invertible matrix.

Basic Variables

The variables corresponding to the selected columns are called basic variables.

They are written:

\[x_B\]

The remaining variables are called nonbasic variables.

In a basic solution, nonbasic variables are set to zero.

Then the basic variables are found from:

\[Bx_B=b\]

so:

\[x_B=B^{-1}b\]

Invertible Matrix

A square matrix $B$ is invertible if there exists a matrix $B^{-1}$ such that:

\[B^{-1}B=I\]

and:

\[BB^{-1}=I\]

where $I$ is the identity matrix.

Identity Matrix

The identity matrix is:

\[I = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix}\]

It satisfies:

\[Ix=x\]

for every compatible vector $x$.

Solving with an Inverse

If:

\[Bx=b\]

and $B$ is invertible, then:

\[x=B^{-1}b\]

This is why invertibility matters.

Without $B^{-1}$, the formula does not work.

Example

Let:

\[B= \begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix}\]

and:

\[b= \begin{bmatrix} 10 \\ 16 \end{bmatrix}\]

The system is:

\[Bx=b\]

or:

\[\begin{cases} x_1+2x_2=10 \\ 2x_1+x_2=16 \end{cases}\]

Solving gives:

\[x_1=\frac{22}{3}, \qquad x_2=\frac{4}{3}\]

So:

\[x=B^{-1}b= \begin{bmatrix} 22/3 \\ 4/3 \end{bmatrix}\]

Invertibility and Linear Independence

For a square matrix $B$, the following are equivalent:

\[B \text{ is invertible}\] \[\operatorname{rank}(B)=m\]

the columns of $B$ are linearly independent.

So, in LP, a valid basis matrix must have independent columns.

Basic Solution

Given:

\[Ax=b\]

choose a basis matrix $B$.

Set all nonbasic variables to zero.

Solve:

\[x_B=B^{-1}b\]

The resulting vector $x$ is called a basic solution.

Basic Feasible Solution

A basic solution is a basic feasible solution if:

\[x_B=B^{-1}b\ge 0\]

and all nonbasic variables are already zero.

So feasibility requires every component of the resulting vector to be nonnegative.

Degenerate Basic Feasible Solution

A basic feasible solution is degenerate if at least one basic variable is zero.

That is:

\[x_B\ge 0\]

but some component of $x_B$ equals zero.

Degeneracy matters in simplex because it can cause special pivoting behavior.

Basis in Simplex

The simplex method moves from one basis to another.

At each iteration:

choose an entering nonbasic variable
choose a leaving basic variable
replace one column of $B$
compute a new basic feasible solution

So simplex is really an algorithm that updates basis matrices.

Why We Need Bases

A linear program can have infinitely many feasible points.

The key theorem behind simplex says that if an LP has an optimal solution, then one can be found at a vertex of the feasible region.

Vertices correspond to basic feasible solutions.

Basic feasible solutions are computed using basis matrices.

So:

\[\text{basis} \rightarrow \text{basic solution} \rightarrow \text{vertex candidate}\]

Common Mistake

Do not choose arbitrary columns of $A$ and assume they form a basis.

They must be linearly independent.

If the selected columns are dependent, $B^{-1}$ does not exist.

Checklist

You understand bases and invertible matrices if you can:

define a basis
explain uniqueness of coordinates
write the canonical basis
identify a basis matrix
explain why a basis matrix must be invertible
compute basic variables using $x_B=B^{-1}b$
distinguish basic solution from basic feasible solution
explain the role of a basis in simplex

Exam checkpoint

Use this topic only as much as needed to support LP algebra: matrices, rank, bases, linear systems, half-spaces, and hyperplanes. Connect every computation back to $Ax=b$, basis matrices, and feasible regions.