Solving a system

A market stall sells three bundles. The first holds one loaf, two cheeses and one bottle, and it costs eight coins. The second holds two loaves and one cheese, and it costs four coins. The third holds one loaf, one cheese and two bottles, and it costs nine coins. The stallkeeper has lost the price list.

The section question asks how elimination — the row-by-row method below — finds every solution, and the stall is a fair test. Write the three bundles as rows of numbers, with the price of each bundle in a last column, and let the first three columns belong to the loaf, the cheese and the bottle. The table is the system, and solving it means finding the single list of three prices that makes every row true. !Three systems after elimination, replayed from the stored row operations in the elimination stepper. Left: a pivot in every column gives one solution, (2, 3, −1). Middle: the third column has no pivot, so z is free and the solutions form a line. Right: a row of zeros beside a 1 reads 0 = 1, so no list satisfies the system. The boxes mark the pivots, the shaded column the free unknown, and the russet box the contradiction. Status: re-simulated.

The display holds the same information as three sentences about loaves, and it is easier to work with because the arithmetic only touches numbers. The vertical rule separates the coefficients from the price on the right.

Gaussian elimination clears the table column by column with three permitted moves: swap two rows, multiply a row by a nonzero number, and add a multiple of one row to another [S:27:37]. Each move is reversible, so the new table has exactly the same solutions as the old one, which is the only reason the method is allowed to change the numbers at all.

Reversibility deserves one line of proof. Undoing a swap is another swap, undoing a multiplication is a division by the same number, and undoing an addition is a subtraction. A solution of the old table therefore satisfies the new one, and a solution of the new table satisfies the old, so the two tables are two descriptions of a single problem.

Clear the first column first — put zeros below its leading entry — by subtracting twice the first row from the second and the first row from the third.

The display says the first column now has a one at the top and zeros below it, and the first pivot has done its work. The first entry of a column that you use to clear the rest is the pivot, and the algorithm always works left to right.

Clear the second column next, where the second pivot is minus three in the second row, and one move finishes the job: multiply the third row by three and subtract the second row from it.

The display is triangular, which means each row now involves only its own price and the ones to its right. The last row reads five bottles cost fifteen coins, so a bottle costs three.

Back substitution walks upward: the second row reads minus three cheeses minus two bottles equal minus twelve, and with a bottle at three that gives a cheese at two. The first row reads one loaf plus two cheeses plus one bottle equal eight, so a loaf costs one. Check the second bundle: two loaves and one cheese cost four, which matches the stallkeeper's total. The check is worth performing in every row, because one arithmetic slip survives back substitution and produces a list that satisfies the rows you used and fails the ones you did not.

The pivots also answer a question you have not asked yet. A pivot in every coefficient column and none in the last column means exactly one solution [S:27:53], which is the stall's case [S:21:213]. A pivot in every coefficient column on its own rules out more than one solution, because it makes the kernel the zero list. It does not guarantee one: a table with more rows than unknowns can satisfy that and still be unsatisfiable.

A pivot in the last column means no solution. When a solution exists, a coefficient column without a pivot leaves a price free to move, so the solutions form a line or a plane [S:27:53]. Elimination therefore classifies a system while it solves it. The previous section already named the free directions: they are the kernel.

The method has two costs, and both show up in practice. Dense elimination, the kind that touches every entry, takes a number of operations that grows with the cube of the table's width, so doubling the number of unknowns multiplies the work by about eight [S:28:75]. The choice of pivot also matters, because a pivot near zero produces huge multipliers and destroys accuracy, which is why implementations swap in a large entry before dividing [S:28:75]. The arithmetic above was exact, and Chapter 6 already showed why exactness stops being free once a computer holds the numbers. The same pivot pattern governs the fits ahead: a table with more rows than unknowns often has no exact solution, and Chapter 8 will choose the closest one.

The formal statement. Write the system as $Ax=b$. Each of the three permitted moves is multiplication on the left by an invertible matrix. A swap is a permutation matrix, a scaling is a diagonal matrix with a nonzero entry, and adding a multiple of one row to another is a triangular matrix with ones on the diagonal. Let $E$ be the product of the moves applied so far. The new system is $EAx=Eb$, and

$$Ax=b\text{ if and only if }EAx=Eb.$$

The display says the two systems have the same solutions, and that equivalence is the whole licence for changing the numbers.

The derivation. One direction is immediate: if $Ax=b$, then $EAx=Eb$. For the other, multiply by $E^{-1}$ and read $Ax=b$ again. Each move has an explicit inverse: swap the rows back, divide by the same nonzero number, subtract the same multiple. So $E^{-1}$ exists and is itself a product of permitted moves. Nothing in the argument assumes that $A$ is square or invertible, which is why elimination also classifies rectangular systems.

The edge case. A row of zeros with a nonzero right side means no solution, and a column without a pivot means a free unknown. L1's stall had a pivot in every column, so its answer was unique. The classification needs the augmented table: a solution exists exactly when the rank of $A$ equals the rank of the augmented matrix [S:27:53]. A table with more rows than columns can have a pivot in every column of $A$ and still fail on the right side, because a row reading $0=c$ with $c\ne 0$ has no pivot. For a square table, a pivot in every column forces $\mathrm{rank}(A)=n$ and $A$ invertible, so $Ax=b$ has exactly one solution for every right-hand side; inconsistency in a square system therefore appears as a column without a pivot, never with all columns pivotal. In floating point a pivot can also be nonzero but tiny, which produces large multipliers and cancels digits; partial pivoting swaps rows before dividing, so the pivot is not a tiny number [S:28:75].

What L1 hid. L1 said dense elimination grows with the cube of the width [S:28:75]. That counts arithmetic operations on a full table. With row and column permutations chosen to keep the factors sparse, the cost of a sparse factorization often grows approximately linearly with the dimension $n$, not with the number of nonzeros; the growth depends on the sparsity pattern and on the ordering [S:44:683]. L1 also presented the cost as a property of the method, while the constant depends on the pivot order, the machine and the storage layout.

Where the analogy breaks. "Clearing a column" suggests that the work stays inside that column. The multipliers you compute while clearing column one are applied to every column to the right, so the table fills in as you go. L1's clean triangle is a picture of the result, not of the intermediate tables, and the fill is what makes sparse elimination a different problem from dense elimination.

Where the idea comes from. Gaussian elimination is an algorithm that applies elementary transformations to bring a system into reduced row-echelon form [S:27:37]. Solomon gives the cost for a dense table as $O(n^3)$ and explains why pivoting is needed: without a row swap, a zero in the pivot position stops the method even when the system has a solution [S:28:75]. He adds that full pivoting is rarely necessary and is not enabled by default in common implementations [S:28:76].

What the field has not settled. How to choose a preconditioner. Solomon writes that the best strategy is often specific to the application and that you generally test a few before settling on one [S:28:239]. A settled theory would give a construction with a convergence bound that holds across a family of matrices. The evidence would be that construction beating hand-tuned choices on a standard test set at equal cost per step.

What depends on it. Large systems are now solved by iteration more often than by elimination. Conjugate gradients solve a symmetric positive definite system through a sequence of matrix-vector products, and the chapter that introduces them presents early stopping as a way to defeat the cubic runtime when an approximate answer suffices [S:28:226]. Sparse direct methods take the other route: with row and column permutations the factors stay sparse, and the cost often grows approximately linearly with the dimension rather than with the number of nonzeros [S:44:683].

What to read next. Read section 2.3 of Mathematics for Machine Learning for the algorithm and the pivot bookkeeping [S:27:37]. Read chapter 11 of Solomon for gradient descent, conjugate gradients and preconditioning [S:28:226]. Read appendix C of Convex Optimization for sparse LU and Cholesky and for the banded case [S:44:683]. Then factor a small matrix by hand and count the operations, which is the only way the cubic becomes believable.