Gaussian Elimination
Swap rows, scale a row, add a multiple of one row to another — none changes the solution set. March to echelon form; each PIVOT pins a variable, each pivotless column leaves a FREE variable. Unique solution, infinitely many, or none: the pivots decide.
The rank is the number of pivots — the true dimension of what the matrix can reach. For an matrix, (free variables) : a homogeneous system of rank always has a -parameter family of solutions.
and : the left sides are proportional, so either (same line — infinitely many solutions) or (parallel lines — none). Elimination makes the dichotomy mechanical.
Every engineering simulation, circuit solver, weather model, and structural analysis ends in a huge linear system, and Gaussian elimination (with clever pivoting) is how they are all solved. Its cost — about operations — is a number every computational scientist knows by heart.
The system reduces to rows , , . For which is it consistent? Work: the last row reads , so consistent only when — and then two pivots, two variables: a UNIQUE solution (, ). One glance at the echelon form settles existence, uniqueness, and the answer.
Proofs & Why It Matters
Row reduce (, rank ): pivot columns and free columns. Each free variable can be set to with the others , and back-substitution fills in the pivot variables — producing solutions of that are independent (each has a where the others have ).
Conversely every homogeneous solution is determined by its free-variable values, so these span: the null space has dimension exactly .
In echelon form, a row with reads : no solution. Otherwise, if every column has a pivot, back-substitution determines each variable uniquely: exactly one solution. Otherwise some column is pivot-free: its variable is free, and each of its infinitely many values extends to a solution. No fourth case exists.
Going Deeper: Explanations & Worked Problems
The method is fully mechanical. (1) Find the leftmost column with a nonzero entry; swap that entry's row to the top — it is the first PIVOT. (2) Subtract multiples of the pivot row from every row below, zeroing that column beneath the pivot. (3) Ignore the pivot row and repeat on the remaining rows.
The result is echelon form: pivots marching down and right, zeros below each. Then read off the verdict: a row , , means INCONSISTENT; otherwise count pivots — every column with a pivot pins a variable, every column without one donates a free parameter. Back-substitution finishes: solve the last pivot equation, substitute upward. The whole of solvability theory — unique/infinite/none, rank, dimension of the solution space — is a bookkeeping layer on this one procedure.
Solve , , .
Step 1 — clear column 1 below the pivot: : ; : .
Step 2 — clear column 2 below the new pivot: : .
Step 3 — echelon form reached with three pivots (): a unique solution exists.
Step 4 — back-substitute: from row 3, ; from row 2, so ; from row 1, .
Step 5 — verify in the ORIGINAL equations: ✓, ✓, ✓. The verification step costs ten seconds and catches nearly every slip.
Reduce .
Step 1: — row 2 was twice row 1, and elimination EXPOSES the dependence as a zero row. Step 2: . Echelon form: pivots in columns 1 and 2, none in column 3: rank .
Step 3 — the homogeneous solutions: is free; row 2 gives ; row 1 gives . So the null space is the LINE of multiples of , dimension — and rank–nullity checks: columns (rank) (nullity) ✓. Rank counts surviving information; nullity counts what the matrix destroys.