Skip to content
Tutorials Center
My learning

Topics

Lesson 193 of 225 ยท Math and Bit Manipulation

Gaussian Elimination and Linear Systems

Solve linear systems with Gaussian elimination in Python: exact fractions, partial pivoting, determinants, modular arithmetic and the XOR basis over GF(2).

A linear system is a set of equations such as 2x + y = 5 and x - y = 1. Solving one by hand means adding multiples of one equation to another until each variable can be read off. Gaussian elimination is that same procedure written as an algorithm, and it is the workhorse behind circuit analysis, least squares, computer graphics and many counting problems.

In this lesson you will solve A x = b exactly with fractions, see why floating point needs pivoting, compute determinants, work modulo a prime, and finally meet the version over bits that powers the XOR basis from bit tricks. The cost is O(n^3) for an n by n system.

The idea: row operations

Write the system as an augmented matrix: the coefficients of A with b glued on the right. Three row operations never change the solution set:

  1. swap two rows,
  2. multiply a row by a non-zero number,
  3. add a multiple of one row to another.

The goal is an upper-triangular matrix (row echelon form). For each column, pick a row with a non-zero entry (the pivot), move it up, and subtract multiples of it from the rows below so that the column becomes zero under the pivot. Then solve from the bottom row upward (back substitution).

flowchart LR
  A["Augmented matrix [A | b]"] --> B["For each column: choose pivot row"]
  B --> C["Swap pivot row into place"]
  C --> D["Eliminate entries below pivot"]
  D --> E["Upper-triangular form"]
  E --> F["Back substitution"]

The forward phase makes zeros below the diagonal, the backward phase reads the answer.

Exact solving with fractions

Python's fractions.Fraction stores numerators and denominators as integers, so there is no rounding at all. That is perfect for learning and for small exact problems.

Python Gaussian elimination with Fraction

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop structure is three nested loops of length n, so the time is O(n^3) and the memory O(n^2). With fractions the numbers can grow, but Python integers never overflow.

Floating point and partial pivoting

With float the same code can fail badly. If a pivot is tiny, dividing by it creates huge multipliers that swamp the other numbers. The cure is partial pivoting: in each column pick the row with the largest absolute value as pivot, not just any non-zero one.

Python Why pivoting matters

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without pivoting the first multiplier is 1e20, and the small coefficient information is lost, so x comes out wrong. With pivoting the rows are swapped first and the answer is accurate. In practice use numpy.linalg.solve, which does this for you, and learn the algorithm for interviews and for exact or modular problems.

A system can have no solution (inconsistent rows such as 0 = 5), exactly one, or infinitely many (free variables). After elimination, count pivots: fewer pivots than unknowns means free variables, and a row that reads 0 ... 0 | non-zero means no solution.

Determinants for free

Elimination also gives the determinant: the product of the pivots, with the sign flipped once for every row swap. Adding a multiple of one row to another does not change it.

Python Determinant with elimination

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A nonzero determinant means the matrix is invertible and the system has exactly one solution.

Working modulo a prime

Many counting problems ask for answers modulo p = 998244353 or similar. Division becomes multiplication by a modular inverse, found with pow(x, -1, p) or pow(x, p - 2, p) (see number theory). There are no rounding errors, so any non-zero entry is as good a pivot as any other.

Python Solving a system modulo p

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This version also clears the entries above the pivot (Gauss-Jordan), so no back substitution is needed: the last column is the answer.

Over bits: GF(2) and the XOR basis

If every number is 0 or 1 and addition means XOR, you work in GF(2). Elimination is the same, and each row can be packed into a Python integer, so a row operation is a single ^. A system of n equations over bits then costs about O(n^3 / 64) with machine words.

Python Linear system over GF(2) with integers as rows

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The XOR basis from the bit-trick lessons is the same elimination without a right-hand side: it keeps one row per leading bit, and asks "is this number a XOR of earlier ones?" by trying to reduce it to zero. Lights-out puzzles and many "choose a subset with XOR equal to k" problems are linear systems over GF(2).

Complexity and cautions

Variant Time Notes
Elimination, n by n O(n^3) back substitution adds only O(n^2)
Determinant O(n^3) product of pivots and sign of swaps
Over GF(2) with bitmasks about O(n^3 / w) w is the word size, 64 in C-like languages
Matrix is sparse or banded much less specialised solvers exist

Common mistakes:

  • Forgetting to swap in a non-zero pivot, which divides by zero.
  • Using exact == comparisons on floats; compare with a tolerance such as abs(x) < 1e-9.
  • Using fractions on large systems, where numerators grow quickly; go modular instead when the question allows it.
  • Forgetting that modular elimination needs a prime modulus (or at least inverses of every pivot).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the time complexity of Gaussian elimination on an n by n system?

    For each of n columns you update up to n rows with up to n entries each, which is n times n times n operations.
  2. 2. Why does partial pivoting choose the entry with the largest absolute value?

    Dividing by a tiny pivot creates huge multipliers that swamp the other numbers in floating point. A large pivot keeps every multiplier at most 1 in size.
  3. 3. A 3x3 elimination used two row swaps and produced pivots 2, 3 and 4. What is the determinant?

    The product of the pivots is 24, and two swaps flip the sign twice, which restores the original sign.
  4. 4. How is a row operation over GF(2) done when rows are packed into integers?

    Addition over GF(2) is XOR, so adding one equation to another is a single ^ on the two integers.

Summary

  • Gaussian elimination turns [A | b] into triangular form with row swaps and row additions, then back-substitutes. It costs O(n^3).
  • Use Fraction for exact answers, partial pivoting for floats, and modular inverses for prime moduli.
  • The determinant is the product of pivots times the sign of the swaps; zero means the system is singular.
  • Fewer pivots than unknowns means free variables (many solutions); a row 0 = non-zero means no solution.
  • Over GF(2), rows fit in integers and the XOR basis is the same algorithm.

Next: Fast Doubling Fibonacci and Newton's Method