Gaussian Elimination

The systematic row-reduction procedure that solves linear systems and reveals rank and invertibility.

The procedure

Gaussian elimination transforms a linear system into an equivalent triangular one by repeatedly adding multiples of one row to another to create zeros below each pivot. This forward elimination phase reduces the matrix to row-echelon form; then back substitution solves for the unknowns from the last equation upward. It is the algorithm behind LU factorization.

Elementary row operations

• swap two rows
• multiply a row by a nonzero scalar
• add a multiple of one row to another

Each of these operations preserves the solution set, so the reduced system has exactly the same solutions as the original. They correspond to multiplying by invertible elementary matrices, which is why elimination can be recorded as a matrix factorization.

Reading off the answer

After reduction, the pivots (the leading nonzero in each row) tell the story. The number of pivots is the rank. If a pivot appears in the augmented column but not the coefficient columns, the system is inconsistent. Columns without pivots correspond to free variables, signaling infinitely many solutions. Continuing to reduced row-echelon form isolates each pivot variable directly.

Pivoting and cost

Choosing the largest available entry as each pivot (partial pivoting) keeps the multipliers small and the computation numerically stable. The whole procedure costs on the order of n^3 operations for an n-by-n system, the same as LU factorization, of which it is the computational core.

import numpy as np
# Augmented matrix, then one elimination step by hand
M = np.array([[2.0, 1.0, 5.0], [4.0, 3.0, 11.0]])
M[1] -= (M[1,0]/M[0,0]) * M[0]   # zero the (1,0) entry
print(M)   # now upper triangular

Understanding elimination clarifies why factorization-based solvers behave as they do, including where pivoting protects accuracy in the large systems that arise from discretized physics.