How Gaussian Elimination Solves Systems of Linear Equations

This article explains how Gaussian elimination systematically solves systems of linear equations in computational mathematics. It breaks down the algorithm into its core phases: translating equations into an augmented matrix, applying elementary row operations to achieve row echelon form through forward elimination, and executing back substitution to isolate the unknown variables. Finally, it addresses how computers use pivoting to maintain numerical stability during these calculations.

1. Constructing the Augmented Matrix

Gaussian elimination begins by stripping away the variables to focus purely on the numerical data. A system of linear equations is normally written as \(Ax = b\), where \(A\) represents the coefficients, \(x\) represents the unknown variables, and \(b\) represents the constants.

To prepare the system for computation, the coefficients and constants are combined into a single grid called an augmented matrix, denoted as \([A|b]\). Each row in the matrix corresponds to an equation, and each column corresponds to a specific variable, with the final column holding the constants from the right side of the equals sign.

2. The Rules: Elementary Row Operations

To solve the matrix without changing the fundamental values of the unknown variables, the algorithm relies on three permitted actions known as elementary row operations:

  • Row Swapping: Interchanging the positions of any two rows.
  • Scalar Multiplication: Multiplying all entries in a single row by a non-zero constant.
  • Row Addition: Adding a multiple of one row to another row.

Computers can execute these array manipulations rapidly, applying them iteratively to simplify the matrix.

3. Forward Elimination

The primary goal of forward elimination is to transform the augmented matrix into "row echelon form" (an upper triangular matrix). In this form, all numbers below the main diagonal are zeros. The algorithm achieves this systematically, working from the top row to the bottom row, and from the left column to the right column:

  1. Identify the Pivot: The algorithm selects the first non-zero number in the top row, known as the pivot.
  2. Eliminate Below the Pivot: Using row addition, the algorithm multiplies the pivot row by a specific ratio and subtracts it from the rows beneath it. This turns every number directly below the pivot into a zero, effectively eliminating that variable from the lower equations.
  3. Move Diagonally: The algorithm moves down one row and right one column to find the next pivot, repeating the elimination process for all rows beneath this new pivot.

This process continues until the matrix forms a staircase pattern of zeros in the bottom-left corner.

4. Back Substitution

Once the matrix is in row echelon form, the system is easily solvable. The bottom row now contains only one unknown variable, which can be solved via simple division (e.g., \(3z = 9\) becomes \(z = 3\)).

The algorithm then initiates back substitution, working from the bottom row up to the top:

  1. It takes the newly found value from the bottom row and substitutes it into the equation in the row directly above it.
  2. It solves that row for its single remaining unknown variable.
  3. It repeats this upward cascade until all variables are solved.

(Note: A variation called Gauss-Jordan elimination skips back substitution by continuing row operations upward until the matrix is in "reduced row echelon form," where the main diagonal consists only of ones, and all other entries are zeros).

5. Computational Considerations: Pivoting and Complexity

In theoretical mathematics, Gaussian elimination is flawless. In computational mathematics, however, computers must deal with finite memory and floating-point rounding errors.

If a pivot number is zero, the algorithm fails because it cannot divide by zero. Furthermore, if a pivot is a very small number close to zero, dividing by it can amplify rounding errors, leading to wildly inaccurate results.

To prevent this, computational algorithms use partial pivoting. Before eliminating a column, the computer scans all the values in that column (from the current row down) and swaps the current row with the row containing the largest absolute value. Using the largest possible number as the pivot ensures numerical stability and minimizes rounding errors.

In terms of computational efficiency, Gaussian elimination requires roughly \(\frac{2}{3}n^3\) arithmetic operations to solve a system of \(n\) equations. While \(O(n^3)\) time complexity is computationally heavy for massive datasets, it remains the foundational baseline for solving dense linear systems in modern scientific computing.