Solving Ax = b, and Gaussian elimination
Up to now a matrix has been a thing that moves vectors around. This part turns the question around. Instead of asking where a given input lands, you are handed the output b and asked which input x produces it. That is the equation A x = b, and it is the most common thing anyone actually wants from linear algebra: the pose of a camera from its observations, the weights of a fit from its data, the flow of a network from its demands. The geometry gives the question its shape — three planes meeting at a point, along a line, or never — and Gaussian elimination gives you a mechanical way to answer it without ever changing the answer.
The question
Which input lands on b?
Part 3 established the central fact of the series: an m×n matrix A is a function, and applying it to a vector is a linear map. A x takes the input x and lands it somewhere in the output space. Solving A x = b asks for every input that lands exactly on the given target b. Sometimes there is one; sometimes there is a whole family of them; sometimes there are none at all.
Two pictures describe the same equation. In the column picture, A x is a linear combination of the columns of A with the entries of x as coefficients, so solving means asking which combination of the columns reaches b. In the row picture, each row of A is one scalar equation, and in three dimensions each scalar equation is a plane. Solving means finding the point or points that lie on all the planes at once. The algebra of elimination will answer the column question; the row picture will tell you what the answer looks like.
It is worth saying what an answer would even mean. If A is invertible there is a single vector A⁻¹b that does the job, and the map has no ambiguity to resolve. But most matrices are not invertible, and the interesting cases are the ones where invertibility fails: a tall system with no exact solution, a wide system with infinitely many, a square system that destroys a direction and leaves a whole family behind. Elimination handles all of these with the same few moves, and the geometry tells you in advance which one you are in.
The two pictures are worth holding side by side because they answer different questions. The column picture is the one you compute with: it turns solving into asking whether b can be assembled from the columns. The row picture is the one you see: it turns the same question into the intersection of flat sheets. When they agree — and they always do — they hand you both a procedure and a mental image, which is the pattern this series keeps returning to.
Elimination, one move at a time
Three legal moves, and an invariant
The reason elimination works is that the solution set is an invariant: every move you are allowed to make rewrites the equations without changing which x satisfies them. There are only three moves, and each one is invertible, so nothing is lost. You may swap two equations, you may multiply an equation by a nonzero number, and you may subtract a multiple of one equation from another. Each of those operations can be undone, which is why the answer survives.
The plan is to use the third move to clear out the entries below the diagonal, one column at a time, until the system is triangular. When a diagonal entry is zero or uncomfortably small, the first move saves you: you exchange rows to bring a larger entry into the pivot position. That is called partial pivoting, and it is what a numerical library does by default. The demo below writes the system as an augmented matrix [ A | b ] and performs one such move each time you press the button. The pivot being used is ringed, the row being eliminated is shaded, and the operation is spelled out in words.
Each press applies exactly one elementary row operation to the augmented matrix.
Watch the right-hand column as the left-hand block is cleared. The numbers change, but the solution to the system they encode does not. When the process stops, the left block is upper triangular: every entry below the diagonal is zero. The system is now in the shape U x = c, and that shape is easy to read from the bottom up.
It is worth naming what the process really computes. The row moves that turn A into U, collected into a lower-triangular matrix L, satisfy A = L U after any row exchanges are accounted for. That factorisation is the reusable object: once you have L and U, a new right-hand side b costs only a forward solve and a back solve, which is exactly the point of the application panel further down. The code behind this page plans the moves with the same partial-pivoting logic the toolkit's LinAlg.mat.lu uses, then replays them one at a time so you can see each one.
There is a second way to see why the answer survives, and it is the one to keep. Each elementary row operation is itself a matrix acting on the left: a permutation matrix swaps rows, a diagonal matrix scales one, and an identity with a single extra entry below the diagonal subtracts a multiple. Eliminating one column is therefore nothing more than multiplying the augmented matrix by some E, and the whole sweep is the product M = E_k … E₂E₁. Every one of those factors is invertible, because every one of the three moves can be undone. The systems A x = b and M A x = M b have exactly the same solutions, since applying the inverse M⁻¹ to both sides recovers the first from the second. Elimination is a change of viewpoint, not a change of problem.
That framing also explains where L comes from. The inverse of the accumulated eliminator is lower triangular, and it records the multipliers you used, in the order a forward solve needs them. The product A = L U is therefore not a lucky identity but a bookkeeping statement: elimination has split A into the multipliers it applied and the triangular shape that resulted. When a library hands you an L U factorisation, it is handing you the history of the row operations, packaged so a new right-hand side can be solved in two cheap sweeps.
Back-substitution
Reading a triangular system from the bottom up
A triangular system is solved in reverse. The last row involves only x_3, so it hands you that value directly. Substitute it upward into the second row, which then involves only x_2, and so on until every unknown is known. Each step divides by a diagonal pivot, which is why a zero on the diagonal is a warning: the system is either singular or in need of a row exchange.
The demo continues where the elimination stepper finished. It uses the final triangular matrix, solves one row at a time, and then checks the answer the only way that matters — by multiplying A x and comparing with b.
Press through the rows from the bottom up. The final step verifies A x = b.
Two facts are hidden in this small exercise. First, the work is cheap: elimination costs on the order of n³ operations, but each new right-hand side costs only n², because the expensive part was factoring the matrix, not solving the system. Second, the answer is unique exactly when every diagonal pivot is nonzero. If a pivot vanishes and cannot be rescued by a row exchange, the triangular system has a free variable, and the solution set grows from a point into a line, a plane, or a higher-dimensional family. That is the rank story of Part 7, seen from the elimination side.
The two triangular sweeps have names. Solving L y = b from the top down is a forward substitution; solving U x = y from the bottom up is the back substitution this demo performs. A single system therefore costs a forward pass, a back pass, and the one-time elimination that produced the factors. When the pivot on a diagonal is zero, the back pass cannot start: division by zero is the algebra telling you that the map has folded a direction onto zero, and the free variable you were expecting shows up as a column with nothing to solve for.
Three planes
The row picture of a 3×3 system
Read each row of a three-by-three system as a plane in space. A row says that a particular combination of x, y and z equals a constant, and the set of points satisfying it is a flat sheet. Solving the whole system means finding the points common to all three sheets. The possible outcomes are few, and they are worth memorising because they recur everywhere: the planes can meet at a single point, they can share a whole line, or they can have no common point at all.
The demo below draws three planes with a translucent fill so you can see through them. Use the preset buttons to switch between a system whose planes meet at one point, a system whose planes share a line, and an inconsistent system whose planes form a triangular prism and never meet. Drag the scene to rotate the camera; the answer is a geometric fact about the planes, not an artifact of the viewpoint.
Drag to orbit. The translucent sheets are the three equations; their common intersection is marked.
Notice what the geometry is telling you about the algebra. When the planes meet at a point, the three row directions are genuinely independent and elimination produces three nonzero pivots. When they share a line, one equation is a consequence of the others, one pivot disappears, and a free variable remains. When there is no common point, the equations contradict one another and elimination eventually produces a row of the form 0 = nonzero — the algebraic signature of an inconsistent system.
Degenerate configurations deserve names, because they are what you will actually meet in floating point. Two planes are parallel when their normal vectors point along the same line; they either never meet or coincide entirely, and in either case the pair already decides the answer. Three planes can fail in a way that is easy to draw: pairwise intersections that are parallel lines, forming a triangular prism whose three sheets have no common point. That is the geometric face of inconsistency, and it is exactly the case elimination reports when it produces a pivot in the right-hand column and none in the left. The opposite degeneracy is redundancy: one equation may be a combination of the other two, in which case the planes pivot around a common line and a free variable appears.
It helps to keep two numbers in view while you look at the picture. The number of independent normals is the rank of the coefficient matrix, and it is the dimension of the set of directions the planes can jointly constrain. The number of independent equations that actually bite is the rank of the augmented matrix, and consistency is the statement that these two ranks agree. When they agree, the common set has dimension n − r: a unique point when r equals the number of unknowns, a line when it is one less, a plane when it is two less. When they disagree, the common set is empty. This is the same ledger you will meet, fully general, in the next part.
Reading the cases
Consistent or not, unique or not
The possible behaviours of A x = b fall into a small table, and every entry is decided by two numbers: the rank of A and whether b lies in the column space of A. Consistency is entirely about b being reachable. Uniqueness is entirely about the columns of A being independent.
| Situation | Row picture | Algebra |
|---|---|---|
| Consistent, unique | Three planes meet at one point | Every column a pivot; no free variables |
| Consistent, many | Planes share a line or plane | A free variable; null space is nonzero |
| Inconsistent | No point on all three planes | A pivot in the augmented column only |
The middle row is the one that surprises people. A system with more than one solution always has infinitely many, because if x and x' both solve it then their difference lies in the null space, and any multiple of a null vector can be added to a solution without changing the output. You will meet that statement again as the rank–nullity theorem in Part 7, where the null space becomes a first-class object rather than a leftover. The determinant from Part 5 already told you the square case: a nonzero determinant means one solution, a zero determinant means either none or infinitely many.
When a system is inconsistent, the honest answer is not a solution but the closest one. That is the least-squares problem, and it is the subject of Part 10: you project b onto the column space and solve the system that remains. Elimination is the engine underneath that projection too.
Numerically, the pivots are the whole conversation. Choosing the largest available entry in a column — partial pivoting — is not cosmetic: a tiny pivot divides through the rest of the row and amplifies whatever rounding error is already there. Swapping the rows first keeps the multipliers small and the computation stable. This is why the elimination code behind this page searches the column for a pivot before every step, and why a library reports the number of row exchanges alongside the factors. The geometric version of the same remark is that nearly parallel planes make the intersection point extremely sensitive to the right-hand side, a conditioning story told in Part 19.
Finally, note which quantities are worth keeping. The solution x is a single vector and may be discarded; the factorisation is reusable. A model that must solve thousands of systems sharing one matrix factors it once and solves many times. A planner that re-solves after every sensor update can often reuse most of the work. Elimination is easy to explain and it is also the shape of the practical algorithm, which is a rare and pleasant combination.
Where this shows up
One idea, two worlds
Triangulation and trilateration
A robot that hears three ranges, or a camera rig that sees one point from several views, ends up with a small linear system whose right-hand side is built from the measurements. Solving it recovers a position in space, and the conditioning of that system decides how much a noisy range moves the estimate. The triangulation part of the geometry guide walks through exactly this solve.
Normal equations and reusable factors
Fitting a model means solving a linear system, and large models solve the same structured system over and over with different right-hand sides. Factoring once and reusing the factors is the difference between a training run that finishes and one that does not. The inference chapter shows how much of that arithmetic is dominated by the same matrix operations.
Further reading
- Grant Sanderson, "Inverse matrices, column space and null space", Essence of Linear Algebra, 3Blue1Brown — the column-space picture of when A x = b can be solved.
- Gilbert Strang, 18.06 Linear Algebra, MIT OpenCourseWare — Lectures 1–4, where elimination, back-substitution and the L U factorisation are developed in full.
- Immersive Math, Chapter 4: Solving systems of linear equations — elimination and the row picture, in a draggable textbook.
- Sheldon Axler, Linear Algebra Done Right, chapter 3 — the same material stated as linear maps and invertibility.