Basic Solutions

Choosing $m$ independent columns of $A$ and solving for them, with every other variable set to zero, produces a basic solution. It is a construction, and it can be carried out correctly and still produce a point outside the feasible region: nothing in the procedure tests the sign restrictions. Feasibility is a separate question asked afterwards.

Definition

Let $A$ be $m \times n$ with rank $m$ , and consider $A x = b$ with $x \geq 0$ .

A basis is a set $B = {B (1), \dots, B (m)}$ of $m$ linearly independent columns of $A$ . Write $A_{B}$ for the $m \times m$ matrix of those columns; independence makes $A_{B}$ invertible.

The corresponding basic solution is obtained by setting every nonbasic variable to zero and solving for the rest:

\begin{aligned} x_{B} & = A_{B}^{- 1} b, \\ x_{j} & = 0 for j \notin B . \end{aligned}

This point satisfies $A x = b$ by construction, since $A x = A_{B} x_{B} = b$ . It is uniquely determined by the choice of $B$ .

What the construction does not do. Nothing above involves the restriction $x \geq 0$ . The components of $A_{B}^{- 1} b$ may be negative, and when any of them is, the basic solution lies outside the feasible region. A basic solution satisfying $x \geq 0$ is called a basic feasible solution; the sign test is what separates the two, and it is a step of its own.

How many there are. Choosing $m$ columns from $n$ can be done in $(\binom{n}{m})$ ways, but not every choice gives a basis. The columns may be dependent, in which case $A_{B}$ is singular and determines no basic solution at all.

Formal statement

For $B$ with $A_{B}$ invertible: $x_{B} = A_{B}^{- 1} b$ , $x_{N} = 0$ . Basic solution: any such $x$ . Basic feasible solution: such an $x$ with $x_{B} \geq 0$ .

Assumptions and scope

The construction requires $A$ to have full row rank. Otherwise no set of $m$ independent columns exists and no basis can be formed; redundant equality constraints must be removed first.
A basic solution satisfies $A x = b$ always, and $x \geq 0$ only sometimes. The second is a test performed on the result, never a consequence of the construction.
Not every choice of $m$ columns is a basis. Dependent columns make $A_{B}$ singular, and then there is no basic solution for that choice rather than an infeasible one.
The basic solution is unique given the basis. Different bases may nonetheless give the same point, which is degeneracy and is taken up separately.
Nonbasic variables are set to zero by definition, not derived. This is the decision that makes the system square, and it is why a basic solution always has at least $n - m$ zero components.

Worked material

Example

Three bases for one system

Take

\begin{aligned} x_{1} + x_{2} + x_{3} & = 4, \\ x_{1} + x_{4} & = 2, \\ x_{1}, x_{2}, x_{3}, x_{4} & \geq 0, \end{aligned}

so $m = 2$ , $n = 4$ , and the columns are $A_{1} = (1, 1)^{T}$ , $A_{2} = (1, 0)^{T}$ , $A_{3} = (1, 0)^{T}$ , $A_{4} = (0, 1)^{T}$ .

Basis ${2, 4}$ . $A_{B} = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})$ , independent. Solving gives $x_{2} = 4$ , $x_{4} = 2$ . The point is $(0, 4, 0, 2)$ . Every component nonnegative: a basic feasible solution.

Basis ${1, 2}$ . $A_{B} = (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix})$ , independent. The second row gives $x_{1} = 2$ ; the first then gives $2 + x_{2} = 4$ , so $x_{2} = 2$ . The point is $(2, 2, 0, 0)$ . Nonnegative: a basic feasible solution.

The set ${2, 3}$ . $A_{2} = A_{3} = (1, 0)^{T}$ are identical, hence dependent. $A_{B}$ is singular. This is not a basis, and there is no basic solution for it. The construction cannot begin.

Three different outcomes from the same system, and only the third is a failure of the construction rather than a result of it.

Non-example

What is not a basic solution

Not a basic solution: a feasible point with too many positive components. In the four-variable example, $(1, 2, 1, 1)$ satisfies both equations and is nonnegative, but all four components are positive. A basic solution has at least $n - m = 2$ zeros. This point is feasible and interior to a segment of the region, not a vertex.

Not a basic solution: the result of a dependent column set. Choosing ${2, 3}$ above gives a singular $A_{B}$ . There is no point to report. This is not an infeasible basic solution; it is the absence of one, and the distinction matters when counting how many bases a system has.

Not a basic feasible solution: a basic solution with a negative component. The point $(- 2 / 5, 11 / 5, 0, 0)$ from the worked example is a perfectly legitimate basic solution and is not feasible. Both halves of that sentence are true simultaneously.

Not a reason to skip the sign test: a clean construction. The determinant being nonzero and the elimination going through without difficulty say nothing about feasibility. They are conditions on $A_{B}$ and $b$ , and the sign of $A_{B}^{- 1} b$ is not among them.

Not the same thing: zero nonbasic variables and zero basic variables. Nonbasic variables are zero by decision, always. A basic variable solving to zero is different. The point is then degenerate, which is taken up separately.

Contrast

Basic solutions that are not feasible

The most reliable way to produce a wrong answer here is to treat a successful construction as a finished one.

What the construction guarantees. That $A x = b$ holds. This follows from the algebra: $A x = A_{B} x_{B} = A_{B} (A_{B}^{- 1} b) = b$ , with no conditions beyond $A_{B}$ being invertible.

What it does not guarantee. That $x \geq 0$ . Nothing in forming $A_{B}^{- 1} b$ consults the sign restrictions, and there is no reason the result should respect them.

The two cases side by side. With $b = (4, 6)^{T}$ and $B = {1, 2}$ , the construction gives $(8 / 5, 6 / 5, 0, 0)$ , feasible. With $b = (4, 1)^{T}$ and the same basis, it gives $(- 2 / 5, 11 / 5, 0, 0)$ , not feasible. Identical procedure, identical effort, identical appearance of success. The only difference is a sign, and the only way to see it is to look.

Why this matters beyond bookkeeping. The enumeration argument for the simplex method rests on optima occurring at vertices. A basic solution that is not feasible is not a vertex, so evaluating the objective there and comparing it with genuine corners can return a value that beats every feasible point. An 'optimum' outside the region. The error does not present as a contradiction. It presents as an unusually good answer.

The habit. Make the sign test an explicit line of the work with its own verdict, in the same way the equality check is. Two sentences at the end: the equalities hold, and every component is nonnegative, so the point is a basic feasible solution, or component $x_{1}$ is negative, so this basic solution is not feasible.

Common errors

Common misconception

A basic solution constructed correctly from an independent set of columns is a corner of the feasible region, because the construction satisfies the constraints.

Basic Solutions

Assumptions and scope

Worked material

Three bases for one system

What is not a basic solution

Basic solutions that are not feasible

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history