5 Row Reduction and Gauss–Jordan Elimination

5.1 Opening question

In Chapter 1, we solved systems by eliminating variables. In Chapter 2, we learned to store a system as an augmented matrix.

Now we combine these ideas.

Instead of rewriting equations again and again, we perform operations directly on the augmented matrix. This gives one of the most important algorithms in linear algebra:

row reduction.

Row reduction is the computational engine behind:

solving linear systems,
finding pivots,
detecting free variables,
describing solution sets,
finding inverses,
computing rank,
finding bases for subspaces,
understanding whether data constraints are independent.

The main algorithm of this chapter is Gauss–Jordan elimination.

5.2 Learning goals

After studying this chapter, you should be able to:

Perform elementary row operations.
Reduce a matrix to row-echelon form.
Reduce a matrix to reduced row-echelon form.
Identify pivot positions, pivot columns, and free variables.
Solve linear systems from an augmented matrix.
Recognize inconsistent systems from row reduction.
Write solution sets in parametric vector form.
Distinguish homogeneous and nonhomogeneous systems.
Understand row reduction as an algorithm.
Use Python and SymPy to compute reduced row-echelon form.

5.3 3.1 Why row reduction?

Consider the system

\[ \begin{cases} x_1-3x_2-5x_3=1,\\ x_1-x_2-2x_3=0,\\ 3x_1-x_2+x_3=3. \end{cases} \]

The augmented matrix is

\[ \left[ \begin{array}{ccc|c} 1&-3&-5&1\\ 1&-1&-2&0\\ 3&-1&1&3 \end{array} \right]. \]

The equations contain variables, but elimination only changes the coefficients and constants. Therefore, we can work directly with the rows of this matrix.

The goal is to transform the system into a simpler but equivalent system.

Equivalent means:

the new system has exactly the same solution set as the original system.

5.4 3.2 Elementary row operations

Definition: elementary row operations

There are three types of elementary row operations:

Swap two rows.
Multiply a row by a nonzero scalar.
Add a multiple of one row to another row.

These operations do not change the solution set of the corresponding linear system.

We use notation such as:

\[ R_2 \leftarrow R_2-R_1 \]

to mean:

replace row 2 by row 2 minus row 1.

Similarly,

\[ R_3 \leftarrow R_3-3R_1 \]

means:

replace row 3 by row 3 minus three times row 1.

And

\[ R_2 \leftarrow \frac{1}{2}R_2 \]

means:

replace row 2 by one half of row 2.

5.5 3.3 Why row operations preserve solutions

Each row of an augmented matrix represents an equation.

Swapping rows only changes the order of equations. The solution set does not change.

Multiplying a row by a nonzero scalar changes an equation like

\[ 2x+4y=6 \]

into

\[ x+2y=3. \]

These equations have the same solutions.

Adding a multiple of one row to another corresponds to replacing one equation by a combination of equations. If a vector satisfies the original equations, it also satisfies the new equation. Conversely, the operation can be reversed, so no solutions are lost.

Core principle

Elementary row operations preserve the solution set of a linear system.

5.6 3.4 Row-echelon form

Row reduction tries to create a staircase pattern.

A matrix is in row-echelon form if:

All zero rows, if any, are at the bottom.
Each nonzero row has a first nonzero entry, called a pivot.
Each pivot is to the right of the pivot in the row above it.
All entries below each pivot are zero.

Example:

\[ \left[ \begin{array}{ccc|c} 1&2&-1&3\\ 0&1&4&5\\ 0&0&2&6 \end{array} \right] \]

is in row-echelon form.

The pivots form a staircase:

\[ \left[ \begin{array}{ccc|c} \boxed{1}&2&-1&3\\ 0&\boxed{1}&4&5\\ 0&0&\boxed{2}&6 \end{array} \right]. \]

Row-echelon form is useful for back substitution.

5.7 3.5 Reduced row-echelon form

Gauss–Jordan elimination goes further.

A matrix is in reduced row-echelon form, abbreviated rref, if:

It is in row-echelon form.
Each pivot is equal to \(1\).
Each pivot is the only nonzero entry in its column.

Example:

\[ \left[ \begin{array}{ccc|c} 1&0&0&2\\ 0&1&0&-1\\ 0&0&1&3 \end{array} \right] \]

is in reduced row-echelon form.

Another example is

\[ \left[ \begin{array}{ccccc|c} 1&2&0&0&3&2\\ 0&0&1&0&-1&4\\ 0&0&0&1&-2&3\\ 0&0&0&0&0&0 \end{array} \right]. \]

The leading \(1\)’s are pivots. The variables corresponding to pivot columns are pivot variables. The other variables are free variables.

5.8 3.6 First full row-reduction example

Solve

\[ \begin{cases} x_1-3x_2-5x_3=1,\\ x_1-x_2-2x_3=0,\\ 3x_1-x_2+x_3=3. \end{cases} \]

Start with the augmented matrix:

\[ \left[ \begin{array}{ccc|c} 1&-3&-5&1\\ 1&-1&-2&0\\ 3&-1&1&3 \end{array} \right]. \]

Eliminate below the first pivot:

\[ R_2\leftarrow R_2-R_1,\qquad R_3\leftarrow R_3-3R_1. \]

This gives

\[ \left[ \begin{array}{ccc|c} 1&-3&-5&1\\ 0&2&3&-1\\ 0&8&16&0 \end{array} \right]. \]

Make the second pivot equal to \(1\):

\[ R_2\leftarrow \frac{1}{2}R_2. \]

Then

\[ \left[ \begin{array}{ccc|c} 1&-3&-5&1\\ 0&1&\frac32&-\frac12\\ 0&8&16&0 \end{array} \right]. \]

Eliminate below the second pivot:

\[ R_3\leftarrow R_3-8R_2. \]

\[ \left[ \begin{array}{ccc|c} 1&-3&-5&1\\ 0&1&\frac32&-\frac12\\ 0&0&4&4 \end{array} \right]. \]

Make the third pivot equal to \(1\):

\[ R_3\leftarrow \frac14R_3. \]

Then

\[ \left[ \begin{array}{ccc|c} 1&-3&-5&1\\ 0&1&\frac32&-\frac12\\ 0&0&1&1 \end{array} \right]. \]

Now eliminate above the third pivot:

\[ R_2\leftarrow R_2-\frac32R_3,\qquad R_1\leftarrow R_1+5R_3. \]

This gives

\[ \left[ \begin{array}{ccc|c} 1&-3&0&6\\ 0&1&0&-2\\ 0&0&1&1 \end{array} \right]. \]

Finally eliminate above the second pivot:

\[ R_1\leftarrow R_1+3R_2. \]

\[ \left[ \begin{array}{ccc|c} 1&0&0&0\\ 0&1&0&-2\\ 0&0&1&1 \end{array} \right]. \]

Therefore

\[ x_1=0,\qquad x_2=-2,\qquad x_3=1. \]

The solution is

\[ \begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix} = \begin{bmatrix} 0\\ -2\\ 1 \end{bmatrix}. \]

5.9 3.7 Pivots and free variables

Consider the reduced matrix

\[ \left[ \begin{array}{ccccc|c} 1&2&0&0&3&2\\ 0&0&1&0&-1&4\\ 0&0&0&1&-2&3\\ 0&0&0&0&0&0 \end{array} \right]. \]

This corresponds to the system

\[ x_1+2x_2+3x_5=2, \]

\[ x_3-x_5=4, \]

\[ x_4-2x_5=3. \]

The pivot variables are

\[ x_1,\quad x_3,\quad x_4. \]

The free variables are

\[ x_2,\quad x_5. \]

Let

\[ x_2=s,\qquad x_5=t. \]

Then

\[ x_1=2-2s-3t, \]

\[ x_3=4+t, \]

\[ x_4=3+2t. \]

Thus

\[ \begin{bmatrix} x_1\\ x_2\\ x_3\\ x_4\\ x_5 \end{bmatrix} = \begin{bmatrix} 2-2s-3t\\ s\\ 4+t\\ 3+2t\\ t \end{bmatrix}. \]

In parametric vector form,

\[ \begin{bmatrix} x_1\\ x_2\\ x_3\\ x_4\\ x_5 \end{bmatrix} = \begin{bmatrix} 2\\ 0\\ 4\\ 3\\ 0 \end{bmatrix} + s \begin{bmatrix} -2\\ 1\\ 0\\ 0\\ 0 \end{bmatrix} + t \begin{bmatrix} -3\\ 0\\ 1\\ 2\\ 1 \end{bmatrix}. \]

How to read free variables

Each non-pivot column among the variable columns gives one free variable. Each free variable creates one direction vector in the solution set.

5.10 3.8 Three possible outcomes

Row reduction reveals which type of solution set a system has.

5.10.1 Unique solution

If every variable is a pivot variable and there is no contradiction, the system has a unique solution.

Example:

\[ \left[ \begin{array}{ccc|c} 1&0&0&2\\ 0&1&0&-1\\ 0&0&1&3 \end{array} \right]. \]

The solution is

\[ (x_1,x_2,x_3)=(2,-1,3). \]

5.10.2 Infinitely many solutions

If at least one variable is free and there is no contradiction, the system has infinitely many solutions.

Example:

\[ \left[ \begin{array}{ccc|c} 1&0&2&3\\ 0&1&-1&4\\ 0&0&0&0 \end{array} \right]. \]

Here \(x_3\) is free.

5.10.3 No solution

If row reduction produces a row of the form

\[ \left[ \begin{array}{cccc|c} 0&0&0&\cdots&1 \end{array} \right], \]

then the system is inconsistent.

This row means

\[ 0=1, \]

which is impossible.

Example:

\[ \left[ \begin{array}{ccc|c} 1&0&2&3\\ 0&1&-1&4\\ 0&0&0&1 \end{array} \right] \]

has no solution.

5.11 3.9 Homogeneous systems and rref

A homogeneous system has the form

\[ Ax=0. \]

The augmented matrix is

\[ [A\mid 0]. \]

Since the zero vector always satisfies \(Ax=0\), a homogeneous system is always consistent.

There are two possibilities:

The only solution is \(x=0\).
There are infinitely many solutions.

There is no third possibility.

If there is a free variable, then there are infinitely many solutions. If every variable is a pivot variable, then the only solution is the zero solution.

5.12 3.10 Example: homogeneous system

Solve

\[ \begin{cases} x_1+2x_2+3x_3=0,\\ 2x_1+4x_2+6x_3=0. \end{cases} \]

The augmented matrix is

\[ \left[ \begin{array}{ccc|c} 1&2&3&0\\ 2&4&6&0 \end{array} \right]. \]

Use

\[ R_2\leftarrow R_2-2R_1. \]

Then

\[ \left[ \begin{array}{ccc|c} 1&2&3&0\\ 0&0&0&0 \end{array} \right]. \]

The equation is

\[ x_1+2x_2+3x_3=0. \]

Let

\[ x_2=s,\qquad x_3=t. \]

Then

\[ x_1=-2s-3t. \]

\[ \begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix} = s \begin{bmatrix} -2\\ 1\\ 0 \end{bmatrix} + t \begin{bmatrix} -3\\ 0\\ 1 \end{bmatrix}. \]

Notice that the solution set goes through the origin because the system is homogeneous.

5.13 3.11 Rank preview

The rank of a matrix is the number of pivot positions in its row-echelon form.

For example,

\[ \left[ \begin{array}{ccccc} 1&2&0&0&3\\ 0&0&1&0&-1\\ 0&0&0&1&-2\\ 0&0&0&0&0 \end{array} \right] \]

has three pivots, so its rank is \(3\).

Rank measures how much independent information is contained in the rows or columns of a matrix. Later, rank will become one of the central concepts of the course.

5.14 3.12 Gauss elimination versus Gauss–Jordan elimination

There are two closely related algorithms.

5.14.1 Gaussian elimination

Gaussian elimination reduces a matrix to row-echelon form. Then we solve using back substitution.

5.14.2 Gauss–Jordan elimination

Gauss–Jordan elimination reduces a matrix all the way to reduced row-echelon form. Then the solution can be read off directly.

For hand computation, Gaussian elimination is often faster.

For conceptual understanding, reduced row-echelon form is very useful because it displays pivot variables and free variables clearly.

5.15 3.13 Algorithm: Gauss–Jordan elimination

Algorithm: Gauss–Jordan elimination

Given an augmented matrix:

Start with the leftmost column containing a nonzero entry.
Swap rows, if necessary, to move a nonzero entry into the pivot position.
Scale the pivot row so the pivot becomes \(1\).
Use row replacement to make all other entries in the pivot column equal to \(0\).
Move to the next row and the next possible pivot column.
Continue until no more pivots can be found.
Move any zero rows to the bottom.
Read the solution from the reduced row-echelon form.

5.16 3.14 Python: exact rref with SymPy

NumPy is excellent for numerical computation, but it does not compute exact reduced row-echelon forms. For exact symbolic row reduction, use SymPy.

import sympy as sp

M = sp.Matrix([
    [1, -3, -5, 1],
    [1, -1, -2, 0],
    [3, -1,  1, 3]
])

M_rref, pivot_columns = M.rref()
M_rref, pivot_columns

(Matrix([
 [1, 0, 0,  0],
 [0, 1, 0, -2],
 [0, 0, 1,  1]]),
 (0, 1, 2))

The first output is the reduced row-echelon form. The second output gives the pivot columns.

For this example, the rref is

\[ \left[ \begin{array}{ccc|c} 1&0&0&0\\ 0&1&0&-2\\ 0&0&1&1 \end{array} \right]. \]

So the solution is

\[ (x_1,x_2,x_3)=(0,-2,1). \]

5.17 3.15 Python: numerical solving with NumPy

For a square system with a unique solution, we can use np.linalg.solve.

import numpy as np

A = np.array([
    [1, -3, -5],
    [1, -1, -2],
    [3, -1,  1]
], dtype=float)

b = np.array([1, 0, 3], dtype=float)

x = np.linalg.solve(A, b)
x

array([ 1.48029737e-16, -2.00000000e+00,  1.00000000e+00])

Check the solution:

A @ x

array([1.00000000e+00, 2.22044605e-16, 3.00000000e+00])

This should reproduce \(b\).

Numerical warning

For theoretical row reduction, use exact arithmetic when possible.

Floating-point arithmetic can introduce small roundoff errors. In numerical linear algebra, we often use more stable algorithms than direct row reduction, especially for large systems.

5.18 3.16 Python: detecting inconsistency with rref

Consider

\[ \begin{cases} x+y=1,\\ x+y=2. \end{cases} \]

The augmented matrix is

\[ \left[ \begin{array}{cc|c} 1&1&1\\ 1&1&2 \end{array} \right]. \]

M = sp.Matrix([
    [1, 1, 1],
    [1, 1, 2]
])

M.rref()

(Matrix([
 [1, 1, 0],
 [0, 0, 1]]),
 (0, 2))

The rref is

\[ \left[ \begin{array}{cc|c} 1&1&0\\ 0&0&1 \end{array} \right]. \]

The second row means

\[ 0=1. \]

Therefore the system is inconsistent.

5.19 3.17 Python: parametric solutions

SymPy can also solve systems symbolically.

x1, x2, x3 = sp.symbols("x1 x2 x3")

solution = sp.linsolve([
    x1 + 2*x2 + 3*x3,
    2*x1 + 4*x2 + 6*x3
], (x1, x2, x3))

solution

\(\displaystyle \left\{\left( - 2 x_{2} - 3 x_{3}, \ x_{2}, \ x_{3}\right)\right\}\)

This returns a parametric description of the solution set.

5.20 3.18 Interpreting rref as information compression

Row reduction simplifies a system without changing its solution set.

In this sense, rref is a kind of information compression. It removes redundant equations and reveals:

which variables are determined,
which variables are free,
whether the system is consistent,
how many independent constraints are present.

In data and AI, many matrices contain redundant or nearly redundant information. Row reduction is the exact algebraic version of revealing independent structure.

Later, rank, QR factorization, and SVD will give more numerically stable and geometrically meaningful versions of this idea.

5.21 3.19 Common mistakes

5.21.1 Mistake 1: using zero as a pivot

A pivot must be nonzero. If the entry is zero, swap with a lower row if possible.

5.21.2 Mistake 2: dividing by zero

You may multiply a row by a nonzero scalar only.

5.21.3 Mistake 3: forgetting to apply row operations to the entire row

In an augmented matrix, row operations must be applied to both the coefficient side and the right-hand side.

5.21.4 Mistake 4: losing free variables

A variable without a pivot is free. Do not set it to zero unless the problem asks for one particular solution.

5.21.5 Mistake 5: confusing \(0=0\) and \(0=1\)

A row of all zeros means no new information.

A row with zeros on the left and a nonzero number on the right means contradiction.

5.21.6 Mistake 6: thinking rref changes the problem

Row operations change the appearance of the system, not its solution set.

5.22 3.20 Chapter summary

Elementary row operations are:

swap two rows,
multiply a row by a nonzero scalar,
add a multiple of one row to another row.

These operations preserve the solution set of a linear system.

Row-echelon form creates a staircase pattern of pivots.

Reduced row-echelon form makes each pivot equal to \(1\) and clears all other entries in pivot columns.

Pivots identify pivot variables.

Non-pivot variable columns identify free variables.

A system has:

a unique solution if every variable is a pivot variable and there is no contradiction,
infinitely many solutions if there is at least one free variable and no contradiction,
no solution if row reduction produces a contradiction such as \(0=1\).

For homogeneous systems \(Ax=0\), there is always at least the zero solution.

5.23 Exercises

5.23.1 A. Elementary row operations

For each operation, state what it does.

\(R_2\leftarrow R_2-3R_1\)
\(R_3\leftarrow 5R_3\)
\(R_1\leftrightarrow R_4\)
\(R_2\leftarrow R_2+\frac12R_3\)

Which of these operations are allowed elementary row operations?

5.23.2 B. Row-echelon form and rref

Determine whether each matrix is in row-echelon form, reduced row-echelon form, both, or neither.

\[ \begin{bmatrix} 1&2&3\\ 0&1&4\\ 0&0&5 \end{bmatrix} \]

\[ \begin{bmatrix} 1&0&2\\ 0&1&-1\\ 0&0&0 \end{bmatrix} \]

\[ \begin{bmatrix} 0&1&2\\ 1&0&3\\ 0&0&0 \end{bmatrix} \]

\[ \begin{bmatrix} 1&0&0&2\\ 0&1&0&-1\\ 0&0&1&3 \end{bmatrix} \]

5.23.3 C. Solve by row reduction

Solve each system by row reduction. Write your answer clearly.

\[ \begin{cases} x+y=5,\\ 2x-y=1. \end{cases} \]

\[ \begin{cases} x_1-3x_2-5x_3=1,\\ x_1-x_2-2x_3=0,\\ 3x_1-x_2+x_3=3. \end{cases} \]

\[ \begin{cases} x_1+x_2+x_3=2,\\ x_1-x_2+2x_3=1,\\ 2x_1+x_2+3x_3=4. \end{cases} \]

\[ \begin{cases} x_1+2x_2+3x_3=1,\\ 2x_1+4x_2+6x_3=2,\\ 3x_1+6x_2+9x_3=4. \end{cases} \]

5.23.4 D. Parametric vector form

For each reduced augmented matrix, write the solution set in parametric vector form.

\[ \left[ \begin{array}{ccc|c} 1&0&2&3\\ 0&1&-1&4\\ 0&0&0&0 \end{array} \right] \]

\[ \left[ \begin{array}{cccc|c} 1&2&0&-1&5\\ 0&0&1&3&2\\ 0&0&0&0&0 \end{array} \right] \]

\[ \left[ \begin{array}{ccccc|c} 1&2&0&0&3&2\\ 0&0&1&0&-1&4\\ 0&0&0&1&-2&3 \end{array} \right] \]

\[ \left[ \begin{array}{ccc|c} 1&0&0&2\\ 0&1&0&-1\\ 0&0&1&3 \end{array} \right] \]

5.23.5 E. Consistency

For each rref matrix, determine whether the corresponding system is consistent. If consistent, say whether it has one solution or infinitely many.

\[ \left[ \begin{array}{ccc|c} 1&0&2&3\\ 0&1&-1&4\\ 0&0&0&0 \end{array} \right] \]

\[ \left[ \begin{array}{ccc|c} 1&0&2&3\\ 0&1&-1&4\\ 0&0&0&1 \end{array} \right] \]

\[ \left[ \begin{array}{ccc|c} 1&0&0&3\\ 0&1&0&4\\ 0&0&1&5 \end{array} \right] \]

\[ \left[ \begin{array}{cccc|c} 1&2&0&3&1\\ 0&0&1&-1&2\\ 0&0&0&0&0 \end{array} \right] \]

5.23.6 F. Homogeneous systems

Explain why a homogeneous system can never be inconsistent.
Solve

\[ \begin{cases} x_1+2x_2+3x_3=0,\\ 2x_1+4x_2+6x_3=0. \end{cases} \]

Solve

\[ \begin{cases} x_1+x_2+x_3=0,\\ x_1-x_2+x_3=0,\\ 2x_1+x_3=0. \end{cases} \]

For a homogeneous system with \(4\) variables and \(3\) pivots, how many free variables are there?

5.23.7 G. Python exercises

Use SymPy to compute the rref of

\[ \left[ \begin{array}{ccc|c} 1&-3&-5&1\\ 1&-1&-2&0\\ 3&-1&1&3 \end{array} \right]. \]

Use SymPy to compute the rref of

\[ \left[ \begin{array}{ccc|c} 1&1&1&2\\ 1&-1&2&1\\ 2&1&3&4 \end{array} \right]. \]

Use SymPy to determine whether the system

\[ \begin{cases} x+y+z=1,\\ 2x+2y+2z=3 \end{cases} \]

is consistent.

Use np.linalg.solve to solve a square system with a unique solution. Then check your answer by computing \(Ax-b\).
Create a matrix with one row that is a multiple of another row. Compute its rref and explain the zero row.

5.24 AI-age connection

Row reduction is one of the first examples of an algorithm that reveals hidden structure in data. It identifies redundancy, detects inconsistency, and separates determined variables from free variables. In modern computation, large data matrices often contain redundant information. Later algorithms such as QR factorization, least squares, and SVD extend this same idea in more stable and scalable ways.