What Is Gaussian Elimination?

The instinct is to guess, substitute, and get tangled, but what is Gaussian elimination? Gaussian elimination replaces that guesswork with a mechanical sequence of three allowed moves on the augmented matrix. You perform those moves until the matrix is in row‑echelon form (REF), then back‑substitute from the last row upward. The result is the solution set, unique, infinite, or none, read directly from the final matrix.

Gaussian elimination is a systematic method for solving systems of linear equations by transforming an augmented matrix into row‑echelon form (REF) and then back‑substituting. Newcomers most often mistake it for a single formula rather than a sequence of row operations (swap, scale, add) that must be applied in a specific order, and they forget that a zero pivot forces a row swap or the system is singular.

Gaussian elimination works by eliminating one variable at a time. Pick a pivot, the first non‑zero entry in the first column, and use row operations to create zeros below it. Move to the next column, choose a new pivot (it must be to the right of the previous pivot), and eliminate the entries below that one. Repeat until every row has either all zeros or a pivot that is the first non‑zero entry in that row.

At that point the matrix is in row‑echelon form. The solution appears by back‑substitution: solve the last equation for its variable, plug that value into the second‑last, and continue upward. The process is deterministic: given the same starting system and the same pivot choices, you get the same REF.

Three operations are allowed, and they never change the solution set of the system. The first is row switching (R_i ↔ R_j): swap two rows. This is safe because equations are unordered; swapping them does not change which values satisfy all of them simultaneously. The second is row multiplication (kR_i → R_i): multiply every entry in a row by a non‑zero constant k. This is safe because multiplying an equation by a non‑zero constant produces an equivalent equation, the same set of solutions. The third is row addition (R_i + kR_j → R_i): add a multiple of one row to another. This is safe because adding a multiple of one equation to another yields an equation that is a linear combination of the originals; every solution of the original system also satisfies the new one, and vice versa.

These three moves are the only ones you need. No dividing by zero, no multiplying by zero, no adding rows to themselves without a multiple. A zero pivot forces a row swap: if the entry in the pivot position is zero, swap with a row below that has a non‑zero in the same column. If no such row exists, the system is singular, either no solution or infinitely many, and the algorithm terminates with that information.

The method is named after the German mathematician Carl Friedrich Gauss (1777-1855), who used it extensively for astronomical calculations in the early 19th century. But the core idea is much older. The earliest known description of Gaussian elimination appears in the ancient Chinese text Jiuzhang Suanshu (Nine Chapters on the Mathematical Art), written around 179 CE, according to the historian Grcar in his 2011 article for the Notices of the AMS. The text solves systems of linear equations using a method equivalent to Gaussian elimination, with the coefficients arranged in a rectangular array and a process of subtracting multiples of one row from another.

Grcar also notes that the name “Gaussian elimination” was applied only in the 20th century. Gauss himself never called it that. The algorithm was later refined by Wilhelm Jordan for computer implementation, Gauss‑Jordan elimination, which continues the process to reduced row echelon form (RREF), but the fundamental sequence of row operations remains the same as the one from the Nine Chapters.

Engineering and Science

Gaussian elimination shows up wherever systems of linear equations appear. Engineers use it to analyse electrical circuits: Kirchhoff’s laws produce linear equations for currents and voltages. Structural engineers solve for forces in trusses and beams using equilibrium equations. In statistics, the method underpins least‑squares regression, where you solve the normal equations A^TAx = A^Tb for the coefficient vector. Computer graphics relies on it for computing transformations, projections, and camera calibration. Economists use it to model market equilibrium with supply and demand equations. The algorithm is the core of the LAPACK routine dgesv, which solves dense linear systems in production code.

Pivoting Strategies

Pivoting strategies, partial pivoting (swapping rows for the largest absolute value in the column) or complete pivoting (swapping rows and columns), are standard classroom and library techniques to reduce round‑off error.

For an n×n matrix, Gaussian elimination requires about (2/3)n³ arithmetic operations (multiplications and additions) for the forward elimination phase. Back‑substitution adds roughly n² operations. An 8×8 system needs a few hundred operations; a 1000×1000 system needs on the order of hundreds of millions of operations. This O(n³) complexity is the reason large systems are solved on computers, not by hand. The practical limit for hand‑checking with a calculator is about 5×5.