Systems of Linear Equations and Row Reduction

A single linear equation in the variables $x_{1}, \dots, x_{n}$ is one that can be written as

a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} = b,

with coefficients $a_{1}, \dots, a_{n}$ and constant $b$ known in advance.¹ It is linear because each variable appears alone, scaled by a constant: no products $x_{1} x_{2}$ , no powers $x_{1}^{2}$ , no $x_{1}$ , no transcendental functions of the unknowns. A system of linear equations (a linear system) is a finite collection of such equations in the same variables. A solution is a list $(s_{1}, \dots, s_{n})$ that makes every equation true at once, and the solution set is the set of all solutions. Two systems are equivalent when they have the same solution set.

Row reduction is a mechanical procedure that returns the complete solution set of any system and, before it finishes, reads off whether that set is empty, a single point, or infinite.

The geometry of two equations

For two equations in two variables, each equation is a line in the plane, and a solution is a point on both lines. Two lines in a plane fall into exactly three positions, and those exhaust the possibilities for the system.

The three ways two lines can sit in the plane: crossing once, never, or everywhere. A linear system inherits exactly these three outcomes.

The middle panel is two parallel lines; the system is inconsistent. The right panel is two names for the same line; every point on it solves the system. This trichotomy holds for any linear system, not only in two dimensions.

In three variables each equation is a plane, and a solution is a point common to all the planes; two planes meet in a line, a third can miss that line (no solution), pierce it (one point), or contain it (a whole line of solutions). The count of outcomes does not change. Row reduction proves the trichotomy; the argument follows once the algorithm is in hand.

In R^3 each equation is a plane; three planes can meet at a single point (one solution) or share a common line (infinitely many solutions).

Matrix notation

The names of the variables carry no information once the equations are lined up; only the coefficients and the right-hand sides matter. Record them in a rectangular array. For the system

x_{1} - 2 x_{2} + x_{3} 2 x_{2} - 8 x_{3} 5 x_{1} - 5 x_{3} = 0 = 8 = 10

the coefficient matrix and the augmented matrix are

105 - 2 20 1 - 8 - 5, 105 - 2 20 1 - 8 - 5 0810 .

The augmented matrix appends the constants as one extra column, separated conceptually by the equals signs. A matrix with $m$ rows and $n$ columns has size $m \times n$ (rows first). The augmented matrix above is $3 \times 4$ . Solving the system will be a sequence of operations on the rows of this array.

Elementary row operations

The elimination strategy is to trade the system for an equivalent one that is easier to read. Three operations on the equations do this without disturbing the solution set, and each has a matching operation on the rows of the augmented matrix.

Two matrices are row equivalent if a sequence of these operations turns one into the other. Each operation is reversible — an interchange is undone by the same interchange, a scaling by $c$ by a scaling by $1/ c$ , and a replacement of row $j$ by row $j + c (row i)$ by adding $- c (row i)$ back. That reversibility is what justifies elimination.

Any solution of the original system satisfies each new equation (each new equation is a combination of old ones), and because the operations are reversible, any solution of the new system satisfies the old. Neither direction loses or invents a solution.

Echelon forms

The triangular shape above is a special case of a pattern that works for any matrix, square or not. Call a row nonzero if it has at least one nonzero entry, and the leading entry of a nonzero row its leftmost nonzero entry.

Property 2 forces the leading entries into a descending staircase, moving down and to the right; property 3 empties the space beneath each step. In the figure below a filled accent square marks a leading entry (a pivot), a gray dot marks an arbitrary entry (any value, including zero), and $0$ marks a forced zero.

An echelon staircase: leading entries step down and to the right, with zeros below each and only zeros in the bottom rows.

A matrix can have many echelon forms (different operations reach different ones), but its reduced echelon form is uniquely determined.

Because the reduced form is unique, so are the positions of its leading $1$ s, and those positions are the same in every echelon form of the matrix. That common set of positions carries a name.

The row reduction algorithm

The procedure has a forward phase that produces an echelon form and a backward phase that produces the reduced echelon form. Reading the forward phase alone already answers the existence and uniqueness questions.

Algorithm:

\textsc{RowReduce}(A)

— Gaussian elimination to reduced echelon form

1
// forward phase
2
$r \gets 1$
3
for each column $c$ from left to right do
4
if column $c$ has a nonzero entry in rows $r, \dots, m$ then
5
choose a pivot row $p \ge r$ with $A[p,c] \ne 0$
6
interchange rows $r$ and $p$
7
for each row $i$ below $r$ do
8
add $-A[i,c]/A[r,c]$ times row $r$ to row $i$
zeros below the pivot
9
$r \gets r + 1$
10
// backward phase
11
for each pivot, from rightmost to leftmost do
12
scale its row so the pivot becomes $1$
13
add multiples of that row to the rows above to zero the rest of its column
14
return the reduced echelon matrix

Two remarks on choices inside the loop. The pivot row is any row with a nonzero entry in the pivot column; hand computation prefers a $1$ to avoid fractions, while a numerical library chooses the entry of largest absolute value (partial pivoting) to limit rounding error.³ The forward phase does the bulk of the arithmetic — about $2 n^{3} /3$ floating-point operations for an $n \times (n + 1)$ system, against at most $n^{2}$ for the backward phase.⁴

Worked example. Row reduce to reduced echelon form and locate the pivot columns:

033 3 - 7 - 9 - 6 812 6 - 5 - 9 486 - 5 915 .

The leftmost nonzero column is column 1. Interchange rows to bring a nonzero entry to the top, here swapping rows 1 and 3, then clear below the pivot:

330 - 9 - 7 3 128 - 6 - 9 - 5 6 684 159 - 5 ⟶ 300 - 9 23 12 - 4 - 6 - 9 46 624 15 - 6 - 5 .

The next pivot is in column 2; clear the entry below it to finish the forward phase and reach an echelon form,

300 - 9 20 12 - 4 0 - 9 40 621 15 - 6 4,

with pivots $3, 2, 1$ in columns 1, 2, 5. The backward phase scales each pivot to $1$ and clears the column above it, giving the reduced echelon form

100010 - 2 - 2 0 320001 - 24 - 7 4 .

Columns 1, 2, 5 are the pivot columns; columns 3, 4 are not.

Reading the solution set

Once the augmented matrix is in reduced echelon form, the solution set falls out. Variables split by the columns they sit in.

For the reduced matrix just computed, the pivots lie in columns 1, 2, 5, so $x_{1}, x_{2}, x_{5}$ are basic and $x_{3}, x_{4}$ are free. Reading the last column as constants, the associated system is

x_{1} - 2 x_{3} + 3 x_{4} x_{2} - 2 x_{3} + 2 x_{4} x_{5} = - 24 = - 7 = 4.

Solving each basic variable in terms of the free ones gives the general solution,

⎩ ⎨ ⎧ x_{1} = - 24 + 2 x_{3} - 3 x_{4}, x_{2} = - 7 + 2 x_{3} - 2 x_{4}, x_{3} free, x_{4} free, x_{5} = 4.

Free variables are parameters: each choice of $(x_{3}, x_{4})$ produces one solution, and the solution set is swept out as they range over all values. With no free variables the solution is a single point; with at least one, there are infinitely many. This form — every basic variable expressed through free parameters — is a parametric description of the solution set, and we adopt the convention of always using the free variables as the parameters.

Existence and uniqueness

The forward phase alone decides both fundamental questions, because they depend only on the pattern of pivots, not on the arithmetic of the backward phase.

A row $[0 \dots 0 ∣ b]$ with $b \neq = 0$ is the equation $0 = b$ , a flat contradiction, so its presence means no solution. Its absence means every nonzero row carries a basic variable, and either all variables are basic (one solution) or some variable is free (a parameter, hence infinitely many). This also proves the three-outcomes theorem: the pivot pattern permits only these cases.

The pivot pattern of the augmented matrix decides everything: a pivot in the last column blocks consistency; free variables among the rest force infinitely many solutions.

The three checks are cheap: run the forward phase, glance at the last column, count the pivots against the number of variables.

Pivot situation	Consistency	Solution set
Pivot in the augmented column	inconsistent	empty
No such pivot; pivot in every variable column	consistent	one point
No such pivot; some variable column has no pivot	consistent	infinite (one free parameter each)

Two consistency checks without solving

Because only the pivot pattern matters, a system can be classified without finishing the reduction.

Lay, Linear Algebra and Its Applications, §1.1 — Systems of Linear Equations: the definition of a linear equation and system, solution sets, equivalence, matrix notation, elementary row operations, and the two fundamental questions of existence and uniqueness. ↩
Lay, §1.2 and Appendix A — Uniqueness of the Reduced Echelon Form: the reduced echelon form of a matrix is unique, so pivot positions are well defined independent of the reduction path. ↩
Lay, §1.2, Numerical Note — partial pivoting selects the pivot of largest absolute value in a column to reduce roundoff error. ↩
Lay, §1.2, Numerical Note — operation counts: the forward phase of reducing an $n \times (n + 1)$ matrix costs about $2 n^{3} /3$ flops, the backward phase at most $n^{2}$ . ↩

The geometry of two equations

Matrix notation

Elementary row operations

Echelon forms

The row reduction algorithm

Reading the solution set

Existence and uniqueness

Two consistency checks without solving

Footnotes