A linear system is a collection of linear equations in several unknowns. Writing it in matrix form as Ax = b transforms the problem into a question about matrices: is b in the column space of A, and if so, what are the weights? Row reduction answers both questions systematically, and the rank of the coefficient matrix determines whether the solution exists, whether it is unique, and what the solution set looks like.
What a Linear System Is
A linear system is a set of m equations in n unknowns where each equation is a linear combination of the unknowns equal to a constant:
a11x1+a12x2+⋯+a1nxn=b1
a21x1+a22x2+⋯+a2nxn=b2
⋮
am1x1+am2x2+⋯+amnxn=bm
"Linear" means no products of unknowns, no powers higher than 1, and no transcendental functions of unknowns. The expression 3x1−2x2+x3=7 is linear; the expression x1x2+x32=1 is not.
A solution is an assignment of values to x1,…,xn that satisfies every equation simultaneously. The solution set is the collection of all solutions. The central question is: what does this set look like?
Writing a System in Matrix Form
The entire system can be compressed into a single matrix equation:
Ax=b
where A is the m×n coefficient matrix with entry aij in row i, column j; x=(x1,x2,…,xn)T is the unknown vector; and b=(b1,b2,…,bm)T is the right-hand side.
Each row of A corresponds to one equation. Each column corresponds to one unknown. The matrix-vector product Ax is a linear combination of the columns of A weighted by the entries of x:
Ax=x1a1+x2a2+⋯+xnan
Asking whether Ax=b has a solution is therefore equivalent to asking whether b lies in the column space of A — whether b can be assembled from the columns using some choice of weights.
The Augmented Matrix
The augmented matrix packages the coefficient matrix and the right-hand side into a single object:
The vertical bar separates the coefficients from the constants but is purely notational — the augmented matrix is an m×(n+1) matrix on which row operations are performed. Every row operation on [A∣b] corresponds to a legal algebraic manipulation of the equations: swapping two equations, multiplying an equation by a nonzero scalar, or adding a multiple of one equation to another. None of these changes the solution set.
The augmented matrix is the object that Gaussian elimination operates on, and comparing its rank to the rank of A alone determines whether the system is consistent.
The Three Possible Outcomes
A linear system Ax=b has exactly one of three outcomes.
No solution: the system is inconsistent. The equations impose contradictory constraints — there is no x that satisfies all of them. In the augmented matrix, this manifests as a row of the form [00⋯0∣d] with d=0, representing the impossible equation 0=d.
Exactly one solution: the system is consistent and determined. There is a unique x satisfying all equations. This requires the coefficient matrix to have rank equal to n (the number of unknowns), leaving no free variables.
Infinitely many solutions: the system is consistent but underdetermined. The constraints do not pin down a single point — the solution set is a line, plane, or higher-dimensional flat parametrized by free variables.
There is no fourth option. A linear system never has exactly two solutions, or ten, or any finite number greater than one. The proof is simple: if x1 and x2 are both solutions with x1=x2, then x1+t(x2−x1) is a solution for every t∈R, producing infinitely many.
Geometric Interpretation
Each equation in a linear system defines a hyperplane in Rn. The solution set is the intersection of all m hyperplanes.
For two equations in two unknowns, each equation is a line in R2. Two distinct non-parallel lines meet at exactly one point — a unique solution. Parallel lines never meet — no solution. Coincident lines (the same line described twice) overlap entirely — infinitely many solutions.
For three equations in three unknowns, each equation is a plane in R3. Three planes can intersect in a point, along a line, or not at all. They can also coincide or be arranged so that each pair intersects but no point lies on all three — a triangular prism configuration that yields no solution.
In higher dimensions the geometry is harder to visualize but the classification persists. The rank of the coefficient matrix counts how many hyperplanes cut independently — each independent equation reduces the dimension of the intersection by one. If the rank is r and the system is consistent, the solution set has dimension n−r.
Elementary Row Operations
The three elementary row operations are the legal moves that transform one augmented matrix into another without altering the solution set.
Swapping two rows (Ri↔Rj) reorders the equations. Multiplying a row by a nonzero scalar (kRi→Ri) rescales an equation. Adding a multiple of one row to another (Ri+cRj→Ri) replaces one equation with a combination of two equations.
Each operation is reversible: a swap undoes itself, scaling by k is reversed by scaling by 1/k, and adding c times row j to row i is reversed by subtracting c times row j from row i. Reversibility guarantees that the solution set is unchanged — no solutions are created or destroyed.
Each row operation corresponds to left-multiplication by an elementary matrix. This algebraic interpretation connects the row-reduction algorithm to the theory of matrix factorization and invertibility. The full systematic application of row operations is Gaussian elimination.
Row Echelon Form and Reduced Row Echelon Form
Row operations aim to reduce the augmented matrix to a standard shape from which the solution can be read.
Row echelon form (REF) has a staircase pattern: the leading entry of each row is to the right of the leading entry of the row above, and all entries below each leading entry are zero. In REF, the solution is obtained by back substitution — solving from the bottom row upward.
Reduced row echelon form (RREF) goes further: each leading entry is 1 and is the only nonzero entry in its column. In RREF, the solution is visible by inspection — each pivot variable is already isolated.
The RREF of any matrix is unique. Different sequences of row operations always arrive at the same RREF. This uniqueness makes the pivot positions intrinsic to the matrix: the rank, the free variables, and the solvability verdict all follow from the pivot structure. The full treatment of both forms, including how to read solutions from each, is on the echelon form page.
Homogeneous Systems
The special case Ax=0 — where every right-hand side entry is zero — is called a homogeneous system. It is always consistent, since x=0 satisfies every equation. The question is whether nontrivial solutions exist.
Nontrivial solutions exist if and only if the rank of A is less than n. If the system has more unknowns than equations (n>m), nontrivial solutions are guaranteed — the rank cannot exceed m, which is less than n.
The solution set of a homogeneous system is the null space of A: a subspace of Rn with dimension n−rank(A). The superposition principle holds — any linear combination of solutions is again a solution — which is why the solution set has the clean structure of a vector space rather than an arbitrary collection of points.
When Does a Solution Exist? When Is It Unique?
The rank of A determines both existence and uniqueness of solutions to Ax=b.
Existence: a solution exists if and only if rank(A)=rank([A∣b]). This means b lies in the column space of A — appending it as an extra column does not introduce a new independent direction.
Uniqueness: if a solution exists, it is unique if and only if rank(A)=n. Full column rank means no free variables and a trivial null space, so the particular solution stands alone with no homogeneous component to add freedom.
When A is square (m=n) and det(A)=0, both conditions hold for every b: the system always has a unique solution, given by x=A−1b. When A is rectangular or singular, the analysis requires comparing ranks and identifying free variables. The full treatment, including overdetermined and underdetermined systems, is on the solvability page.
Solution Methods Beyond Row Reduction
Gaussian elimination is the most general and widely used method, but several alternatives exist for special cases.
Cramer's rule solves an n×n system by expressing each unknown as a ratio of determinants. It gives a closed-form solution but is computationally impractical for large n.
The inverse formula x=A−1b applies when A is square and invertible. It is elegant but rarely the most efficient approach — computing A−1 costs roughly three times as much as solving by elimination.
LU decomposition factors A into a lower triangular matrix L and an upper triangular matrix U. Once the factorization is computed, solving Ax=b reduces to two cheap triangular solves. This is the method of choice when multiple systems share the same coefficient matrix A but have different right-hand sides.
Iterative methods — Jacobi, Gauss-Seidel, conjugate gradient — generate a sequence of approximations converging to the solution. They are preferred for very large sparse systems where direct methods would require too much memory or time. These methods lie at the boundary between linear algebra and numerical analysis.