Systems of Linear Equations and Row Reduction

The general solution of a linear system Ax = b is a particular solution plus the null space of A. We prove this structure theorem by developing Gaussian elimination and reduced row echelon form, and give precise conditions for when solutions exist and when they are unique.

Folio Official

March 1, 2026

1. Matrix Formulation

A system of $m$ linear equations in $n$ unknowns,

⎩ ⎨ ⎧ a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} = b_{1} a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} = b_{2} ⋮ a_{m 1} x_{1} + a_{m 2} x_{2} + \dots + a_{mn} x_{n} = b_{m}

can be written as the single matrix equation

A x = b,

where

A = (a_{ij}) \in M_{m \times n} (K)

x = (x_{1}, \dots, x_{n})^{T}

, and

b = (b_{1}, \dots, b_{m})^{T}

. When

b = 0

, the system is called homogeneous; otherwise it is nonhomogeneous.

2. Elementary Row Operations

Definition 1 (Elementary row operations).

The following three types of operations on a matrix are called elementary row operations:

Interchange two rows: $R_{i} \leftrightarrow R_{j}$ .
Multiply a row by a nonzero scalar: $R_{i} \to c R_{i}$ ( $c \neq = 0$ ).
Add a scalar multiple of one row to another: $R_{i} \to R_{i} + c R_{j}$ .

Theorem 2.

Elementary row operations do not change the solution set of the corresponding system.

Proof.

Each elementary row operation is reversible (it can be undone by an operation of the same type), so it produces an equivalent system. □

Remark 3.

Each elementary row operation corresponds to left multiplication by an invertible matrix (an elementary matrix).

3. Reduced Row Echelon Form (RREF)

Definition 4 (Reduced row echelon form).

A matrix is in reduced row echelon form (RREF) if:

All zero rows are at the bottom.
The first nonzero entry (pivot) in each nonzero row is $1$ .
Pivots move strictly to the right as one goes down the rows.
Each pivot is the only nonzero entry in its column.

Theorem 5.

Every matrix can be brought to RREF by a sequence of elementary row operations. Moreover, the RREF of a matrix is unique.

Example 6.

123246102328 R_{2} - 2 R_{1} 103206 1 - 2 2 3 - 4 8 R_{3} - 3 R_{1} 100200 1 - 2 - 1 3 - 4 - 1

- \frac{1}{2} R_{2} 100200 11 - 1 32 - 1 R_{3} + R_{2} 100200110 32 - 3

One continues the elimination to arrive at the RREF.

4. Structure of the Solution Set

Theorem 7 (Null space of a homogeneous system).

The solution set of

A x = 0

is a subspace

ker A

K^{n}

, and

dim ker A = n - rank A .

Proof.

That

ker A

is a subspace follows from the fact that it is the kernel of the linear map

x \mapsto A x

. The dimension formula is an immediate consequence of the rank–nullity theorem:

dim K^{n} = dim ker A + dim Im A

, so

dim ker A = n - rank A

. □

Theorem 8 (Structure of solutions to a nonhomogeneous system).

A x = b

has a solution

x_{0}

, then the general solution is

x = x_{0} + ker A = {x_{0} + h ∣ h \in ker A} .

That is, the general solution is a particular solution plus the general solution of the associated homogeneous system.

Proof.

A x = b

and

A x_{0} = b

, then

A (x - x_{0}) = 0

, so

x - x_{0} \in ker A

. Conversely, if

h \in ker A

, then

A (x_{0} + h) = A x_{0} + A h = b + 0 = b

. □

Example 9.

Consider the system

A x = b

with

A = (111213), b = (36) .

The RREF of the augmented matrix is

(11121336) \to (1001 - 1 2 03) .

The pivot columns are columns

1

and

2

. The free variable is

x_{3} = t

. A particular solution is

x_{0} = (0, 3, 0)^{T}

, and the null space is

ker A = span {(1, - 2, 1)^{T}} .

The general solution is therefore

x = (t, 3 - 2 t, t)^{T} = (0, 3, 0)^{T} + t (1, - 2, 1)^{T}

5. Conditions for Existence and Uniqueness

Theorem 10.

The system

A x = b

has a solution if and only if

rank A = rank (A ∣ b)

Theorem 11.

For an

m \times n

system

A x = b

A solution exists if and only if $rank A = rank (A ∣ b)$ .
When a solution exists, it is unique if and only if $rank A = n$ .
When solutions exist, the solution set has $n - rank A$ free parameters.

Linear Algebra Algebra Textbook Systems of Equations Row Reduction RREF

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Systems of Linear Equations and Row Reduction

Folio Official

March 1, 2026

1. Matrix Formulation

A system of $m$ linear equations in $n$ unknowns,

⎩ ⎨ ⎧ a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} = b_{1} a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} = b_{2} ⋮ a_{m 1} x_{1} + a_{m 2} x_{2} + \dots + a_{mn} x_{n} = b_{m}

can be written as the single matrix equation

A x = b,

where

A = (a_{ij}) \in M_{m \times n} (K)

x = (x_{1}, \dots, x_{n})^{T}

, and

b = (b_{1}, \dots, b_{m})^{T}

. When

b = 0

, the system is called homogeneous; otherwise it is nonhomogeneous.

2. Elementary Row Operations

Definition 1 (Elementary row operations).

The following three types of operations on a matrix are called elementary row operations:

Interchange two rows: $R_{i} \leftrightarrow R_{j}$ .
Multiply a row by a nonzero scalar: $R_{i} \to c R_{i}$ ( $c \neq = 0$ ).
Add a scalar multiple of one row to another: $R_{i} \to R_{i} + c R_{j}$ .

Theorem 2.

Elementary row operations do not change the solution set of the corresponding system.

Proof.

Each elementary row operation is reversible (it can be undone by an operation of the same type), so it produces an equivalent system. □

Remark 3.

Each elementary row operation corresponds to left multiplication by an invertible matrix (an elementary matrix).

3. Reduced Row Echelon Form (RREF)

Definition 4 (Reduced row echelon form).

A matrix is in reduced row echelon form (RREF) if:

All zero rows are at the bottom.
The first nonzero entry (pivot) in each nonzero row is $1$ .
Pivots move strictly to the right as one goes down the rows.
Each pivot is the only nonzero entry in its column.

Theorem 5.

Every matrix can be brought to RREF by a sequence of elementary row operations. Moreover, the RREF of a matrix is unique.

Example 6.

123246102328 R_{2} - 2 R_{1} 103206 1 - 2 2 3 - 4 8 R_{3} - 3 R_{1} 100200 1 - 2 - 1 3 - 4 - 1

- \frac{1}{2} R_{2} 100200 11 - 1 32 - 1 R_{3} + R_{2} 100200110 32 - 3

One continues the elimination to arrive at the RREF.

4. Structure of the Solution Set

Theorem 7 (Null space of a homogeneous system).

The solution set of

A x = 0

is a subspace

ker A

K^{n}

, and

dim ker A = n - rank A .

Proof.

That

ker A

is a subspace follows from the fact that it is the kernel of the linear map

x \mapsto A x

. The dimension formula is an immediate consequence of the rank–nullity theorem:

dim K^{n} = dim ker A + dim Im A

, so

dim ker A = n - rank A

. □

Theorem 8 (Structure of solutions to a nonhomogeneous system).

A x = b

has a solution

x_{0}

, then the general solution is

x = x_{0} + ker A = {x_{0} + h ∣ h \in ker A} .

That is, the general solution is a particular solution plus the general solution of the associated homogeneous system.

Proof.

A x = b

and

A x_{0} = b

, then

A (x - x_{0}) = 0

, so

x - x_{0} \in ker A

. Conversely, if

h \in ker A

, then

A (x_{0} + h) = A x_{0} + A h = b + 0 = b

. □

Example 9.

Consider the system

A x = b

with

A = (111213), b = (36) .

The RREF of the augmented matrix is

(11121336) \to (1001 - 1 2 03) .

The pivot columns are columns

1

and

2

. The free variable is

x_{3} = t

. A particular solution is

x_{0} = (0, 3, 0)^{T}

, and the null space is

ker A = span {(1, - 2, 1)^{T}} .

The general solution is therefore

x = (t, 3 - 2 t, t)^{T} = (0, 3, 0)^{T} + t (1, - 2, 1)^{T}

5. Conditions for Existence and Uniqueness

Theorem 10.

The system

A x = b

has a solution if and only if

rank A = rank (A ∣ b)

Theorem 11.

For an

m \times n

system

A x = b

A solution exists if and only if $rank A = rank (A ∣ b)$ .
When a solution exists, it is unique if and only if $rank A = n$ .
When solutions exist, the solution set has $n - rank A$ free parameters.

Linear Algebra Algebra Textbook Systems of Equations Row Reduction RREF

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Systems of Linear Equations and Row Reduction

1. Matrix Formulation

2. Elementary Row Operations

3. Reduced Row Echelon Form (RREF)

4. Structure of the Solution Set

5. Conditions for Existence and Uniqueness

Share your expertise with the world

More from Folio Official

Matrices and Representation of Linear Maps

The Determinant: A Scalar Invariant of Square Matrices

Jordan Normal Form: Beyond Diagonalization

The Singular Value Decomposition: Structure of Arbitrary Matrices

Systems of Linear Equations and Row Reduction

1. Matrix Formulation

2. Elementary Row Operations

3. Reduced Row Echelon Form (RREF)

4. Structure of the Solution Set

5. Conditions for Existence and Uniqueness

Share your expertise with the world

More from Folio Official

Matrices and Representation of Linear Maps

The Determinant: A Scalar Invariant of Square Matrices

Jordan Normal Form: Beyond Diagonalization

The Singular Value Decomposition: Structure of Arbitrary Matrices