Basic feasible solution

For $Ax=b$, $x\ge 0$, a feasible vector $x$ is basic when the columns $A_i$ indexed by its positive coordinates are linearly independent. Equivalently, enlarge those columns to a basis, set every nonbasic coordinate to zero, and solve the resulting square system.

A basic feasible solution is degenerate when one or more of its basic variables is zero. A simplex algorithm pivot may then change the basis without moving the feasible point or changing the objective. Assignment networks force many zero-flow basic tree arcs.

For a full-row-rank system $Ax=b$ with $m$ rows, choose $m$ linearly independent columns, set all remaining variables to zero, and solve the resulting square system. The resulting vector is a basic solution; it is feasible when it also satisfies the required nonnegativity constraints.

If a linear program has an optimal solution, it has an optimal basic feasible solution. Choose an optimum with minimal positive support. A dependence among its active columns gives a feasible two-sided perturbation; optimality makes its objective slope zero, and moving until one coordinate vanishes contradicts minimality.