Gaussian Elimination Solver

Linear Systems & Augmented Matrix Formulation

A system of $m$ linear equations in $n$ unknowns $x_1, x_2, \dots, x_n$ is expressed in standard scalar form as:

In matrix notation, this compacts to $A \mathbf{x} = \mathbf{b}$, where $A \in \mathbb{R}^{m \times n}$ is the coefficient matrix, $\mathbf{x} \in \mathbb{R}^n$ is the unknown column vector, and $\mathbf{b} \in \mathbb{R}^m$ is the constant vector. To perform simultaneous algebraic reduction without repeatedly writing variable names, linear algebra defines the augmented matrix $[A \mid \mathbf{b}]$:

For general matrix algebra operations including determinants and inversions, visit our Matrix Calculator.

The Three Elementary Row Operations

Gaussian elimination relies on three elementary row operations that transform an augmented matrix into an equivalent system having the exact same solution set:

The Forward Elimination Algorithm (REF)

The forward elimination phase processes columns sequentially from left to right to create an upper-triangular echelon matrix:

• Pivot Selection: At step $k$, examine column $k$ in rows $k, k+1, \dots, n$. The non-zero entry $a_{kk}$ serves as the pivot element.
• Row Swap: If $a_{kk} = 0$, swap row $k$ with a row below that contains a non-zero entry in column $k$.
• Sub-Diagonal Elimination: For each row $i > k$, compute the multiplier $m_{ik} = a_{ik} / a_{kk}$ and perform the row replacement: $$R_i \leftarrow R_i - m_{ik} R_k$$ This replaces all entries below the pivot $a_{kk}$ with exact zeros.
• Termination: Repeat for $k = 1, 2, \dots, n-1$. The resulting matrix is in Row Echelon Form (REF).

Partial Pivoting & Numerical Stability

In numerical linear algebra, standard Gaussian elimination without row reordering is numerically unstable in finite-precision arithmetic. If a pivot element $|a_{kk}|$ is extremely small, the multiplier $m_{ik} = a_{ik} / a_{kk}$ becomes enormous, causing catastrophic cancellation and roundoff magnification.

Partial Pivoting resolves this by finding the row $p \ge k$ that maximizes the absolute value:

Row $p$ is swapped into row $k$ before elimination begins. This guarantees that all multipliers satisfy $|m_{ik}| \le 1$, bounding error growth throughout the forward reduction.

The Back-Substitution Phase

Once the augmented matrix reaches upper-triangular echelon form $[U \mid \mathbf{c}]$, the bottom equation contains only the single variable $x_n$:

Working upward from $i = n-1$ down to $1$, each preceding variable is computed by substituting all previously determined unknowns into row $i$:

Back-substitution executes in $O(n^2)$ time, completing the solution vector without requiring full matrix inversion. For alternative algebraic solvers, our Systems of Equations Solver offers substitution and Cramer's rule comparisons.

Solution Classification: The Rouché-Capelli Theorem

The existence and uniqueness of solutions to $A\mathbf{x} = \mathbf{b}$ is fully governed by the Rouché-Capelli Theorem, which compares the rank of the coefficient matrix $A$ to the rank of the augmented matrix $[A \mid \mathbf{b}]$:

Engineering Applications: Circuits, Structures & Networks

Gaussian elimination is the computational engine inside finite element analysis (FEA), circuit simulators (SPICE), and structural load analyzers:

• Kirchhoff's Current & Voltage Laws (KCL / KVL): In electrical engineering, nodal analysis of a circuit containing $N$ nodes creates an $N \times N$ conductance matrix $G \mathbf{v} = \mathbf{i}$, solved directly via Gaussian elimination.
• Civil Engineering Truss Analysis: Evaluating tensile and compressive forces on structural bridge joints creates joint equilibrium matrices $K \mathbf{d} = \mathbf{F}$ balancing external dead/live loads against internal structural members.
• Chemical Reaction Balancing: Mass conservation for stoichiometric reactions forms a homogeneous linear system $A \mathbf{x} = \mathbf{0}$, resolved to integer ratios via row reduction.

Common Pitfalls & Computational Traps

• Dividing by Zero Pivot: Proceeding with row elimination when $a_{kk} = 0$ leads to division by zero. A row swap with a lower row having a non-zero entry in that column is strictly required before continuing.
• Premature Decimal Rounding: Converting fractions to decimals (e.g. $1/3 \approx 0.333$) during intermediate row operations accumulates severe truncation errors. Exact fraction arithmetic preserves algebraic purity.
• Forgetting to Operate on Constant Vector: Applying row operations solely to matrix $A$ while forgetting column vector $\mathbf{b}$ destroys the equivalence of the linear equations.