Basic Solutions

A basic solution is obtained by selecting a basis, setting nonbasic variables to zero, and solving the remaining square system.

Setup

Consider

where $A\in\mathbb{R}^{m\times n}$ and $\operatorname{rank}(A)=m$.

Choose a Basis

Choose $m$ linearly independent columns of $A$:

The corresponding variables are basic variables $x_B$. The others are nonbasic variables $x_N$.

Construct the Basic Solution

Set

and solve

Thus

Feasibility Is Separate

A basic solution satisfies $Ax=b$, but it may not satisfy $x\ge 0$.

If any component of $x_B$ is negative, it is not feasible.

At Most m Nonzero Variables

A basic solution has all nonbasic variables equal to zero, so it has at most $m$ nonzero variables.

Checklist

You should be able to choose a valid basis, compute $B^{-1}b$, build the full vector $x$, and test its signs.

See Also

• Basis Matrices
• Basic Feasible Solutions
• Canonical Form

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.