Engineering Fluency OS

Why This Matters

A system of linear equations is one of the most common structures in applied mathematics. When an engineer designs a circuit, the voltages and currents satisfy a system of linear equations. When a data scientist fits a regression model, the optimal parameters come from solving a linear system. When a game engine resolves collisions, it solves a system of constraint equations. The question is always the same: given a set of linear relationships, find the values that satisfy all of them simultaneously.

Gaussian elimination is the systematic algorithm for solving any system of linear equations. Instead of guessing or substituting, you perform a sequence of simple row operations -- swapping rows, scaling rows, and adding multiples of one row to another -- to reduce the system to a simpler form that you can solve by back-substitution. It is one of the most important algorithms ever invented.

The process works on an augmented matrix, which combines the coefficient matrix and the right-hand-side vector into a single table. The goal is to reach row echelon form, where the leading entry of each row is to the right of the one above it, creating a staircase pattern. From there, you read off the solution from bottom to top.

Define Terms

Visual Model

System of EquationsAx = b

Augmented Matrix[A | b]

Row OperationsSwap, Scale, Add

Row Echelon FormStaircase pattern

Reduced REFLeading 1s, zeros above

Back SubstitutionSolve bottom to top

SolutionUnique, infinite, or none

The full process at a glance. Click Start tour to walk through each step.

Gaussian elimination transforms a system into row echelon form through row operations, then solves by back substitution.

Code Example

Code

// Gaussian Elimination in JavaScript

function gaussianElimination(augmented) {
  // Clone the matrix
  const A = augmented.map(row => [...row]);
  const m = A.length;
  const n = A[0].length;

  // Forward elimination
  for (let col = 0; col < m; col++) {
    // Find pivot (partial pivoting)
    let maxRow = col;
    for (let row = col + 1; row < m; row++) {
      if (Math.abs(A[row][col]) > Math.abs(A[maxRow][col])) {
        maxRow = row;
      }
    }
    // Swap rows
    [A[col], A[maxRow]] = [A[maxRow], A[col]];

    // Eliminate below
    for (let row = col + 1; row < m; row++) {
      const factor = A[row][col] / A[col][col];
      for (let j = col; j < n; j++) {
        A[row][j] -= factor * A[col][j];
      }
    }
  }

  // Back substitution
  const x = new Array(m).fill(0);
  for (let i = m - 1; i >= 0; i--) {
    x[i] = A[i][n - 1];
    for (let j = i + 1; j < m; j++) {
      x[i] -= A[i][j] * x[j];
    }
    x[i] /= A[i][i];
  }
  return x;
}

// Solve: x + 2y = 5, 3x + 4y = 11
const aug1 = [[1, 2, 5], [3, 4, 11]];
console.log("Solution:", gaussianElimination(aug1)); // [1, 2]

// Solve: 2x + y - z = 8, -3x - y + 2z = -11, -2x + y + 2z = -3
const aug2 = [[2, 1, -1, 8], [-3, -1, 2, -11], [-2, 1, 2, -3]];
console.log("Solution:", gaussianElimination(aug2)); // [2, 3, -1]

Interactive Experiment

Try these exercises:

Solve the system x + y = 3, 2x - y = 0 by hand using row reduction. Verify with code.
Create a system with no solution (a contradiction). What does the augmented matrix look like after elimination?
Create a system with infinitely many solutions (a free variable). How does the row echelon form differ from the unique-solution case?
Swap the order of the equations in a system. Does the solution change? Why or why not?
Try a 4x4 system. How many row operations does it take? Can you see why Gaussian elimination is O(n^3)?

Quick Quiz

Coding Challenge

System Solver

Write a function called `solve(augmented)` that takes an augmented matrix (2D array where the last column is the right-hand side) and returns the solution vector. You may assume the system has a unique solution and no zero pivots. Implement forward elimination to get row echelon form, then back substitution to find the answer.

Loading editor...

Real-World Usage

Solving linear systems is one of the most computed operations on Earth:

Engineering: Structural analysis (finite element method) solves systems with millions of equations to determine stresses and deformations in bridges, buildings, and aircraft.
Machine learning: The normal equations for linear regression solve (A^T A)x = A^T b to find the best-fit parameters. Ridge regression adds regularization to the same system.
Computer graphics: Lighting calculations, mesh deformations, and cloth simulations all reduce to solving linear systems at each time step.
Economics: Input-output models (Leontief) use matrix equations to model how industries depend on each other. Solving the system predicts equilibrium prices.
Circuit analysis: Kirchhoff laws produce a system of linear equations. Solving it gives all the voltages and currents in the circuit.

Systems & Gaussian Elimination