16.2 Row Echelon Form

Types: N/A
Examples: N/A
Constructions: N/A
Generalizations: N/A

Properties: N/A
Sufficiencies: N/A
Questions: N/A

Row Echelon Form

Let $U \in R^{m \times n}$ be a given matrix. We say that $U$ is in row echelon form iff $U$ satisfies the following three conditions:

All zero rows are below all nonzero rows
The column index of the first nonzero entry in a row is larger than the column index of the first nonzero entry in any previous row.
All entries in a column below a leading entry are zeros.

Remark. The conditions of row echelon form generalize the conditions of an 8.9 Upper-Triangular Matrix.
$⧫$

Let's analyze the sparsity structure some matrices and determine if they are in row echelon form.

Example

$[\begin{matrix} ⋆ & \times & \times \\ 0 & ⋆ & \times \\ 0 & 0 & ⋆ \end{matrix}]$

There are no all zero rows, so condition 1 is satisfied trivially.
Notice the "stair step" pattern. The leading entries (the first nonzero entry in the rows) go down and to the right. The column index of the leading entries is increasing from left to right, satisfying condition 2.
Underneath the stars is all zeroes. Therefore, the 3rd condition is satisfied.

Therefore, this matrix is in row echelon form.

Example

$[\begin{matrix} ⋆ & \times & \times & \times & \times & \times & \times \\ 0 & 0 & ⋆ & \times & \times & \times & \times \\ 0 & 0 & 0 & 0 & 0 & ⋆ & \times \\ 0 & 0 & 0 & 0 & 0 & 0 & \times \end{matrix}]$

There are no all zero rows, so condition 1 is satisfied trivially.
There is a "stair step" pattern, although this pattern is a bit longer than the last example. Nevertheless, the column indexes of the leading entries are still increasing from left to right. Therefore, the 2nd condition is satisfied.
Under each leading entry is all zeroes, so this is condition is also satisfied.

Therefore, this matrix is in row echelon form.

& Note that properties 2 and 3 are redundant. However, it is helpful to have 2 different ways of checking.

Example

$[\begin{matrix} 0 & ⋆ & \times & \times & \times & \times & \times & \times & \times & \times & \times \\ 0 & 0 & ⋆ & \times & \times & \times & \times & \times & \times & \times & \times \\ 0 & 0 & 0 & 0 & ⋆ & \times & \times & \times & \times & \times & \times \\ 0 & 0 & 0 & 0 & 0 & ⋆ & \times & \times & \times & \times & \times \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & ⋆ & \times & \times \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}]$

There is one all zero row at the bottom, so condition 1 is satisfied.
There is a "stair step" pattern, so condition 2 is met.
Below each star is all zeroes, so condition 3 is met.

Therefore, this matrix is in row echelon form.