Elimination Turns Geometry into an Algorithm

What This Concept Is

Linear algebra begins with systems of linear equations, but the real object is not the list of equations. It is the structure that survives legal rewriting. Three geometries can sit on top of the same algebra: rows as hyperplanes that intersect, columns as vectors that combine to hit $b$, and a matrix as a function $x \mapsto Ax$. Elimination is the bridge that turns all three into a single mechanical procedure.

Gaussian elimination uses three row operations to transform a system into a simpler equivalent one: swap two rows, scale a row by a nonzero constant, or add a multiple of one row to another. These moves preserve the solution set while exposing the pivot structure -- the leading nonzero entries after reduction. Pivots tell you, without guessing, whether the system has a unique solution, infinitely many solutions, or no solution. They also let you read off rank, nullity, and the column space basis.

Distinguish elimination from its neighbors. Cramer's rule computes each variable by a determinant ratio; elegant but numerically poor and slow ($O(n^4)$ naïvely, $O(n!)$ from the definition). Matrix inversion gives $x = A^{-1}b$; it does more work than needed and is less stable than forward-then-back-substitution. Iterative methods (Jacobi, Gauss-Seidel, conjugate gradient, covered later in the module) sacrifice exactness for scalability when $A$ is huge and sparse. Elimination sits between symbolic elegance and iterative pragmatism: exact on paper, and the template for the $LU$ factorization used in every dense linear solver you will ever touch.

Elimination is also the procedural heart of three other operations you will meet later. Computing rank is "count pivots." Inverting a matrix is "run elimination on $[A \mid I]$ and read off $[I \mid A^{-1}]$." Computing a determinant is "track the sign and magnitude of the pivot product." One algorithm, four jobs.

The habit the procedure trains is to stop treating equations as separate facts and start treating them as one coupled object. Every row operation is a legal rewrite of the whole system. The formal end-state is the reduced row echelon form (RREF): every pivot is $1$, every pivot column is clean above and below, and free columns express their data as explicit coefficients. RREF is unique for a given matrix (the elimination path is not), and that uniqueness is what lets you read rank, nullity, and particular-plus-homogeneous solution structure without ambiguity.

The structure that comes out -- pivots, free variables, consistency -- matters more than any specific numerical solution. If you remember only one sentence from this page, it is that: elimination is how geometry becomes an algorithm, and the algorithm's output is a description of a solution space, not a single point. Write the geometry ($Ax = b$), mechanize the algebra (row ops on $[A \mid b]$), read the structure (pivots, free columns, inconsistent rows). That loop is reusable for every system you will solve by hand, and it is the faithful mental model for every library call that does the same in floating point.

Why It Matters Here

This module keeps returning to the question, "What can a matrix do, and what can it not do?" Elimination is the first serious answer. It gives you a constructive way to solve $Ax=b$, the first operational meaning of rank, the first encounter with nullspace and free variables, and the bridge from geometry to computation.

Without stable elimination habits, later topics such as basis, least squares, and eigen-analysis become symbolic theater. Every later factorization -- $LU$, $QR$, eigendecomposition, SVD -- is in some sense a structured variant of "eliminate and keep track of what you did."

The same thinking drives the forward pass of sparse linear solvers in computational physics, the pivot selection in the simplex method for linear programming, and the reduction phase of symbolic computer-algebra systems. If you understand elimination deeply, you already understand a third of what a numerical-linear-algebra engineer does every day.

Concrete Examples

Example 1 -- inconsistent system. Consider

$$\begin{pmatrix} 1 & 1 & 1 \ 2 & 3 & 5 \ 1 & 2 & 4 \end{pmatrix} \begin{pmatrix} x \ y \ z \end{pmatrix} = \begin{pmatrix} 4 \ 11 \ 9 \end{pmatrix}.$$

Apply $R_2 \leftarrow R_2 - 2R_1$ and $R_3 \leftarrow R_3 - R_1$:

$$\begin{pmatrix} 1 & 1 & 1 & | & 4 \ 0 & 1 & 3 & | & 3 \ 0 & 1 & 3 & | & 5 \end{pmatrix}.$$

Then $R_3 \leftarrow R_3 - R_2$ produces a row $\begin{pmatrix} 0 & 0 & 0 & | & 2 \end{pmatrix}$, which says $0=2$. The system is inconsistent. Geometrically, the three planes have no common point. Structurally, $\text{rank}(A) = 2$ but $\text{rank}([A \mid b]) = 3$, and the Rouché-Capelli theorem tells you that unequal ranks means no solution.

Example 2 -- one free variable. Consider

$$A = \begin{pmatrix} 1 & 2 & -1 \ 2 & 4 & -2 \ 1 & -1 & 3 \end{pmatrix}, \quad b = \begin{pmatrix} 1 \ 2 \ 7 \end{pmatrix}.$$

After $R_2 \leftarrow R_2 - 2R_1$, row 2 becomes zero (the second equation was a duplicate of the first). After $R_3 \leftarrow R_3 - R_1$,

$$\begin{pmatrix} 1 & 2 & -1 & | & 1 \ 0 & 0 & 0 & | & 0 \ 0 & -3 & 4 & | & 6 \end{pmatrix}.$$

After a row swap and $R_3 \leftarrow -\tfrac{1}{3} R_3$ you get pivots in columns 1 and 2 and one free variable $z$. Back-substitution yields $y = -2 + \tfrac{4}{3}z$ and $x = 1 - 2y + z = 5 - \tfrac{5}{3}z$.

The solution set is the line $(5, -2, 0) + z,(-\tfrac{5}{3}, \tfrac{4}{3}, 1)$. Notice that the particular solution $(5, -2, 0)$ lives in the row space of $A$, and the direction vector $(-\tfrac{5}{3}, \tfrac{4}{3}, 1)$ lives in the nullspace -- a preview of the fundamental-subspaces picture.

Example 3 -- $LU$ stored alongside elimination. For

$$A = \begin{pmatrix} 2 & 1 & 1 \ 4 & 3 & 3 \ 8 & 7 & 9 \end{pmatrix}$$

run elimination: $R_2 \leftarrow R_2 - 2R_1$, $R_3 \leftarrow R_3 - 4R_1$, then $R_3 \leftarrow R_3 - 3R_2$. Record the multipliers $(2, 4, 3)$ in the lower triangle and the residual upper rows in $U$:

$$L = \begin{pmatrix} 1 & 0 & 0 \ 2 & 1 & 0 \ 4 & 3 & 1 \end{pmatrix}, \quad U = \begin{pmatrix} 2 & 1 & 1 \ 0 & 1 & 1 \ 0 & 0 & 2 \end{pmatrix}.$$

You can verify $LU = A$. This is the payoff of doing elimination once: future solves against new right-hand sides cost only two $O(n^2)$ triangular substitutions instead of a fresh $O(n^3)$ reduction.

Example 4 -- partial pivoting and its limits. In Example 3, the first pivot is chosen from row 3 because 8 has largest magnitude in column 1. Continue choosing the largest available magnitude at each stage and track the permutation consistently in $PA=LU$. Partial pivoting bounds multiplier magnitudes by one; it does not prevent growth in the evolving matrix or guarantee small forward error. Backward-error analysis also depends on the growth factor, and forward error additionally depends on conditioning. See the growth-factor explanation by Nick Higham.

Common Confusion / Misconceptions

"Row operations change the system." They change its appearance, not its solution set. Each operation is invertible and preserves the affine solution variety. They do not preserve the column space, which is why you read column-space bases from the original matrix, not the reduced one.

"Free variables can be chosen without specifying an ordering." In RREF with fixed column order, nonpivot columns identify free variables canonically. Other parameterizations are possible: column permutations or choosing another independent column set can change which coordinates serve as parameters. State that choice explicitly.

"Rank counts nonzero rows in the original matrix." Rank is revealed after row reduction, by counting pivots. Three nonzero rows in the original can still have rank 1 if they are scalar multiples.

"Forming the inverse is the default solve." For a nonsingular square system, factor and solve directly. Explicit inversion usually adds work and storage when only its action on a vector is needed. It is useful in some symbolic or specialized tasks, but neither a universal speed ratio nor an unconditional accuracy ranking applies.

"Elimination always succeeds without row exchanges." A zero candidate pivot may require exchanging rows or moving to a later column. Numerical pivoting uses magnitudes and a stated tolerance policy; library APIs expose permutations in different forms. Do not infer exact rank from a single tiny floating-point pivot.

"RREF depends on which row operations I chose." The sequence of row operations is not unique, but the RREF itself is: two different students who both fully reduce the same matrix will produce the same final matrix (up to zero rows in the same positions). That uniqueness is a small theorem, and it is why "pivot columns" and "free columns" are well-defined independent of process.

How To Use It

When solving a system:

1. Write the augmented matrix $[A \mid b]$ immediately. Do not keep equations as prose.
2. Clear entries below each pivot systematically, going left to right.
3. Choose the largest available magnitude in the active pivot column (partial pivoting) in numerical work to control round-off.
4. Watch for contradictory rows $[0 ; 0 ; \cdots ; 0 \mid c]$ with $c \ne 0$; that ends the search.
5. Count pivots in the coefficient matrix $A$ for rank; nonpivot variable columns give nullity. A pivot in the augmented right-hand-side column signals inconsistency and is not a variable pivot.
6. Back-substitute to find a particular solution; parameterize free variables to describe the full solution set.
7. Interpret before celebrating arithmetic: is the system consistent? How many degrees of freedom? Which variables are determined by pivots?
8. If you need to solve repeatedly with the same $A$, capture the work as an $LU$ (or $PA = LU$) factorization and reuse it; do not re-run elimination per right-hand side.
9. If you need to classify the solution set rather than compute it, stop after obtaining RREF -- rank, nullity, and reachability read off directly.

Transfer to the calibration project

Use this concept to justify a result or reject an assumption in the calibration project. Name the matrix shape, objective, scalar field and available evidence before interpreting the result.

Check Yourself

1. What does a contradictory row mean geometrically, and what does it mean for $\text{rank}(A)$ versus $\text{rank}([A\mid b])$?
2. Why do pivot positions matter more than the raw coefficients after elimination?
3. When does a homogeneous system $Ax = 0$ have nontrivial solutions? Tie your answer to nullity.
4. Why is partial pivoting the default in floating-point implementations even when the mathematical pivot is nonzero?
5. How does elimination extend to rectangular $A$ (more columns than rows, or vice versa)?
6. Why is explicit inversion a worse default than $LU$ for solving $Ax=b$?
7. Given RREF, how do you write the full solution set as "particular + span of nullspace basis"?
8. Why is the uniqueness of RREF a theorem rather than something that follows from the definition?

Mini Drill or Application

1. Row-reduce the augmented matrix for $$x + 2y - z = 1, \quad 2x + 4y - 2z = 2, \quad x - y + 3z = 7$$ and state whether the solution is unique, infinite, or impossible. If solutions exist, write the solution set in parameter form.
2. Compute in NumPy: A = np.array([[1,2,-1],[2,4,-2],[1,-1,3]]); b = np.array([1,2,7]); np.linalg.lstsq(A, b, rcond=None). Compare the output vector to your hand-computed particular solution; explain why lstsq rather than np.linalg.solve is needed when $A$ is singular.
3. For a $4\times 4$ matrix of your choice with all nonzero pivots, run elimination by hand and record the multipliers into a matrix $L$. Verify that $LU$ reproduces $A$ and that your pivots sit on the diagonal of $U$.
4. Use SciPy: from scipy.linalg import lu; P, L, U = lu(A). Read off $P$ to understand which row swaps happened, and convince yourself $PA = LU$.
5. Explain in one sentence what the pivots told you before you solved completely.
6. Build a $5 \times 5$ Hilbert-like matrix $H_{ij} = 1/(i+j-1)$ and run elimination by hand for the first two columns. Notice how quickly the pivots shrink; this is the numerical foreshadowing of ill-conditioning (Cluster 5).

Read This Only If Stuck

Use the bounded reading guide and the Strang book index. The book link opens an index; find the named topic in your edition, read a small section and reconstruct one argument with the book closed.

Certify both outcomes of a solve

For A=[[1,2],[2,4]], b=(1,3), subtract twice the first equation from the second. The result 0=1 is an impossibility certificate. The same operation on the identity gives y=(-2,1): y^T A=0 but y^T b=1. If Ax=b existed, multiplying by y^T would force 0=1. This general argument makes the certificate independently checkable without trusting the reduction procedure.

For b=(1,2), one particular solution is (1,0), and every solution is (1,0)+t*(-2,1). Prove both directions: adding a null vector preserves Ax=b, and the difference of any two solutions lies in Null(A). Track coefficient pivots separately from the augmented column. Transfer: P1–P2 and the exact-system lab.

After an independent attempt, use practice feedback and model contracts to check your reasoning.