Engineering / Mathematics — Modules, Vector Spaces and Matrices
Solving Systems of Linear Equations
Solving linear systems over a field: consistency, the structure of the solution set, and modular methods for exact rational answers.
Executive summary
A linear system is consistent when the right-hand side lies in the image, and its solution set is then a coset of the kernel. Elimination decides consistency and produces a solution simultaneously.
Over the rationals, exact solving uses modular computation and rational reconstruction to avoid coefficient growth.
Learning objectives
- Determine consistency and describe the solution set.
- Solve by elimination on the augmented matrix.
- Apply the modular method for exact rational solutions.
01Consistency and solution structure
Solution set structure
The system Ax = b is consistent if and only if rank(A) = rank([A | b]).
When consistent, the solution set is x₀ + ker(A) for any particular solution x₀ — a coset of the kernel, of dimension equal to the nullity.
| rank(A) | rank([A|b]) | Outcome |
|---|---|---|
| r | r < n | Infinitely many solutions, a coset of dimension n − r |
| n | n | Unique solution |
| r | r + 1 | Inconsistent — no solution |
The rank condition is the first isomorphism theorem in practical form: b is reachable exactly when adding it to the columns does not increase the rank, that is, when it already lies in the image.
02Solving by elimination
Solve Ax = b
matrix A, vector b over a fielda particular solution and a kernel basis, or inconsistency- Form the augmented matrix [A | b].
- Reduce to row echelon form.
- If a row has all zeros in the A block but a non-zero entry in the b column, report inconsistent.
- Set every free variable to zero.
- Back-substitute to determine the pivot variables, giving a particular solution.
- Compute a kernel basis to describe the full solution set.
O(n³) field operations03Exact rational solving
Over the rationals, direct elimination causes severe coefficient growth. The modular method avoids it entirely.
Bound the answer
Use Cramer's rule with Hadamard's bound to bound numerators and denominators of the true solution.
Choose primes
Pick word-sized primes whose product exceeds twice the bound.
Solve modulo each prime
Run elimination in each F_p; all arithmetic is single precision.
Chinese remainder
Combine the modular solutions componentwise.
Reconstruct rationals
Apply rational reconstruction to each component.
Verify
Substitute back into the original system — cheap and complete.
The verification step is worth keeping even when the bound is rigorous. Substituting a candidate solution costs a matrix-vector product, far less than the solve, and catches both unlucky primes and underestimated bounds.
04Frequently asked questions
Why is the solution set a coset rather than a subspace?
Because it contains a particular solution that is generally non-zero, and the difference of any two solutions lies in the kernel. Only a homogeneous system, with b zero, has a subspace as its solution set.
How are the bounds obtained?
By Cramer's rule: each component is a ratio of determinants, and Hadamard's bound limits each determinant by the product of the row norms. This gives a rigorous, if pessimistic, bound.
Is the modular method always faster?
For large systems with small entries, substantially. For very small systems the overhead of multiple modular solves and reconstruction exceeds the direct cost, so implementations switch based on size.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 331-335.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.