Echelon Forms and Row Reduction

Elementary Row Operations

Definition 59: Elementary Row Operation

An elementary row operation on a matrix $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ is one of the following operations:

Row swap ( $𝑅_{𝑖} \leftrightarrow 𝑅_{𝑗}$ ). Interchange the $𝑖$ ^th and $𝑗$ ^th rows of $𝐴$ with $𝑖 \neq 𝑗$ .
Row scaling ( $𝑅_{𝑖} \leftarrow 𝑐 𝑅_{𝑖}$ ). Scale the $𝑖$ ^th row of $𝐴$ by $𝑐$ .
Row replacement ( $𝑅_{𝑖} \leftarrow 𝑅_{𝑖} + 𝑐 𝑅_{𝑗}$ ). Add $𝑐$ times the $𝑗$ ^th row to the $𝑖$ ^th row.

Where $1 \leq 𝑖 \neq 𝑗 \leq 𝑚$ and $𝑐 \in 𝐹$ is a scalar such that $𝑐 \neq 0$ .

Definition 60: Elementary Matrix

An elementary matrix $𝐸 \in 𝐹^{𝑛 \times 𝑛}$ is a square matrix obtained by applying a single elementary row operation to the identity matrix $𝐼_{𝑛}$ .

Corollary 31: Elementary Row Operations as Matrix Multiplication

Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ be a matrix and $𝐸 \in 𝐹^{𝑚 \times 𝑚}$ be an elementary matrix obtained by applying an elementary row operation $𝑅$ to $𝐼_{𝑚}$ . Then the matrix product $𝐸 𝐴$ is the matrix obtained by applying the row operation $𝑅$ to $𝐴$ .

Notation: Specifying Elementary Matrices

Let $𝐼$ be the identity matrix.

$𝐸 [𝑅_{𝑖} \leftrightarrow 𝑅_{𝑗}]$ denotes the elementary matrix after applying $𝑅_{𝑖} \leftrightarrow 𝑅_{𝑗}$ to $𝐼$ with $𝑖 \neq 𝑗$ .
$𝐸 [𝑅_{𝑖} \leftarrow 𝑐 𝑅_{𝑖}]$ denotes the elementary matrix after applying $𝑅_{𝑖} \leftarrow 𝑐 𝑅_{𝑖}$ to $𝐼$ .
$𝐸 [𝑅_{𝑖} \leftarrow 𝑅_{𝑖} + 𝑐 𝑅_{𝑗}]$ denotes the elementary matrix after applying $𝑅_{𝑖} \leftarrow 𝑅_{𝑖} + 𝑐 𝑅_{𝑗}$ to $𝐼$ .

This allows us to describe an arbitrary matrix $𝐴 \in 𝐹^{𝑛 \times 𝑝}$ after applying an elementary row operation $𝑅$ to $𝐴$ by writing $𝐸 [𝑅] 𝐴$ .

Definition 61: Row Equivalence

Let $𝐴, 𝐵 \in 𝐹^{𝑚 \times 𝑛}$ be matrices. We say that $𝐴$ and $𝐵$ are row equivalent, denoted $𝐴 \sim 𝐵$ , if there exists a finite sequence of elementary row operations that transforms $𝐴$ into $𝐵$ . That is, there exists a finite sequence of elementary matrices $𝐸_{1}, 𝐸_{2}, \dots, 𝐸_{𝑘}$ such that $𝐵 = 𝐸_{𝑘} 𝐸_{𝑘 - 1} \dots 𝐸_{1} 𝐴$ .

Proposition 13: Row Equivalence is an Equivalence Relation

Let $𝐴, 𝐵, 𝐶 \in 𝐹^{𝑚 \times 𝑛}$ be matrices, and let $\sim$ denote row equivalence. Then the following hold:

Reflexivity. $𝐴 \sim 𝐴$ .
Symmetry. If $𝐴 \sim 𝐵$ , then $𝐵 \sim 𝐴$ .
Transitivity. If $𝐴 \sim 𝐵$ and $𝐵 \sim 𝐶$ , then $𝐴 \sim 𝐶$ .

Proposition 14: Invertibility of Elementary Matrices

Every elementary matrix is invertible, and its inverse is also an elementary matrix.

Theorem 52: Alternative Characterization of Invertibility

Let $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ . Then $𝐴$ is invertible if and only if $𝐴$ is row equivalent to the identity matrix $𝐼_{𝑛}$ .

Proof: Alternative Characterization of Invertibility.

Let

𝐴 \in 𝐹^{𝑛 \times 𝑛}

Echelon Forms

Definition 62: Row Echelon Form

A matrix $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ is in row echelon form (ref) if it satisfies the following conditions:

Separated. All nonzero rows are above any rows of all zeros.
Triangular. The leading entry of each nonzero row (called a pivot) is in a column to the right of the leading entry of the previous row.
Zeroed Below. All entries in a column below a pivot are zeros.

Theorem 53: Existence of Row Echelon Form

Every matrix is row equivalent to at least one matrix in row echelon form.

Definition 63: Reduced Row Echelon Form

A matrix is in reduced row echelon form (rref) if it is in row echelon form and additionally satisfies:

Leading Ones. The leading entry in each nonzero row is $1$ .
Unique Pivots. Each leading $1$ is the only nonzero entry in its column.

Theorem 54: Existence and Uniqueness of Reduced Row Echelon Form

Every matrix is row equivalent to exactly one reduced row echelon form.

Terminology

Let $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ be a matrix in row echelon form. A pivot is a leading nonzero entry of a nonzero row. A pivot column of $𝐴$ is a column that contains a pivot. A pivot row of $𝐴$ is a row that contains a pivot.

Row Reduction Algorithms

Algorithm 1: Gaussian Elimination

Definition 64: LU Factorization

An LU factorization of a matrix $𝐴$ is a factorization of $𝐴$ into the product of a lower triangular matrix $𝐿$ and an upper triangular matrix $𝑈$ , i.e. $𝐴 = 𝐿 𝑈$ .