Evanalysis
2.3Source-backedEmbedded interactionEstimated reading time: 3 min

2.3 Gaussian elimination and RREF

Follow one full row-reduction path and learn how REF and RREF let you read a system instead of guessing.

Note collections

MATH1030: Linear algebra I

Rigorous linear algebra notes on systems, matrices, structure, and proof, with interaction used only where it clarifies the mathematics.

Language

ENEnglish繁Traditional Chinese简Simplified Chinese
All note collectionsSeries overview

Chapter 1

Systems of equations

Learn to read equations as full solution sets.

1.1

1.1 Equations and solution sets

Chapter 2

Matrices and elimination

Build matrix intuition and use row reduction with purpose.

2.1

2.1 Matrix basics

2.2

2.2 Augmented matrices and row operations

2.3

2.3 Gaussian elimination and RREF

2.4

2.4 Solution-set types

Chapter 3

Matrix algebra

Matrix multiplication, transpose, and structural matrix notation.

3.1

3.1 Matrix multiplication and identity matrices

3.2

3.2 Transpose and special matrices

Chapter 4

Solution structure

Homogeneous systems, null spaces, and the shape of full solution sets.

4.1

4.1 Homogeneous systems and null space

Chapter 5

Invertibility

Understand when a matrix can be undone and why that matters.

5.1

5.1 Invertible matrices

Member

Chapter 6

Vector spaces

Move from matrix procedures to the structure of spaces, span, independence, and basis.

6.1

6.1 Vector spaces

Member

6.2

6.2 Subspaces

Member

6.3

6.3 Linear combinations and span

Member

6.4

6.4 Linear dependence and independence

Member

6.5

6.5 Basis and dimension

Member

6.6

6.6 Column space, row space, and rank

Member

Why elimination matters

When students first meet Gaussian elimination, it can feel like a pile of rules:

  • swap rows,
  • multiply a row,
  • subtract a row,
  • keep going until the matrix looks “nice.”

That is not the right mental model.

Gaussian elimination is really a reading strategy. You start with a system that is hard to read, then you use row operations to make the logical structure of the system more visible. Each row operation should answer a question such as:

  • Which variable am I trying to isolate next?
  • Which entry is blocking me?
  • Which move will create more zeros without changing the solution set?

If you keep asking those questions, elimination becomes much less mechanical.

Intuition first: what are we trying to build?

The dream shape is not “a random simpler matrix.” The dream shape is a matrix whose important columns are easy to spot and whose equations are easy to read from bottom to top.

In practice, that means:

  1. pick a pivot entry,
  2. clear the entries below it,
  3. move to the smaller submatrix that remains,
  4. then clean up above the pivots if you want full reduced form.

So elimination is a controlled way of building a staircase of pivots.

Definition

REF and RREF

A matrix is in row echelon form (REF) when:

  1. all zero rows are at the bottom, and
  2. each nonzero row starts farther to the right than the row above it.

A matrix is in reduced row echelon form (RREF) when, in addition:

  1. each pivot is 1, and
  2. each pivot is the only nonzero entry in its column.

The first nonzero entry in a nonzero row is called a pivot or leading entry. A column containing a pivot is a pivot column. Columns without a pivot correspond to free variables.

That vocabulary matters because it tells you what kind of solution set to expect later.

Theorem

Why row reduction is safe

If two augmented matrices are row-equivalent, then they represent equivalent systems of linear equations. In other words, row operations change the look of the system, but not its solution set.

This is why elimination is legitimate. We are reorganizing information, not inventing a new problem.

One full elimination path

The local lecture notes in MATH1030-Notes.pdf §2.2 build elimination by starting from an augmented matrix and repeatedly clearing the entries beneath a pivot. We will follow that same idea on a small system:

x+2y+2z=4,x+3y+3z=5,2x+6y+5z=6.\begin{aligned} x + 2y + 2z &= 4, \\ x + 3y + 3z &= 5, \\ 2x + 6y + 5z &= 6. \end{aligned}

Its augmented matrix is

[122413352656].\begin{bmatrix} 1 & 2 & 2 & 4 \\ 1 & 3 & 3 & 5 \\ 2 & 6 & 5 & 6 \end{bmatrix}.

Worked example

Read every row operation as a purpose

The entry in the top-left corner is already a convenient pivot because it is 1. So the first goal is simple:

make everything below that pivot become 0.

Use

R2←R2−R1,R3←R3−2R1.R_2 \leftarrow R_2 - R_1, \qquad R_3 \leftarrow R_3 - 2R_1.

Then the matrix becomes

[12240111021−2].\begin{bmatrix} 1 & 2 & 2 & 4 \\ 0 & 1 & 1 & 1 \\ 0 & 2 & 1 & -2 \end{bmatrix}.

Now column 1 is finished. The next pivot lives in row 2, column 2. So we use it to clear the 2 below it:

R3←R3−2R2.R_3 \leftarrow R_3 - 2R_2.

This gives

[1224011100−1−4].\begin{bmatrix} 1 & 2 & 2 & 4 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & -1 & -4 \end{bmatrix}.

At this stage the matrix is already in REF. You can solve by back-substitution. But if you want the cleanest reading form, continue to RREF.

First make the last pivot equal to 1:

R3←−R3⇒[122401110014].R_3 \leftarrow -R_3 \quad\Rightarrow\quad \begin{bmatrix} 1 & 2 & 2 & 4 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 4 \end{bmatrix}.

Then clear the entries above that pivot:

R1←R1−2R3,R2←R2−R3,R_1 \leftarrow R_1 - 2R_3, \qquad R_2 \leftarrow R_2 - R_3,

so the matrix becomes

[120−4010−30014].\begin{bmatrix} 1 & 2 & 0 & -4 \\ 0 & 1 & 0 & -3 \\ 0 & 0 & 1 & 4 \end{bmatrix}.

Finally clear the 2 above the second pivot:

R1←R1−2R2,R_1 \leftarrow R_1 - 2R_2,

which gives the RREF

[1002010−30014].\begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & -3 \\ 0 & 0 & 1 & 4 \end{bmatrix}.

Now the solution can be read immediately:

x=2,y=−3,z=4.x = 2,\qquad y = -3,\qquad z = 4.

Notice the teaching pattern:

  • below-pivot clearing creates REF,
  • above-pivot clearing creates RREF,
  • RREF is the easiest form to read directly.

Try the same path interactively

The stepper below keeps the same logic, but slows it down. At each stage, look at three things:

  1. which pivot is active,
  2. which row operation is being applied, and
  3. what becomes easier to read afterward.

Read and try

Trace one full row-reduction path

The live stepper walks through one complete elimination path, showing the row operation, the pivot you are focusing on, and the matrix produced at each step.

1224
1335
2656

Row operation

Choose the first pivot in column 1.

What to notice

Column 1 already has a convenient pivot 1 in the first row, so we do not need a row swap.

Start with the augmented matrix. The first pivot should help us clear the entries underneath it.

How to read an RREF matrix

Once a matrix is in RREF, the main reading questions are:

  • Does every variable column have a pivot?
  • Is there any free variable?
  • Is there a contradiction row?

Worked example

Read structure before you compute

Suppose you arrive at

[103501−210000].\begin{bmatrix} 1 & 0 & 3 & 5 \\ 0 & 1 & -2 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}.

Here columns 1 and 2 are pivot columns, but column 3 is not. That means the third variable is free.

So this system does not have one unique solution. Instead, it has infinitely many solutions, because you may choose the free variable first and then solve for the pivot variables.

Theorem

What a contradiction row means

If row reduction produces a row such as

[0001],\begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix},

then the corresponding equation is 0=10 = 1. That is impossible, so the system is inconsistent and has no solution.

Common mistakes

Common mistake

REF is not yet RREF

It is common to stop as soon as everything below each pivot is 0. That may be good enough for back-substitution, but it is not yet RREF. In RREF, each pivot column must have zeros everywhere else as well.

Common mistake

Choosing operations without a target

Do not subtract rows just because “something should happen.” Before each move, state the target clearly:

  • which pivot are you using?
  • which entry are you trying to kill?
  • why is this the best next move?

That habit keeps your work organized and makes sign mistakes easier to catch.

Quick checks

Quick check

When should you swap rows before eliminating?

Think about the first available pivot position. What if the entry there is 0 but a nonzero entry appears lower in the same column?

Solution

Answer

Quick check

Is [0 0 0 | 1] a harmless row?

Translate the row back into an equation before you answer.

Solution

Answer

Exercises

Exercise 1

Start from

[112323580112].\begin{bmatrix} 1 & 1 & 2 & 3 \\ 2 & 3 & 5 & 8 \\ 0 & 1 & 1 & 2 \end{bmatrix}.

What is the most natural first row operation if your goal is to clear the entry below the first pivot?

Solution

Guided solution for exercise 1

Exercise 2

Consider the matrix

[102401−130000].\begin{bmatrix} 1 & 0 & 2 & 4 \\ 0 & 1 & -1 & 3 \\ 0 & 0 & 0 & 0 \end{bmatrix}.

Does this represent a system with a unique solution, infinitely many solutions, or no solution?

Solution

Guided solution for exercise 2

Read this first

This page builds directly on 2.2 Augmented matrices and row operations. If you are still unsure why row operations preserve the solution set, go back to that note first before practicing longer elimination paths.

Section mastery checkpoint

Complete the questions below to run a final section checkpoint. Progress: 0%.

Skills: rref, pivot-columns, row-reduction

In RREF, which statement is always true about pivot columns of a matrix A?

Prerequisites

2.2

2.2 Augmented matrices and row operations

Key terms in this unit

More notes in this series

Previous section

2.2 Augmented matrices and row operations

Next section

2.4 Solution-set types