Simplex pivots and degeneracy

For minimization in equality standard form, partition the matrix into basic columns $B$ and remaining columns $A_N$. Solving the equalities gives $x_B=B^{-1}b-B^{-1}A_Nx_N$. Substituting into the objective leaves a constant plus the reduced costs times nonbasic coordinates. The reduced cost of column $j$ is $c_j-c_B^TB^{-1}A_j$. It accounts for both the entering variable's direct cost and the cost changes required in the old basic variables. Looking only at the original cost coefficient can therefore select the wrong direction.

If every reduced cost is nonnegative at a primal feasible basis, every feasible nonbasic vector has objective at least the current constant. This is a global optimality proof, not merely a local observation about neighboring vertices. A negative reduced cost permits improvement if a positive feasible step exists. Choose that column to enter, define $d=B^{-1}A_j$, and increase its coordinate by $\theta$. The old basic coordinates become $x_B-\theta d$. This formula determines feasibility and handles positive, zero, and negative components of the direction without geometric guessing.

Only components with $d_i>0$ restrict an increase in the entering coordinate, because they decrease an existing basic coordinate. The largest feasible step is the minimum of $x_{B_i}/d_i$ over those components. A minimizing coordinate leaves the basis. Components with $d_i\le0$ cannot be used in this minimum: dividing by them either has no meaning or reverses the relevant inequality. If there are no positive components and the reduced cost is negative, arbitrary positive steps stay feasible, providing an explicit improving ray and proving the minimization problem unbounded below.

When the minimum ratio is positive, a negative reduced cost yields strict objective improvement. If it is zero, the exchange is degenerate: the basis changes at the same feasible vector. A tie between positive ratios creates a newly degenerate basis because several coordinates hit zero together. Pivoting still preserves the equations and nonnegativity, but strict descent can no longer prove termination by counting bases. A sequence of zero-length pivots can return to a previous basis under an unfortunate pivot rule. This is cycling, rather than numerical oscillation between approximately equal vectors.

Bland's rule chooses the eligible entering variable with smallest index and resolves leaving ties by the smallest indexed basic variable. In exact arithmetic this prevents cycling and gives finite termination when a feasible starting basis is available; it does not prove a polynomial pivot bound. Classical simplex pivot strategies can require exponentially many pivots on carefully constructed families. Polynomial-time algorithms for rational linear programming are known through other approaches, while a general strongly polynomial algorithm remains an open question. Practical effectiveness and a worst-case complexity guarantee answer different questions.

Revised simplex implementations solve systems with the basis and update sparse factorizations instead of rebuilding a dense tableau at every iteration. They also monitor primal residuals, dual residuals, scaling, and numerical stability. An apparently negative reduced cost smaller than floating-point uncertainty should not be treated as an exact theorem. Conversely, a rounded zero basic variable may conceal infeasibility. The mathematical pivot derivation supplies invariants that software can test, but robust implementation requires tolerance policies and refactorization safeguards beyond the exact arithmetic lesson.