Basic Solutions

Switch off all but $m$ variables, solve for what remains, and you have constructed a point. Nothing in that construction consults the sign restrictions, which is why the point it produces may be nowhere you are allowed to be.

The construction is short: switch off the variables outside the basis, solve for the ones left on. What makes it worth its own unit is the step that is not in it. Nothing in the procedure consults the nonnegativity restrictions, so the arithmetic will hand you a point with a negative component and report no difficulty at all. That point satisfies every equation and is still not a member of the feasible region.

So there are two questions here, and they are answered in order rather than together: what point does this basis determine, and is that point feasible. Collapsing them is the error this unit exists to prevent.

This unit assumes you can test a set of vectors for independence, solve a square system, and convert a program to standard form.

There are more variables than equations, so the equations alone do not pin down a point. They leave a whole flat of solutions. To land on one specific point you must supply something extra, and the extra thing is a decision.

The decision is: choose $n-m$ variables and declare them zero. What remains is a square system, and a square system whose columns are independent has exactly one solution. So the construction is choose which variables to switch off, then solve for the rest.

The arithmetic gives no signal when the result is infeasible. You solve $A_B{x}_B=b$ and numbers come out. Some may be negative. The equations hold exactly, substitute and check, $Ax=b$ is satisfied, and the point is still not an answer, because a production quantity of $-3$ units is not a plan and a negative slack is a constraint that was violated rather than met.

That is why the feasibility test is a separate step rather than a property of a job well done. A successful construction guarantees the equalities. It guarantees nothing about the signs, and the signs are half of what feasibility means.

There is a second thing the arithmetic will not tell you. If the chosen columns are dependent, $A_B$ is singular and there is no basic solution for that choice, not an infeasible one, none at all. Checking independence first is what distinguishes 'this basis gives an infeasible point' from 'this was never a basis'.

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

Basis. A set $B=\{B(1),\dots ,B(m)\}$ of $m$ linearly independent columns of $A$. Writing $A_B$ for the $m\times m$ matrix of those columns, independence makes $A_B$ invertible.

Basic solution. Set every nonbasic variable to zero and solve for the rest:

This satisfies $Ax=b$ by construction, since $Ax=A_B{x}_B=b$, and it is uniquely determined by $B$.

Basic feasible solution. A basic solution that additionally satisfies $x\ge 0$.

The gap between the two. The construction above involves no sign test. The components of $A_B^{-1}b$ may be negative, and where any is, the basic solution lies outside the feasible region. The test $x_B\ge 0$ is a separate step applied to the result.

Structure of the point. Every basic solution has at least $n-m$ components equal to zero, since that many variables were set to zero to make the system square. It may have more, if a basic variable also solves to zero.

How many. There are $(\genfrac{}{}{0ex}{}{n}{m})$ ways to choose $m$ columns from $n$, but not every choice is a basis: dependent columns make $A_B$ singular and determine no basic solution at all.

Check the system is in standard form. Equality constraints and nonnegative variables. If it is not, convert first: the definitions below are stated for $Ax=b$ with $x\ge 0$ and do not apply to a mixed system.

Test the proposed columns for independence. Assemble $A_B$ and determine whether its columns are independent, by elimination or by a nonzero determinant. If they are dependent, stop and report that the set is not a basis. There is no basic solution to construct, which is a different outcome from constructing an infeasible one.

Set every nonbasic variable to zero. Write them down explicitly as zeros rather than omitting them. They are components of the answer, and a reported vector missing them is incomplete.

Solve the square system $A_B{x}_B=b$. Use elimination rather than forming the inverse. The result assigns a value to each basic variable.

Assemble the full vector. Place the solved values at their basic positions and zeros elsewhere, in the original variable order.

Verify the equalities. Substitute into $Ax=b$ and confirm every row. This catches arithmetic slips before the feasibility question is reached.

Now test the signs, as a separate question. Check whether every component is nonnegative. If so the point is a basic feasible solution and therefore a vertex of the feasible region. If any component is negative the point is a basic solution that is not feasible: a legitimate result of the construction, and not a corner.

Report both facts. Say which point the basis determines and whether it is feasible. Reporting only the first invites the reader to assume the second.

Take

so $m=2$, $n=4$, and the columns are $A_1=(1,1{)}^{\mathsf{T}}$, $A_2=(1,0{)}^{\mathsf{T}}$, $A_3=(1,0{)}^{\mathsf{T}}$, $A_4=(0,1{)}^{\mathsf{T}}$.

Basis $\{2,4\}$. , 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\}$. , 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{)}^{\mathsf{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.

Problem. For the system

construct the basic solution for $B=\{1,2\}$ and classify it.

Goal. The point the basis determines, and whether it is feasible.

Relevant principle. The construction guarantees the equalities. Feasibility is a separate test on the result.

Step 1: check independence.

Nonzero, so the columns are independent and $B$ is a basis.

Step 2: set the nonbasic variables to zero. $x_3=0$ and $x_4=0$.

Step 3: solve the square system.

From the second, $x_2=6-3x_1$. Substituting: $x_1+2(6-3x_1)=4$, so $x_1+12-6x_1=4$, giving $-5x_1=-8$ and $x_1=8/5$. Then $x_2=6-24/5=6/5$.

Step 4: assemble. $x=(8/5,6/5,0,0)$.

Step 5: verify the equalities. $8/5+12/5+0=20/5=4$. And $24/5+6/5+0=30/5=6$. Both hold.

Step 6: test the signs. Every component is nonnegative. This one is a basic feasible solution.

Now change $b$ to $(4,1{)}^{\mathsf{T}}$ and repeat with the same basis. The system becomes $x_1+2x_2=4$, $3x_1+x_2=1$. From the second, $x_2=1-3x_1$; substituting, $x_1+2-6x_1=4$, so $-5x_1=2$ and $x_1=-2/5$, then $x_2=1+6/5=11/5$.

The point is $(-2/5,11/5,0,0)$. Verify the equalities. $-2/5+22/5=20/5=4$, and $-6/5+11/5=5/5=1$. Both hold exactly.

Test the signs. . This is a basic solution that is not feasible. It is not a vertex of the feasible region and it is not a candidate for the optimum.

What to notice. Steps 1 through 5 were equally successful in both cases. The determinant was nonzero, the system solved cleanly, the equalities checked out. Only step 6 separates them, and a learner who treats step 5 as the end of the work will report the second point as a corner.

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.

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 $Ax=b$ holds. This follows from the algebra: $Ax=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\ge 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{)}^{\mathsf{T}}$ and $B=\{1,2\}$, the construction gives $(8/5,6/5,0,0)$, feasible. With $b=(4,1{)}^{\mathsf{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.

1. For $x_1+x_2+x_3=3$, $2x_1+x_4=2$, $x\ge 0$, construct the basic solution for $B=\{3,4\}$ and classify it.

2. Same system, $B=\{1,3\}$. Construct and classify.

3. Same system. Show that $\{1,2\}$ is a basis, construct its basic solution, and say whether it is feasible.

4. How many components of a basic solution of this system must be zero, at minimum? Give a basic solution with more zeros than that minimum, and say what such a point is called.

5. A colleague reports: 'I chose columns 2 and 3, the determinant was zero, so the basic solution is infeasible.' Two things are wrong with that sentence. What are they?

A basis is $m$ independent columns. The basic solution it determines comes from setting every nonbasic variable to zero and solving the square system $A_B{x}_B=b$, and it is unique given the basis.

The construction guarantees the equality constraints and nothing else. Feasibility is a separate test, every component nonnegative, applied to the result, and a basic solution failing it is not a vertex and not a candidate for the optimum.

Three outcomes are possible from a proposed column set, and they are genuinely different: the columns are dependent and there is no basic solution at all; the construction succeeds and the point is infeasible; the construction succeeds and the point is a basic feasible solution.

Every basic solution has at least $n-m$ zero components, because that many variables were switched off to make the system square. When a basic variable also solves to zero the point has more zeros than the minimum, and that is degeneracy.

This construction is performed inside every simplex iteration, where the sign test has been folded into the ratio test and is no longer visible as a separate step. Knowing it is there is what makes the ratio test's restriction intelligible rather than arbitrary.