Basis matrices
Basis Matrices
A basis matrix is an invertible square matrix made from linearly independent columns of the constraint matrix $A$.
Definition
If $A\in\mathbb{R}^{m\times n}$, a basis matrix is
\[B=[A_{B(1)}\ A_{B(2)}\ \cdots\ A_{B(m)}],\]where the selected columns are linearly independent. Therefore $B^{-1}$ exists.
Associated Variables
The variables corresponding to the columns of $B$ are basic variables. Their cost vector is $c_B$.
All other variables are nonbasic.
Feasible Basis
A basis is feasible if
\[B^{-1}b\ge 0.\]Then the associated basic solution is feasible.
Optimal Basis
For minimization, a feasible basis is optimal if
\[\bar c^T=c^T-c_B^TB^{-1}A\ge 0.\]Basis Update
A simplex pivot replaces one column of $B$ with an entering column $A_j$. The leaving column is chosen by the minimum ratio test.
Checklist
You should be able to form $B$, identify $x_B$ and $x_N$, compute $B^{-1}b$, and update one basis column during a pivot.
See Also
Exam checkpoint
For BFS questions, convert to standard form before checking the point. A candidate in original variables must be lifted with slack and surplus variables before testing basis columns.