---
title: Systems of Linear Equations and Row Reduction
module: Linear Equations in Linear Algebra
moduleNumber: 1
lessonNumber: 1
order: 101
summary: >
  A linear system is a finite set of linear equations in shared variables.
  Elementary row operations rewrite it without changing its solution set, and
  reducing the augmented matrix to echelon form decides both existence and
  uniqueness. Pivot positions say whether the solution set is empty, a single
  point, or infinite.
topics: [Linear Equations in Linear Algebra]
sources:
  - book: Lay
    ref: "Ch. 1 — Linear Equations; §1.1 Systems of Linear Equations"
  - book: Lay
    ref: "§1.2 Row Reduction and Echelon Forms; Appendix A Uniqueness of the Reduced Echelon Form"
---

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 + \cdots + a_n x_n = b,
$$

with coefficients $a_1, \dots, a_n$ and constant $b$ known in advance.[^lay-11]
It is linear because each variable appears alone, scaled by a constant: no
products $x_1 x_2$, no powers $x_1^2$, no $\sqrt{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.

$$
% caption: The three ways two lines can sit in the plane: crossing once, never,
% or everywhere. A linear system inherits exactly these three outcomes.
\begin{tikzpicture}[scale=1.0, font=\footnotesize]
\definecolor{acc}{HTML}{4A6FA5}
% --- panel 1: unique ---
\begin{scope}
  \draw[black] (-0.2,-0.2) rectangle (2.6,2.6);
  \draw[acc, thick] (-0.1,0.2) -- (2.5,2.0);
  \draw[acc, thick] (0.1,2.4) -- (2.3,-0.1);
  \fill[acc] (1.32,1.18) circle (2pt);
  \node[anchor=north] at (1.2,-0.35) {one solution};
\end{scope}
% --- panel 2: none ---
\begin{scope}[xshift=3.6cm]
  \draw[black] (-0.2,-0.2) rectangle (2.6,2.6);
  \draw[acc, thick] (-0.1,0.3) -- (2.5,1.9);
  \draw[acc, thick] (-0.1,0.9) -- (2.5,2.5);
  \node[anchor=north] at (1.2,-0.35) {no solution};
\end{scope}
% --- panel 3: infinite ---
\begin{scope}[xshift=7.2cm]
  \draw[black] (-0.2,-0.2) rectangle (2.6,2.6);
  \draw[acc, line width=1.6pt] (-0.1,0.4) -- (2.5,2.1);
  \node[anchor=north] at (1.2,-0.35) {infinitely many};
\end{scope}
\end{tikzpicture}
$$

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.

> **Theorem (Three outcomes).** A system of linear equations has either no
> solution, exactly one solution, or infinitely many solutions. A system is
> **consistent** if it has at least one solution and **inconsistent** if it has
> none.

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.

$$
% caption: 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).
\begin{tikzpicture}[scale=1.0, font=\footnotesize]
\definecolor{acc}{HTML}{4A6FA5}
% --- left: three planes meeting at a point ---
\begin{scope}
  \draw[acc!55, fill=acc!8] (-1.4,-0.5) -- (1.4,-1.0) -- (1.7,0.9) -- (-1.1,1.4) -- cycle;
  \draw[acc!70, fill=acc!10] (-1.5,0.9) -- (1.5,1.3) -- (1.2,-1.1) -- (-1.8,-0.6) -- cycle;
  \draw[black, fill=black!6] (-1.6,0.2) -- (1.6,-0.2) -- (1.3,-1.3) -- (-1.9,-0.9) -- cycle;
  \fill[acc] (0.05,-0.05) circle (2.2pt);
  \node[anchor=north] at (0,-1.75) {meet at a point};
\end{scope}
% --- right: three planes sharing a line ---
\begin{scope}[xshift=6.4cm]
  \draw[acc!55, fill=acc!8] (-1.6,-1.2) -- (1.6,-1.2) -- (0.9,1.4) -- (-2.3,1.4) -- cycle;
  \draw[acc!70, fill=acc!10] (-1.1,-1.3) -- (2.0,-0.9) -- (0.7,1.5) -- (-2.4,1.1) -- cycle;
  \draw[black, fill=black!6] (-1.9,-1.0) -- (1.3,-1.3) -- (0.5,1.5) -- (-2.7,1.2) -- cycle;
  \draw[acc, very thick] (-1.0,-1.25) -- (0.05,1.45);
  \node[anchor=north] at (-0.3,-1.75) {share a line};
\end{scope}
\end{tikzpicture}
$$

## 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

$$
\begin{aligned}
x_1 - 2x_2 + x_3 &= 0 \\
2x_2 - 8x_3 &= 8 \\
5x_1 - 5x_3 &= 10
\end{aligned}
$$

the **coefficient matrix** and the **augmented matrix** are

$$
\begin{bmatrix} 1 & -2 & 1 \\ 0 & 2 & -8 \\ 5 & 0 & -5 \end{bmatrix},
\qquad
\begin{bmatrix} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 5 & 0 & -5 & 10 \end{bmatrix}.
$$

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.

> **Definition (Coefficient and augmented matrix).** For a system of $m$
> equations in $n$ variables, the **coefficient matrix** is the $m \times n$
> array of coefficients $a_{ij}$, and the **augmented matrix** is the
> $m \times (n+1)$ array formed by appending the column of constants $b_i$.

## 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.

> **Definition (Elementary row operations).**
> - **Replacement**: add to one row a multiple of another row.
> - **Interchange**: swap two rows.
> - **Scaling**: multiply all entries of a row by a nonzero constant.

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\,(\text{row }i)$ by adding $-c\,(\text{row }i)$ back. That
reversibility is what justifies elimination.

> **Theorem (Row operations preserve solutions).** If the augmented matrices of
> two linear systems are row equivalent, the two systems have the same solution
> set.

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.

> **Worked example.** Solve the system with the $3 \times 4$ augmented matrix
> above by elimination.
>
> Use the leading $x_1$ to clear the entries below it. Add $-5$ times row 1 to
> row 3 to remove the $5$ in the lower-left corner:
>
> $$
> \begin{bmatrix} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 0 & 10 & -10 & 10 \end{bmatrix}.
> $$
>
> Scale row 2 by $\tfrac12$, then add $-10$ times the new row 2 to row 3:
>
> $$
> \begin{bmatrix} 1 & -2 & 1 & 0 \\ 0 & 1 & -4 & 4 \\ 0 & 0 & 30 & -30 \end{bmatrix}
> \;\longrightarrow\;
> \begin{bmatrix} 1 & -2 & 1 & 0 \\ 0 & 1 & -4 & 4 \\ 0 & 0 & 1 & -1 \end{bmatrix}.
> $$
>
> The last matrix is triangular. Row 3 gives $x_3 = -1$, and back-substitution
> gives $x_2 = 0$ then $x_1 = 1$, so the unique solution is $(1, 0, -1)$.
> Substituting back into the original equations confirms $0 = 0$, $8 = 8$,
> $10 = 10$. Each step was an elementary row operation, so this solves the
> original system, not merely the triangular one.

## 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.

> **Definition (Echelon form).** A matrix is in **echelon form** (**row echelon
> form**) when:
> 1. every all-zero row lies below every nonzero row;
> 2. each leading entry sits in a column strictly to the right of the leading
>    entry of the row above it;
> 3. every entry below a leading entry is zero.
>
> It is in **reduced echelon form** if additionally:
> 4. every leading entry is $1$;
> 5. each leading $1$ is the only nonzero entry in its column.

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.

$$
% caption: An echelon staircase: leading entries step down and to the right,
% with zeros below each and only zeros in the bottom rows.
\begin{tikzpicture}[scale=0.62, font=\small]
\definecolor{acc}{HTML}{4A6FA5}
% pivots at (row,col) = (0,0),(1,1),(2,3): filled accent squares
\foreach \r/\c in {0/0, 1/1, 2/3} {
  \draw[acc, thick] (\c-0.34,-\r-0.34) rectangle (\c+0.34,-\r+0.34);
  \fill[acc] (\c-0.15,-\r-0.15) rectangle (\c+0.15,-\r+0.15);
}
% arbitrary entries to the right of the staircase: gray dots
\foreach \r/\c in {0/1, 0/2, 0/3, 0/4, 1/2, 1/3, 1/4, 2/4} {
  \fill[black] (\c,-\r) circle (2.4pt);
}
% forced zeros below the staircase
\foreach \r/\c in {1/0, 2/0, 2/1, 2/2, 3/0, 3/1, 3/2, 3/3, 3/4} {
  \node[black] at (\c,-\r) {$0$};
}
% staircase outline
\draw[acc, dashed, thick] (-0.5,0.5) -- (0.5,0.5) -- (0.5,-0.5) -- (1.5,-0.5) -- (1.5,-1.5) -- (3.5,-1.5) -- (3.5,-2.5) -- (4.5,-2.5);
\end{tikzpicture}
$$

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

> **Theorem (Uniqueness of the reduced echelon form).** Each matrix is row
> equivalent to one and only one reduced echelon matrix.[^lay-appA]

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.

> **Definition (Pivot position and pivot column).** A **pivot position** of a
> matrix $A$ is a location that holds a leading $1$ in the reduced echelon form
> of $A$. A **pivot column** is a column containing a pivot position. A **pivot**
> is a nonzero entry placed in a pivot position during row reduction.

## 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
caption: $\textsc{RowReduce}(A)$ — Gaussian elimination to reduced echelon form
// forward phase
$r \gets 1$
for each column $c$ from left to right do
  if column $c$ has a nonzero entry in rows $r, \dots, m$ then
    choose a pivot row $p \ge r$ with $A[p,c] \ne 0$
    interchange rows $r$ and $p$
    for each row $i$ below $r$ do
      add $-A[i,c]/A[r,c]$ times row $r$ to row $i$   // zeros below the pivot
    $r \gets r + 1$
// backward phase
for each pivot, from rightmost to leftmost do
  scale its row so the pivot becomes $1$
  add multiples of that row to the rows above to zero the rest of its column
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.[^lay-12num] The forward phase does the bulk
of the arithmetic — about $2n^3/3$ floating-point operations for an
$n \times (n+1)$ system, against at most $n^2$ for the backward phase.[^lay-flops]

> **Worked example.** Row reduce to reduced echelon form and locate the pivot
> columns:
>
> $$
> \begin{bmatrix} 0 & 3 & -6 & 6 & 4 & -5 \\ 3 & -7 & 8 & -5 & 8 & 9 \\ 3 & -9 & 12 & -9 & 6 & 15 \end{bmatrix}.
> $$
>
> 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:
>
> $$
> \begin{bmatrix} 3 & -9 & 12 & -9 & 6 & 15 \\ 3 & -7 & 8 & -5 & 8 & 9 \\ 0 & 3 & -6 & 6 & 4 & -5 \end{bmatrix}
> \;\longrightarrow\;
> \begin{bmatrix} 3 & -9 & 12 & -9 & 6 & 15 \\ 0 & 2 & -4 & 4 & 2 & -6 \\ 0 & 3 & -6 & 6 & 4 & -5 \end{bmatrix}.
> $$
>
> The next pivot is in column 2; clear the entry below it to finish the forward
> phase and reach an echelon form,
>
> $$
> \begin{bmatrix} 3 & -9 & 12 & -9 & 6 & 15 \\ 0 & 2 & -4 & 4 & 2 & -6 \\ 0 & 0 & 0 & 0 & 1 & 4 \end{bmatrix},
> $$
>
> 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
>
> $$
> \begin{bmatrix} 1 & 0 & -2 & 3 & 0 & -24 \\ 0 & 1 & -2 & 2 & 0 & -7 \\ 0 & 0 & 0 & 0 & 1 & 4 \end{bmatrix}.
> $$
>
> 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.

> **Definition (Basic and free variables).** A variable is **basic** if its
> column is a pivot column, and **free** otherwise. The reduced echelon form
> places each basic variable alone in one equation, expressed in terms of the
> free variables.

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

$$
\begin{aligned}
x_1 - 2x_3 + 3x_4 &= -24 \\
x_2 - 2x_3 + 2x_4 &= -7 \\
x_5 &= 4.
\end{aligned}
$$

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

$$
\begin{cases}
x_1 = -24 + 2x_3 - 3x_4, \\
x_2 = -7 + 2x_3 - 2x_4, \\
x_3 \text{ free}, \quad x_4 \text{ free}, \\
x_5 = 4.
\end{cases}
$$

**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.

> **Theorem (Existence and uniqueness).** A linear system is consistent if and
> only if the rightmost column of the augmented matrix is _not_ a pivot column —
> equivalently, if and only if no echelon form has a row of the shape
> $[\,0 \;\cdots\; 0 \mid b\,]$ with $b \ne 0$. When consistent, the system has a
> unique solution if there are no free variables, and infinitely many if there
> is at least one free variable.

A row $[\,0 \;\cdots\; 0 \mid b\,]$ with $b \ne 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.

$$
% caption: 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.
\begin{tikzpicture}[scale=1.0, font=\footnotesize,
  box/.style={draw, minimum width=34mm, minimum height=9mm, align=center},
  dec/.style={draw, acc, thick, minimum width=40mm, minimum height=9mm, align=center}]
\definecolor{acc}{HTML}{4A6FA5}
\node[box] (start) at (0,0) {echelon form of\\augmented matrix};
\node[dec] (q1) at (0,-1.9) {pivot in the last column?};
\node[box, fill=acc!8] (incon) at (5.2,-1.9) {inconsistent:\\no solution};
\node[dec] (q2) at (0,-3.8) {any free variable?};
\node[box, fill=acc!8] (many) at (5.2,-3.8) {consistent:\\inf\/initely many};
\node[box, fill=acc!8] (uniq) at (0,-5.6) {consistent:\\unique solution};
\draw[->, black] (start) -- (q1);
\draw[->, black] (q1) -- (incon) node[midway, above, font=\scriptsize] {yes};
\draw[->, black] (q1) -- (q2) node[midway, left, font=\scriptsize] {no};
\draw[->, black] (q2) -- (many) node[midway, above, font=\scriptsize] {yes};
\draw[->, black] (q2) -- (uniq) node[midway, left, font=\scriptsize] {no};
\end{tikzpicture}
$$

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.

> **Worked example.** After the forward phase, an augmented matrix reaches
>
> $$
> \begin{bmatrix} 1 & 5 & 2 & 6 \\ 0 & 4 & -7 & 2 \\ 0 & 0 & 5 & 0 \end{bmatrix}.
> $$
>
> Pivots sit in all three variable columns and none in the augmented column, so
> the system is consistent with exactly one solution. The pivot pattern settles
> this without computing the solution.

> **Worked example.** Classify the system
>
> $$
> \begin{aligned}
> x_2 - 4x_3 &= 8 \\
> 2x_1 - 3x_2 + 2x_3 &= 1 \\
> 4x_1 - 8x_2 + 12x_3 &= 1.
> \end{aligned}
> $$
>
> Reducing the augmented matrix reaches an echelon form whose last row is
> $[\,0\;0\;0 \mid 15\,]$, the equation $0 = 15$. The rightmost column is a pivot
> column, so the system has no solution.

[^lay-11]: **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-appA]: **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-12num]: **Lay**, §1.2, Numerical Note — partial pivoting selects the pivot of largest absolute value in a column to reduce roundoff error.
[^lay-flops]: **Lay**, §1.2, Numerical Note — operation counts: the forward phase of reducing an $n \times (n+1)$ matrix costs about $2n^3/3$ flops, the backward phase at most $n^2$.