2.3 Gaussian elimination and RREF

Why elimination matters

Gaussian elimination rewrites a system so that its solutions can be read from a sequence of pivot equations. At each stage, choose a pivot, clear the entries beneath it, and continue with the rows and columns that remain. Every operation must preserve the solution set while making the next variable easier to isolate.

This section follows that process from its target shape to a complete calculation. First distinguish REF from RREF; then use one worked reduction to see how each pivot is established and how the finished matrix describes the solutions.

The target: a staircase of pivots

The target shape makes each leading variable visible and allows the equations to be 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 among the coefficient columns correspond to free variables, once the augmented system is known to be consistent.

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.

Two questions: a valid path and a useful destination

Concept lensAlgorithmic

Elimination is an algorithm inside a row-equivalence class

Row equivalence tells us which changes are legal. Gaussian elimination tells us how to choose those changes so that a finite calculation reaches an interpretable destination. These are different questions. Swapping the same pair of rows forever preserves the solution set at every step, but does not solve the system. A useful algorithm needs both an invariant and a measure of progress.

The invariant is the solution set of the augmented system. During forward elimination, the progress is that successive pivot positions move strictly to the right and occupy successively lower rows. Once a pivot column is finished below its pivot, later operations on lower rows do not disturb those zeros. The algorithm works because its local simplifications accumulate rather than undoing one another.

To make that description precise, consider the rows still waiting to be processed. Find their leftmost column containing a nonzero entry. If necessary, swap one such entry into the top unprocessed row. Use this entry as the pivot and eliminate all entries beneath it. Then continue with the lower rows, searching only farther to the right. A column containing only zeros in the unprocessed rows is skipped; it does not require a division or a replacement pivot.

The phrase “leftmost” matters. It ensures that every unprocessed row has zero entries before the newly selected pivot. Linear combinations of these rows keep that prefix zero. Thus a later row cannot acquire a leading entry to the left of an earlier pivot. The definition of echelon form is therefore maintained by construction, not checked only after a fortunate calculation.

If all unprocessed rows are zero, forward elimination stops immediately. Otherwise each pivot uses another row and another column. There are only finitely many rows and columns, so the process must terminate. This is an existence argument for an echelon form, independent of any special numerical example. It does not prove uniqueness of the echelon form: different legal choices can give different nonzero pivot values and different entries above pivots.

Why backward cleanup preserves completed work

Starting with REF, normalize each nonzero pivot to one. Work from the last pivot row upward. To clear an entry above the current pivot, subtract its multiple of the pivot row. The pivot row has zero entries before its leading entry, so this subtraction cannot change any earlier pivot column. Pivot columns to its right have already been cleaned, including in the current row, so they are not spoiled either.

After finishing a pivot column, its leading one is the only nonzero entry there. Continue upward until every pivot column has this property. This gives RREF. The argument also explains why eliminating upwards in a carefully chosen order is easier to audit than making arbitrary substitutions throughout the matrix.

Normalization is not needed merely to obtain REF. A leading entry of two or minus three is allowed there. It becomes necessary for the reduced form because the definition of RREF requires leading ones. Back-substitution can already solve a consistent echelon system; reduced form is useful when the goal is to display all parameter dependence directly.

The existence of an algorithm and the uniqueness of its reduced output are separate theorems. The reduction procedure proves that some RREF can be reached. The uniqueness theorem says that every completed RREF obtained from the same matrix is identical. A different sequence of operations is therefore not evidence of an error, whereas two different claimed final RREF matrices cannot both be correct. The dedicated uniqueness note later supplies the proof of this distinction.

One full elimination path

Elimination starts from an augmented matrix and repeatedly clears the entries beneath a pivot. We will follow that idea on a small system:

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

Its augmented matrix is

$$\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

$$R_2 \leftarrow R_2 - R_1, \qquad R_3 \leftarrow R_3 - 2R_1.$$

Then the matrix becomes

$$\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:

$$R_3 \leftarrow R_3 - 2R_2.$$

This gives

$$\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$:

$$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:

$$R_1 \leftarrow R_1 - 2R_3, \qquad R_2 \leftarrow R_2 - R_3,$$

so the matrix becomes

$$\begin{bmatrix} 1 & 2 & 0 & -4 \\ 0 & 1 & 0 & -3 \\ 0 & 0 & 1 & 4 \end{bmatrix}.$$

Finally clear the $2$ above the second pivot:

$$R_1 \leftarrow R_1 - 2R_2,$$

which gives the RREF

$$\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,\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.

See the pivot staircase

The visual sequence below follows the same worked example. Read it as a bridge between the formal row operations and the interactive stepper: each frame keeps one mathematical purpose in focus before the calculation moves on.

Follow the same elimination example as a short visual sequence: pivots are selected, entries are cleared, and the final RREF is read as a solved system.

1. Start from the augmented matrix

   The first column already has a convenient pivot in row 1. The immediate goal is to make every entry below that pivot equal to 0.

2. Build the pivot staircase

   After the first clearing step, the next pivot appears in row 2, column 2. Clearing beneath it produces a row echelon form.

3. Normalize the last pivot

   The last nonzero row has leading entry -1. Multiplying the row by -1 turns the pivot into 1 without changing the solution set.

4. Clear above pivots

   RREF is obtained only after each pivot is the sole nonzero entry in its column, so the operations move upward as well as downward.

5. Read the solved variables

   Once the left block is the identity, the right column can be read directly as x = 2, y = -3, and z = 4.

The calculation is not a collection of disconnected row operations. It is a controlled change of form: first create REF by clearing below pivots, then create RREF by normalizing pivots and clearing above them.

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.

Track pivots through a larger system

A larger system tests whether the same pivot strategy remains clear across many steps. Before each operation, identify the column being cleared and the pivot being used; after it, check that the earlier pivot columns remain intact.

Consider the augmented matrix

$$C= \begin{bmatrix} 1 & 2 & 0 & 1 & 0 & 2 & 1 \\ 1 & 2 & 1 & 0 & 1 & 2 & 3 \\ 2 & 4 & 1 & 1 & 2 & 5 & 1 \\ 5 & 10 & 3 & 2 & 4 & 11 & 8 \end{bmatrix}.$$

The first column already has a usable pivot in row 1. Clearing below that pivot gives

$$\begin{bmatrix} 1 & 2 & 0 & 1 & 0 & 2 & 1 \\ 0 & 0 & 1 & -1 & 1 & 0 & 2 \\ 0 & 0 & 1 & -1 & 2 & 1 & -1 \\ 0 & 0 & 3 & -3 & 4 & 1 & 3 \end{bmatrix}.$$

Now row 2 supplies the next pivot. Use it to remove the matching entries below:

$$R_3\leftarrow R_3-R_2, \qquad R_4\leftarrow R_4-3R_2.$$

After also clearing the duplicate row created by the next pivot, one clean echelon stage is

$$\begin{bmatrix} 1 & 2 & 0 & 1 & 0 & 2 & 1 \\ 0 & 0 & 1 & -1 & 1 & 0 & 2 \\ 0 & 0 & 0 & 0 & 1 & 1 & -3 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}.$$

This is the point where you should pause and read the structure: pivot columns are columns $1$, $3$, and $5$; free columns are columns $2$, $4$, and $6$. To reach RREF, clear the entry above the pivot in column $5$:

$$R_2\leftarrow R_2-R_3.$$

The final reduced form is

$$C'= \begin{bmatrix} 1 & 2 & 0 & 1 & 0 & 2 & 1 \\ 0 & 0 & 1 & -1 & 0 & -1 & 5 \\ 0 & 0 & 0 & 0 & 1 & 1 & -3 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}.$$

Let

$$x_2=u,\qquad x_4=v,\qquad x_6=w.$$

Then the pivot equations read

$$\begin{aligned} x_1+2x_2+x_4+2x_6 &= 1,\\ x_3-x_4-x_6 &= 5,\\ x_5+x_6 &= -3. \end{aligned}$$

So every solution has the form

$$x= \begin{bmatrix} 1\\0\\5\\0\\-3\\0 \end{bmatrix} +u \begin{bmatrix} -2\\1\\0\\0\\0\\0 \end{bmatrix} +v \begin{bmatrix} -1\\0\\1\\1\\0\\0 \end{bmatrix} +w \begin{bmatrix} -2\\0\\1\\0\\-1\\1 \end{bmatrix}.$$

This example illustrates the real purpose of a long reduction: not merely to produce zeros, but to expose the pivot/free-variable pattern from which the whole solution set follows.

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

$$\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

$$\begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix},$$

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

Worked example

When a matrix is almost RREF

Sometimes a matrix is very close to RREF, but one pivot column has not yet been cleaned. For example,

$$\begin{bmatrix} 1 & 3 & 0 & 1 & 2 & 4 \\ 0 & 0 & 1 & 1 & 0 & -1 \\ 0 & 0 & 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}$$

is not RREF because the pivot in column $5$ has a $2$ above it. The single move

$$R_1\leftarrow R_1-2R_3$$

gives

$$\begin{bmatrix} 1 & 3 & 0 & 1 & 0 & -2 \\ 0 & 0 & 1 & 1 & 0 & -1 \\ 0 & 0 & 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}.$$

Now the pivot columns are clean, so the matrix is in RREF. The free variables are $x_2$ and $x_4$; with $x_2=s$ and $x_4=t$, the solution is

$$x= \begin{bmatrix} -2\\0\\-1\\0\\3 \end{bmatrix} +s \begin{bmatrix} -3\\1\\0\\0\\0 \end{bmatrix} +t \begin{bmatrix} -1\\0\\-1\\1\\0 \end{bmatrix}.$$

A skipped column is meaningful information

Worked example

Start with a zero column and still finish the algorithm

Treat the last column as the constants column in a system with three unknowns:

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

The first coefficient column is zero, so there is no pivot to find there. The first pivot is in column two. Normalize both rows, then clear the entry above the second pivot:

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

The result says $x_2=1$ and $x_3=1$. No equation restricts $x_1$, so all solutions are $(t,1,1)$ with $t\in\mathbb R$. Substitution into the original rows gives $2+4=6$ and $3=3$, regardless of $t$. Skipping column one did not skip an equation or lose a condition; the variable was absent from every equation from the beginning.

This example also shows why a pivot need not lie on the main diagonal. Echelon form is a staircase determined by leading entries, not a demand that the first row have a pivot in the first column. In larger matrices, several nonpivot columns can appear between successive pivots.

When the matrix is augmented, variable columns and the constants column must remain distinct. A pivot in the last column represents a contradiction, not an extra determined variable. First check consistency; only then describe the nonpivot coefficient columns as freely assignable coordinates of solutions. A nonpivot column need not be a zero column: its entries can record how a free variable influences several pivot variables.

For example, the column containing the coefficients $3$ and $-2$ in the earlier structural reading is nonpivot although it is not zero. Its variable may be chosen freely, but the pivot variables must then adjust. “Free” means unconstrained as an independent choice, not irrelevant to the remaining equations.

Checking a long calculation without repeating it

For each displayed arrow, verify the targeted entry first, then verify the rest of the affected row, especially the last column. Next inspect the structural claim: a matrix called REF must have the staircase and zero rows at the bottom; a matrix called RREF must also have leading ones and cleaned pivot columns. These checks catch different errors. Correct arithmetic can still stop short of RREF, and a matrix with the right visual pattern can still come from incorrect arithmetic.

Finally substitute the parameterization into the reduced equations. Because every arrow was reversible, the same parameterization then solves the original system. Setting all free parameters to zero gives one easy numerical check, but a full check retains the parameters and verifies their coefficients as well. This prevents a sign error in a direction vector from hiding behind an accidentally correct particular 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

Checkpoint

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

Swap rows when the current pivot position is unusable, for example when it is $0$ but a nonzero entry appears below it in the same column. The row swap moves a usable pivot into place so elimination can continue.

Checkpoint

Is $\left[\begin{array}{ccc|c}0&0&0&1\end{array}\right]$ a harmless row?

Translate the row back into an equation before you answer.

Solution · Answer

No. It represents $0 = 1$, which is a contradiction. That means the system is inconsistent and has no solution.

Checkpoint

In the longer reduction above, why are $x_2$, $x_4$, and $x_6$ free?

Look at the final RREF $C'$. Which variable columns contain leading $1$s?

Solution · Answer

The leading $1$s are in columns $1$, $3$, and $5$. Therefore columns $2$, $4$, and $6$ have no pivots, so $x_2$, $x_4$, and $x_6$ are free variables.

Exercises

Exercise 1

Start from

$$\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

The first pivot is already the $1$ in row 1, column 1. The entry beneath it is $2$, so the natural move is

$$R_2 \leftarrow R_2 - 2R_1.$$

That operation clears column 1 below the pivot in one step.

Exercise 2

Consider the matrix

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

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

Solution · Guided solution for exercise 2

There is no contradiction row, so the system is not inconsistent. But column 3 has no pivot, which means there is a free variable. Therefore the system has infinitely many solutions.

Exercise 3

Start from

$$\begin{bmatrix} 1 & 3 & 0 & 1 & 2 & 4 \\ 0 & 0 & 1 & 1 & 0 & -1 \\ 0 & 0 & 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}.$$

Which single row operation turns this matrix into RREF?

Solution · Guided solution for exercise 3

The pivot in column $5$ is the $1$ in row 3. The only nonzero entry elsewhere in that pivot column is the $2$ in row 1, so subtract twice row 3 from row 1:

$$R_1\leftarrow R_1-2R_3.$$

Exercise 4

For the RREF matrix

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

set $x_2=u$, $x_4=v$, and $x_6=w$. Write $x_1$, $x_3$, and $x_5$ in terms of $u$, $v$, and $w$.

Solution · Guided solution for exercise 4

Read the three nonzero rows:

$$\begin{aligned} x_1+2u+v+2w &= 1,\\ x_3-v-w &= 5,\\ x_5+w &= -3. \end{aligned}$$

Therefore

$$x_1=1-2u-v-2w,\qquad x_3=5+v+w,\qquad x_5=-3-w.$$

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.