Practice: Basic Solutions

Check the arithmetic first. With $B=\{1,2\}$ the system is $x_1+2x_2=4$ and $3x_1+x_2=3$. From the second, $x_2=3-3x_1$. Substituting: $x_1+2(3-3x_1)=4$, so $x_1+6-6x_1=4$, giving $-5x_1=-2$ and $x_1=2/5$. Then $x_2=3-6/5=9/5$. The student's numbers are correct.

Check the equalities. $2/5+18/5+0=20/5=4$. And $6/5+9/5+0=15/5=3$. Both hold exactly, as the student says.

Check the signs. , , $x_3=x_4=0$. Every component is nonnegative. So here the point is feasible, and the conclusion happens to be right.

But the reasoning does not support it. The student's argument runs: determinant nonzero, equations check out, therefore vertex. That chain is invalid, and it would produce the same confident conclusion on a system where the answer is wrong. The sign test never appeared in it.

A case that breaks it. Keep the same $A$ and basis, and change the right-hand side to $b=(4,12{)}^{\mathsf{T}}$. Then $x_1+2x_2=4$ and $3x_1+x_2=12$ give $x_1+24-6x_1=4$, so $-5x_1=-20$, $x_1=4$, and $x_2=12-12=0$. Now try $b=(10,3{)}^{\mathsf{T}}$: $x_1+2x_2=10$, $3x_1+x_2=3$ give $x_1+6-6x_1=10$, so $-5x_1=4$ and $x_1=-4/5$, with $x_2=3+12/5=27/5$. The determinant is still $-5$, the equalities still check out exactly, and $(-4/5,27/5,0,0)$ is not feasible and not a vertex.

What the student is missing. A step, not an answer. The construction guarantees $Ax=b$ and nothing else; feasibility requires testing $x\ge 0$ on the result. Getting the right verdict without that test is luck, and it is the kind of luck that runs out silently.

Why the basis suffices. A basis determines its basic solution uniquely: set every nonbasic variable to zero and solve $A_B{x}_B=b$, giving $x_B=A_B^{-1}b$. Nothing else is needed, so the list of indices is a complete description of the point. Logging $m$ indices rather than $n$ numbers is also considerably more compact.

What must additionally hold. That $x_B\ge 0$. The construction guarantees the equality constraints only, so a basis alone does not certify a corner. Inside the simplex method this test is not performed as a separate step at each iteration. It is maintained as an invariant: the method starts from a basic feasible solution, and the minimum ratio test chooses the step precisely so that no component is driven negative. The sign test has been folded into the ratio test, which is why it is no longer visible.

Two iterations, same point, different bases. That is degeneracy. A corner with fewer than $m$ strictly positive components can be described by more than one basis, so a swap changed the basis while the point stayed put. The step length was zero.

What it signals. Not an error. It means the method stalled. One iteration spent without progress in position or objective value. Occasional stalling is ordinary; a repeating cycle of it is the pathological case that anti-cycling rules exist to prevent, and a log showing the same point recurring over many iterations is the symptom worth investigating.

Why this reading requires the unit. A learner who treats a basis and a point as interchangeable has no account of two bases naming one point, and reads the log as a bug in the solver rather than a property of the geometry.