Skip to main content

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 changes the factors, not the answer. Re-run the Example 3 matrix but swap rows 1 and 3 before elimination (because $|8| > |2|$, partial pivoting would choose row 3 first). The resulting factorization is $PA = LU$ with $P$ the permutation matrix encoding the swap; the computed $x$ is identical up to floating-point noise, but the multipliers stored in $L$ are all $\le 1$ in absolute value, which is exactly the numerical guarantee that prevents the fabricated rounding errors of unpivoted elimination. This is why LAPACK always returns $P, L, U$: bounded multipliers bound the backward error.

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.

"A free variable is any variable I feel like solving for." A variable becomes free only after pivot structure is known. Free = non-pivot column; bound = pivot column. You cannot rename these by preference; the choice is forced by the reduction.

"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.

"Inverting $A$ and computing $A^{-1}b$ is a good default solve." It is usually the wrong default: it costs roughly three times the work of $LU$ forward/back-substitution and is less numerically stable. Use elimination or $LU$; reserve $A^{-1}$ for theoretical arguments, never for a production solve.

"Elimination always succeeds without row exchanges." Not even close. A zero in the pivot position forces a swap, and a near-zero pivot forces one for numerical safety. Real implementations apply partial pivoting (swap in the largest available row) every step. The factorization then becomes $PA = LU$ with a permutation matrix $P$, which NumPy and SciPy surface by default.

"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 pivot (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 $=$ rank; count free columns $=$ nullity; they sum to the number of columns.
  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 / Where This Shows Up Later​

  • S2 (algorithms & data structures): Elimination is the template for Gauss-Jordan reduction in matrix-form dynamic programming. Transitive closure over an adjacency matrix (Warshall's algorithm) is boolean-semiring elimination; Floyd-Warshall is tropical-semiring elimination.
  • S4 (computer organization): Dense $LU$ is the canonical BLAS/LAPACK benchmark; cache-blocking decisions are shaped by blocked elimination kernels, and SIMD/AVX instructions exist partly to accelerate inner loops of forward substitution.
  • S5 (databases & queueing): Solving stationary distributions of Markov chains uses elimination on $(P - I)^T$ plus a normalization row; join-graph optimization uses elimination-like order selection.
  • S7 (architecture): Dependency matrices between services reduce via elimination-style transitive closure to reveal coupling and layering violations.
  • S8 (ranking & graphs): PageRank's linear system $(I - \alpha P^T)\pi = (1-\alpha)v$ is solved by elimination for small $n$ and by iterative variants for web scale -- both trace back to the row-reduction mindset.
  • Phase 7 (ML): The normal equations $A^TA,\hat{x} = A^T b$ in linear regression are solved by Cholesky or $LU$; the forward/backward pass of a linear layer is block elimination in disguise; Kalman filter updates rely on triangular solves.
  • Numerical libraries: numpy.linalg.solve wraps LAPACK's gesv (LU with partial pivoting); scipy.linalg.lu_factor and lu_solve expose the factorization for reuse. The elimination you do by hand is exactly what those routines do in double precision.

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​