Let B be the columns of the original coefficient matrix belonging to the current basis. Then the body of every tableau on the path is B⁻¹[A | b] and its objective row is c_BᵀB⁻¹[A | b] - [c | 0], with B⁻¹ itself sitting in whichever columns started as the identity. A tableau twenty pivots in is a view of the original data rather than a degraded copy of it, and one of the three products on this page is the solution of a second programme hidden in the first.
Core ideas
Nothing new is computed here. What changes is what a tableau is: not a record of what has been done to the data, but the data multiplied by one matrix.
A pivot is a sequence of elementary row operations, and each of those is left multiplication by an invertible matrix. So the whole run of pivots amounts to one invertible matrix M applied to [A | b]. Because the basic columns of the result are the identity, M·B = I, so M is B⁻¹ and there is nothing else it could be.
The basis is a set of column indices. B is those columns of the original A, before any pivoting, assembled in the order the tableau’s rows carry them. Taking them from the current tableau gives the identity and a vacuous check; the content of the identity is that the original data is enough to reproduce a tableau twenty pivots later.
Not “the slack columns”. Those coincide after a ≤-only setup and part company the moment a ≥ or an = row appears: the surplus column of a ≥ row is -1, and the identity column beside it is the artificial. Learn the rule and the block is always in the right place; learn the slogan and it is in the right place on the easy examples only.
The material
The identity and its one-paragraph proof, the three products checked entry for entry, and the misreading that survives every caps-only example.
For a standard-form programme with coefficient matrix A and a basis whose columns, in row order, are B(1), …, B(m), the basis matrix B is the m × m matrix whose i-th column is column B(i) of A. It is invertible, which is part of what it means to be a basis.
The tableau at basis B has body B⁻¹[A | b] and objective row c_BᵀB⁻¹[A | b] - [c | 0], where c_B is the vector of objective coefficients of the basic variables in row order. In particular the right-hand column is B⁻¹b and the reduced cost of column j is c_BᵀB⁻¹A_j - c_j.
Each elementary row operation on a matrix is left multiplication by an invertible matrix, and a pivot is a composition of finitely many of them. So the tableau body after any run of pivots is M[A | b] for a single invertible M, because a product of invertible matrices is invertible.
The tableau is held so that the basic columns form the identity: the columns of M A indexed by the basis are I. Those columns of A are B by definition, so M B = I and therefore M = B⁻¹. The objective row is the same argument on the extra equation: it starts as -[c | 0] and each pivot adds multiples of body rows to it until the basic columns read zero, which is exactly the combination c_BᵀB⁻¹[A | b].
□
Two consequences follow at once. A tableau is not a degraded copy of the data — it is B⁻¹ times the data, recoverable from A, b and a list of column indices. And every entry of it is a ratio of determinants of submatrices of the original data, by Cramer’s rule, so the denominators never grow beyond what the numbers you typed can produce, however many pivots it takes.
Take maximise 3x₁ + 2x₂ subject to x₁ + x₂ ≤ 4 (capacity) and x₁ + 3x₂ ≥ 6 (a contract). The ≥ row gets a surplus e₂ with column -1 and an artificial a₂ with column +1, so the columns are x₁, x₂, s₁, e₂, a₂ and the starting identity is {s₁, a₂}. The method finishes at the basis {x₁, x₂}.
Now the misreading. B⁻¹ is [[3/2, -1/2], [-1/2, 1/2]], and it appears in the final tableau under the columns s₁ and a₂ — the two that started as the identity. The slack and surplus columns are s₁ and e₂, and e₂’s column is (1/2, -1/2), which is the negative of B⁻¹’s second column, because A’s surplus column is the negative of its artificial column. Read B⁻¹ out of the slack and surplus columns and you get a matrix whose determinant has the wrong sign.
On maximise 3x₁ + 5x₂ with x₁ ≤ 4, 2x₂ ≤ 12 and 3x₁ + 2x₂ ≤ 18, all three rows are ≤ rows, the three slacks are the starting identity, and the final tableau really does hold B⁻¹ under s₁, s₂, s₃: [[1, 1/3, -1/3], [0, 1/2, 0], [0, -1/3, 1/3]] against a basis matrix built from the s₁, x₂ and x₁ columns of the original A.
Every example a reader is likely to have met is of this kind, which is why the slogan survives. It stops being true at the first ≥ row, and it also stops being true after a first phase of “Artificial Variables and Two-Phase Simplex”, where the starting identity contains artificials by construction.
One detail of the requirement-row tableau is worth explaining rather than passing over: the reduced cost of a₂ is -1/2, which is negative in an optimal tableau. That column is an artificial, dropped after the first phase and barred from re-entering, so it is not a candidate and the optimality test does not apply to it. Its entry is still a perfectly meaningful number — it is the second component of c_BᵀB⁻¹.
c_BᵀB⁻¹ is (7/2, -1/2) here, and those two numbers are sitting in the objective row under the columns that started as the identity. They are the solution of a second linear programme built from the same data, they say what one more unit of each right-hand side would be worth, and finding them already computed in a row you have been carrying since the first pivot is the whole opening of Duality and Sensitivity Analysis.
Interactive
B from the basis, B inverse by reduction, and the tableau rebuilt from the original data
Method
The point of the exercise is that nothing but the original matrix and a list of indices is needed. Resist every temptation to read a number off the tableau you are checking.
Row 1 carries one basic variable, row 2 another, and the order matters because it fixes the order of B’s columns and of c_B. A permuted B inverts to a permuted B⁻¹ and nothing will match.
Those columns as they were before any pivoting. If you find yourself copying from the current tableau you will get the identity, and the check will pass without testing anything.
The same row reduction as “Inverse Matrices”, and the same trace: when the left block is the identity the right block is B⁻¹. Keep it as exact fractions; this is the one matrix every other figure on the page depends on.
The body of the tableau and its right-hand column, respectively. Any single mismatch means an error in the basis order, in B, or in the pivoting — and you can tell which by whether the basic columns came out as the identity.
c_BᵀB⁻¹A - cᵀ, which should reproduce the objective row including the zeros on the basic columns. Then read c_BᵀB⁻¹ off the columns that started as the identity and check those two readings agree.
A capacity row and a contract row, so the columns are x₁, x₂, s₁, e₂ and an artificial a₂. Everything below is built from A, b, c and the two basis indices.
The reason e₂’s column is the negative of the right one is already in A: the surplus column is (0, -1) and the artificial column is (0, 1), so multiplying by B⁻¹ keeps them negatives of each other. Nothing has gone wrong in the pivoting — the wrong block was read out.
The two numbers (7/2, -1/2) are worth a second look. They are c_BᵀB⁻¹, they appear in the objective row under s₁ and a₂, and they are the marginal value of one more unit of each right-hand side: capacity is worth 7/2 per unit and the contract requirement costs 1/2 per unit. That is the dual solution, sitting in a row that has been carried along since the first pivot, and Duality and Sensitivity Analysis begins by naming it.
For a faded rehearsal, take the caps-only programme maximise 3x₁ + 5x₂ with x₁ ≤ 4, 2x₂ ≤ 12, 3x₁ + 2x₂ ≤ 18, whose optimal basis is {s₁, x₂, x₁} in row order. The supplied first move is that B’s three columns are the s₁, x₂ and x₁ columns of the original A, in that order: [[1,0,1],[0,2,0],[0,2,3]]. Invert it, produce B⁻¹A and B⁻¹b, and then say why the slogan about the slack columns happens to be true on this one and not on the one above.
You should be able to assemble B in row order from the original A, invert it by reduction, reproduce the body, the right-hand column and the objective row by multiplication, name the columns that hold B⁻¹ and say why they are not always the slacks, and point at c_BᵀB⁻¹ in the objective row.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.