Revised simplex avoids storing a full tableau, but it still needs to solve systems with a changing basis. Recomputing a factorization after every pivot is possible; a product-form update shows how a new solve can instead reuse earlier work. This unit develops the algebra in exact arithmetic, explains the order of the operations, and distinguishes an algebraically valid update from a numerically reliable implementation.
A replacement is a matrix multiplication
In the standard-form maximization problem , let be a nonsingular basis. Its basic values satisfy . Suppose a nonbasic column enters at basis position and compute its direction from
Definition 19.1.1
(Eta matrix of a basis replacement)
Let be a nonsingular basis with ordered columns, let a column replace the column in position , and let solve . The eta matrix of this replacement is the identity with column replaced by :
where is the th coordinate vector. Column of is , the old column, and column is ; hence is exactly the new basis matrix.
The index is a position in the ordered basis, not necessarily the label of the leaving variable.
Common mistake
(Indexing the eta column by the leaving variable)
If the ordered basis is and leaves, the replacement happens in position , so column 2 of the identity is replaced by . Replacing column 1 because the leaving variable is called builds the product for a different basis: it removes , keeps , and the update solves the wrong systems from then on.
Theorem 19.1.2
(One update and its inverse)
The replacement basis is nonsingular exactly when . When this holds, solving requires
Solving requires for , followed by
Proof
(Determinant and the two eta solves)
All columns of except column are coordinate vectors. Expanding its determinant along that column gives , so and is nonsingular precisely when . In , row reads , while every other row reads ; these give the first formula. In , every row except reads , and row reads . Substitution gives the second formula. Each operation is reversible when .
In a primal feasible pivot the ratio test selects a row with , so the pivot is nonzero. A zero step can still give a valid new basis: the leaving basic value can be zero even though is positive. By contrast, replacing at a zero direction coordinate produces a singular matrix and is not a pivot.
Concept lensAlgebraic
The inverse update is a tableau pivot
The solve formula says that is again an eta matrix: it is the identity with column replaced by , where and for . Hence , and applying to the full tableau divides row by and subtracts times the new row from each row . That is exactly the tableau pivot on the entering column, whose current entries are . The product form stores these pivots instead of the tableau.
A sequence of updates
Start from an invertible for which a factorization is available. If successive pivots produce eta matrices , then
Proposition 19.1.3
(Solving with a product-form basis)
Let be nonsingular and let be eta matrices with nonzero pivots, so that is nonsingular.
- The system is solved by solving , then for , and taking .
- The transpose system is solved by solving , then for , and finally .
When , only the original basis solve is needed.
Proof
(Peeling factors from the left)
Each factor is nonsingular: by assumption and each because its determinant is its nonzero pivot. For the ordinary system, reads , which holds exactly when with the unique solution of . Suppose that after solves the equation has become . Writing the left side as , it holds exactly when , where . After such steps no factor remains and .
For the transpose system, . The same peeling now meets first: holds exactly when with . Continuing removes and leaves .
Proof X-ray
Why the transpose order reverses
The proof repeats one move: a nonsingular factor standing leftmost in the equation is canceled by one solve, leaving an equation of the same shape with one factor fewer. The nonzero-pivot hypothesis enters only here; with some step could have no solution or many. The single place where the two systems differ is the transpose rule for products: transposition reverses the order of factors, so becomes leftmost and rightmost. Nothing in the argument lets factors move past one another, which is why the eta matrices never need to commute, and the argument closes after exactly solves because each step removes one factor.
For a current basis, solve to obtain reduced costs . To inspect an entering column, solve . Together with , these are precisely the quantities needed by the primal ratio test and reduced-cost test. The data must be updated when a basic variable changes; the previous price vector is generally no longer correct.
Common mistake
(Reusing the previous price vector)
After a pivot, the cost in position of changes, so the old no longer satisfies . In the worked examples below, the prices at the first updated basis are ; at the second basis they give , not . The transpose solve must be repeated with the updated .
Worked examples
Worked example 19.1.4
(Two replacements from the identity basis)
Begin with and . Let enter position 1. Since , the ratio candidates are and ; position 1 leaves. The new basic vector is and
Next let enter. Solving gives . The ratios are and ; position 2 leaves. Thus
The new basic vector is : the first old basic value decreases by and the entering value is 2. Equivalently, solving and then yields . Direct multiplication verifies .
Worked example 19.1.5
(Prices by the reversed transpose solve)
Continue with and suppose the basic costs are . For the transpose solve, gives and , so . Then reads , , so . Directly, .
If the two original identity columns have cost zero, their reduced costs are both . With no other columns, primal feasibility and nonpositive reduced costs certify the maximum . The two specified entries indeed have positive reduced cost at their respective starting bases for this cost choice: 3 initially, and after the first pivot, where solves .
Counterexample mode
A plausible update in the wrong order
For the same two factors, applying before to produces , not . Multiplying by gives , not . Matrix inverses cannot be reordered just because each individual solve is correct.
The next example isolates the boundary case of the ratio test: a pivot with a positive direction entry and a zero step.
Worked example 19.1.6
(A zero step with a nonsingular update)
Take , and let enter, so . The ratio candidates are and ; position 1 leaves with step length zero. The eta matrix is the above, with , and solving gives , . The basis has changed, the basic values have not, and the update is valid.
Replacing position 2 instead is also algebraically legal, since , but it ignores the ratio test. With , solving gives and . The new basis is nonsingular but infeasible. A nonzero pivot guarantees a basis; the ratio test is what preserves feasibility.
Computation and limits
An eta update stores its pivot position and direction; applying it costs work proportional to the stored nonzeros plus the pivot operation. Sparse directions can make this economical, but multiplying or solving can create fill-in, and a long update chain grows in work and storage. Practical implementations periodically refactor the current basis and discard its old update chain. The best frequency depends on sparsity, hardware and numerical behavior; there is no universal fixed threshold proved here.
The formulas divide by . A very small nonzero pivot is legitimate in exact arithmetic but can magnify floating-point error. Check the residuals and , and use suitable scaling, stability controls and refactorization in numerical software. Small residuals alone do not guarantee small forward errors for an ill-conditioned basis. Exact reduced-cost signs and finite-pivot arguments do not automatically survive rounded arithmetic; a rigorous certificate requires independently justified error bounds.
Exercises
Quick check
(Let be the identity of order three with column 2 replaced by . Solve and .)
Use the two formulas of the update theorem with and .
Solution · Answer
The first formula gives , and . For the transpose, , , and . Direct substitution verifies both results.
Quick check
(In the two-pivot example, suppose a third column is and costs 4. Find its direction and reduced cost at . Is it an improving entering column for maximization?)
Use the prices already computed at .
Solution · Answer
Solving gives , since and . With , its reduced cost is ; it cannot improve the current maximum by increasing from zero.
Quick check
(If , can replacing column of a nonsingular basis by give another basis? Explain without performing a ratio test.)
Compute the determinant of the replacement.
Solution · Answer
No. The replacement is with determinant , so its columns are dependent. A nonzero pivot is a necessary algebraic condition even outside the primal ratio test.
Quick check
(A solver obtains a residual of zero after rounding the displayed residual to six decimal places. Does this prove that the computed basic vector is exact?)
Separate the rounding of the displayed number from the conditioning of the basis.
Solution · Answer
No. The unrounded residual may be nonzero. Even an exactly small residual can correspond to appreciable forward error if the basis is ill-conditioned. A bound on the inverse action and controlled rounding are needed to turn residual information into a forward-error bound.