Mathematics
Gaussian Elimination for Solving Systems of Linear Equations
Quick fact
This method was named after Carl Friedrich Gauss, but the technique was known in Chinese mathematics as early as 179 AD, in a text called 'The Nine Chapters on the Mathematical Art'.
Why this is interesting
You've probably solved pairs of equations like 2x + y = 5 and x - y = 1 by cleverly combining them. But what if you had 10 equations with 10 variables? There has to be a systematic, foolproof way—and there is: Gaussian elimination.
Read the full explanation
Understanding Gaussian Elimination for Solving Systems of Linear Equations
Gaussian elimination is like playing a strategic game of reducing a messy system of equations into a neat, triangular form that can be solved easily. Imagine you have three equations with three unknowns. You first rewrite them as a matrix, a rectangular grid of numbers, where each row represents an equation and each column represents a variable (with a vertical bar for the constants). Then you use three allowed moves: swapping rows, multiplying a row by a non-zero number, and adding a multiple of one row to another. These moves are like legal chess moves—they don't change the solution, but they can change how the board looks. Your goal is to create zeros below a diagonal of 'pivots', like stairs. Once you have that, the last equation has only one variable, so you solve it, then substitute upward to find the others. That final step is called back substitution. This systematic process is what makes it reliable, even for hundreds of equations.
A deeper explanation
The power of Gaussian elimination lies in its algorithm and the concept of equal operations. Elementary row operations correspond to legal algebraic manipulations on the original system: swapping equations, multiplying both sides by a constant, and combining equations. Because these operations are reversible, the new system has exactly the same solution set. The algorithm's goal is to achieve row-echelon form, where each row's leading coefficient is progressively to the right of the one above, and below the leading coefficients are zeros. This structure makes the system triangular, enabling back substitution. Gaussian elimination is not just a manual technique; it's the foundation of how computers solve linear systems. By counting the operations, we see it takes roughly O(n³) steps for an n×n system, which is why optimizing it matters. The method also reveals when a system has no solution (if you get a contradictory row like 0=1) or infinitely many solutions (if a variable is free). This understanding is essential for matrix factorization, which makes solving many systems with the same coefficient matrix even faster.