Section 1.2 Row Reduction and Echelon Forms

Objective

Use the row reduction algorithm to analyze linear systems. For example, to answer the fundamental existence and uniqueness questions.

(I) Row Reduction Algorithm

Definitions

Leading Entry: The leading entry of a row refers to the leftmost nonzero entry in a nonzero row.

Row Echelon Form (REF)

A rectangular matrix is in echelon form (or row echelon form) if it has the following 3 properties:

All nonzero rows are above any row of all zeros.
Each leading entry of a row is in a column to the right of the leading entry of the row above it.
All entries in a column below a leading entry are zeros.

Reduced Row Echelon Form (RREF)

If a matrix in echelon form satisfies the following additional conditions, then it is in reduced echelon form:

The leading entry in each nonzero row is 1.
Each leading 1 is the only nonzero entry in its column.

Consider the following matrix:

\[ \begin{bmatrix} 0 & \mathbf{-3} & 2 & 1 \\ 0 & 0 & \mathbf{-4} & 8 \\ 0 & 0 & 0 & \mathbf{\frac{5}{2}} \\ 0 & 0 & 0 & 0 \end{bmatrix} \]

The bolded values are the leading entries. This matrix is in REF, but not in RREF.

Example 1: Echelon Forms

The following matrices illustrate echelon forms. Let \(\blacksquare\) represent any nonzero value, and \(*\) represent any value (including zero).

Echelon Form (REF):

\begin{bmatrix} \blacksquare & * & * & * \\ 0 & \blacksquare & * & * \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}, \quad \begin{bmatrix} 0 & \blacksquare & * & * & * & * & * \\ 0 & 0 & 0 & \blacksquare & * & * & * \\ 0 & 0 & 0 & 0 & \blacksquare & * & * \\ 0 & 0 & 0 & 0 & 0 & \blacksquare & * \end{bmatrix}

Reduced Echelon Form (RREF):

\begin{bmatrix} 1 & 0 & * & * \\ 0 & 1 & * & * \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}, \quad \begin{bmatrix} 0 & 1 & * & 0 & 0 & 0 & * \\ 0 & 0 & 0 & 1 & 0 & 0 & * \\ 0 & 0 & 0 & 0 & 1 & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 1 & * \end{bmatrix}

Theorem 1: Uniqueness of the RREF

Each matrix is row equivalent to one and only one reduced echelon matrix. (Proved in Appendix A)

Pivot Positions

Pivot Position: A pivot position in a matrix \(A\) is a location in \(A\) that corresponds to a leading 1 in the RREF.

Pivot Column: A pivot column is a column of \(A\) that contains a pivot position.

The Row Reduction Algorithm

Forward Phase:

Step 1: Begin with the leftmost nonzero column. This is a pivot column. The pivot position is at the top.
Step 2: Select a nonzero entry in the pivot column as a pivot. If necessary, interchange rows to move this entry into the pivot position.
Step 3: Use row replacement operations to create zeros in all positions below the pivot.
Step 4: Ignore the row containing the pivot position and all rows above it. Apply Steps 1–3 to the submatrix that remains. Repeat the process until there are no more nonzero rows to modify.

Backward Phase:

Step 5: Beginning with the rightmost pivot and working upward and to the left, create zeros above each pivot. If a pivot is not 1, make it 1 by a scaling operation.

Example 2: Executing Row Reduction

Row reduce the matrix \(A\) to REF and then RREF, and locate the pivot columns.

Forward Phase (To REF):

\( \begin{aligned} A = \begin{bmatrix} 0 & -3 & -6 & -12 \\ -1 & -2 & -1 & 1 \\ 1 & 4 & 5 & 7 \end{bmatrix} &\xrightarrow{R_1 \leftrightarrow R_3} \begin{bmatrix} 1 & 4 & 5 & 7 \\ -1 & -2 & -1 & 1 \\ 0 & -3 & -6 & -12 \end{bmatrix} \\ &\xrightarrow{R_2 = R_1 + R_2} \begin{bmatrix} 1 & 4 & 5 & 7 \\ 0 & 2 & 4 & 8 \\ 0 & -3 & -6 & -12 \end{bmatrix} \\ &\xrightarrow[\frac{-1}{3}R_3]{\frac{1}{2}R_2} \begin{bmatrix} 1 & 4 & 5 & 7 \\ 0 & 1 & 2 & 4 \\ 0 & 1 & 2 & 4 \end{bmatrix} \\ &\xrightarrow{R_3 = -R_2 + R_3} \begin{bmatrix} 1 & 4 & 5 & 7 \\ 0 & 1 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} \quad \text{(REF)} \end{aligned} \)

Backward Phase (To RREF):

\( \begin{aligned} \begin{bmatrix} 1 & 4 & 5 & 7 \\ 0 & 1 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} &\xrightarrow{R_1 = -4R_2 + R_1} \begin{bmatrix} 1 & 0 & -3 & -9 \\ 0 & 1 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} \quad \text{(RREF)} \end{aligned} \)

The pivot columns are columns 1 and 2 of matrix \(A\). Thus, their corresponding positions in the original matrix \(A\) at coordinates (1,1) and (2,2) are the pivot positions.

(II) Solutions of Linear Systems

The variables corresponding to pivot columns are called basic variables. Other variables are called free variables.

Example 3: Extracting the General Solution

Find the general solution of the linear system whose augmented matrix has been reduced to REF:

\begin{bmatrix} 1 & 6 & 2 & -5 & -2 & -4 \\ 0 & 0 & 2 & -8 & -1 & 3 \\ 0 & 0 & 0 & 0 & 1 & 7 \end{bmatrix} \quad \text{(REF)}

Step 1: Reduce to RREF

\( \begin{aligned} &\xrightarrow{R_2 = R_3 + R_2} \begin{bmatrix} 1 & 6 & 2 & -5 & -2 & -4 \\ 0 & 0 & 2 & -8 & 0 & 10 \\ 0 & 0 & 0 & 0 & 1 & 7 \end{bmatrix} \\ &\xrightarrow{R_1 = 2R_3 + R_1} \begin{bmatrix} 1 & 6 & 2 & -5 & 0 & 10 \\ 0 & 0 & 2 & -8 & 0 & 10 \\ 0 & 0 & 0 & 0 & 1 & 7 \end{bmatrix} \\ &\xrightarrow{\frac{1}{2}R_2} \begin{bmatrix} 1 & 6 & 2 & -5 & 0 & 10 \\ 0 & 0 & 1 & -4 & 0 & 5 \\ 0 & 0 & 0 & 0 & 1 & 7 \end{bmatrix} \\ &\xrightarrow{R_1 = -2R_2 + R_1} \begin{bmatrix} 1 & 6 & 0 & 3 & 0 & 0 \\ 0 & 0 & 1 & -4 & 0 & 5 \\ 0 & 0 & 0 & 0 & 1 & 7 \end{bmatrix} \quad \text{(RREF)} \end{aligned} \)

Step 2: Write the Corresponding Equations

\begin{cases} x_1 + 6x_2 + 3x_4 = 0 \\ x_3 - 4x_4 = 5 \\ x_5 = 7 \end{cases}

Step 3: Identify Variables

\(x_1\), \(x_3\), and \(x_5\) are basic variables (pivot columns 1, 3, 5).
\(x_2\) and \(x_4\) are free variables (or parameters).

Step 4: Parametric Description of the Solution Set

\begin{cases} x_1 = -6x_2 - 3x_4 \\ x_2 \text{ is free} \\ x_3 = 4x_4 + 5 \\ x_4 \text{ is free} \\ x_5 = 7 \end{cases}

(III) Existence and Uniqueness Questions

Example 4

Determine the existence and uniqueness of the solutions to the system:

\begin{cases} -3x_2 - 6x_3 = -12 \\ -x_1 - 2x_2 - x_3 = 1 \\ x_1 + 4x_2 + 5x_3 = 7 \end{cases}

(Note: Translating the system into an augmented matrix yields the matrix \(A\) from Example 2).

REF is enough to answer this question. By Example 2, the system is consistent (no row of the form \([0 \dots 0 \ | \ b]\)), and there are infinitely many solutions since \(x_3\) is a free variable (column 3 is not a pivot column).

Theorem 2: Existence and Uniqueness Theorem

Existence: A linear system is consistent if and only if the rightmost column of the augmented matrix is NOT a pivot column. That is, if and only if an echelon form has no row of the form:

\begin{bmatrix} 0 & 0 & \dots & 0 & b \end{bmatrix} \quad \text{with } b \neq 0

Uniqueness: If it is consistent, then the solution set contains:

A unique solution when there is no free variable.
Infinitely many solutions when there is at least one free variable.

                Summary: Using Row Reduction to Solve a Linear System
                Write the augmented matrix of the system.
Find the REF. Determine whether it's consistent or not. Find the RREF if consistent.
Write the system of equations corresponding to the matrix in Step 2.
Rewrite each nonzero equation from Step 3 so that each basic variable is expressed in terms of any free variable(s).

            