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.

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 2.3.1

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

Theorem 2.3.2

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

One full elimination path

Consider the 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 2.3.3

(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}.$$

This matrix is in REF. Read the equations from bottom to top:

$$-z=-4\ \Longrightarrow\ z=4,\qquad y+z=1\ \Longrightarrow\ y=-3,\qquad x+2y+2z=4\ \Longrightarrow\ x=2.$$

The system is already solved. Continuing to RREF records these substitutions in the matrix itself, so that each variable's value can be read directly.

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

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.

See the pivot staircase

The following sequence keeps the active pivot and the entries being cleared visible at each stage of the same reduction.

Try the same path interactively

In the stepper, compare each row operation with the entries it clears and check that the zeros in earlier pivot columns remain intact.

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 2.3.4

(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 2.3.5

(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 2.3.6

(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 2.3.7

(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 need not be RREF)

Clearing the entries below each pivot produces REF, which is enough for back-substitution. The result may already be RREF, but that requires a separate check: every pivot must be $1$, with zeros everywhere else in its column.

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

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.

Quick check

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

Quick check

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