Bases and Basic Variables

Recall that a linear program in standard form has constraints of the form

$$A\mathbf{x} = \mathbf{b}, \qquad \mathbf{x} \geq \mathbf{0},$$

where $A$ is an $m \times n$ matrix with $m < n$ and full row rank. Since the system $A\mathbf{x} = \mathbf{b}$ has more unknowns than equations, it admits infinitely many solutions. The basic feasible solutions (the vertices of the feasible region) are obtained by selecting which $m$ variables to treat as "active" and forcing the remaining $n-m$ to be zero.

A basis is a set of $m$ column indices $\mathcal{B} = \{j_1, j_2, \ldots, j_m\} \subseteq \{1, 2, \ldots, n\}$ such that the corresponding columns of $A$ are linearly independent. The $m \times m$ matrix

$$B = \bigl[\,A_{j_1}\ \big|\ A_{j_2}\ \big|\ \cdots\ \big|\ A_{j_m}\,\bigr]$$

formed by these columns is called the basis matrix and is necessarily invertible.

The variables indexed by $\mathcal{B}$ are the basic variables, written $\mathbf{x}_B.$ The remaining $n-m$ variables are the non-basic variables, written $\mathbf{x}_N.$ The columns of $A$ not in the basis form the non-basic matrix $N.$

For instance, consider

$$A = \begin{bmatrix} 1 & 2 & 1 & 0 \\ 3 & 1 & 0 & 1 \end{bmatrix}.$$

Here $m = 2$ and $n = 4.$ Choosing the basis $\mathcal{B} = \{3, 4\},$ we obtain

$$B = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}, \qquad N = \begin{bmatrix} 1 & 2 \\ 3 & 1 \end{bmatrix},$$

with $\mathbf{x}_B = (x_3, x_4)$ and $\mathbf{x}_N = (x_1, x_2).$