= Row echelon form
{title2=REF}
{wiki}
= REF
{c}
{synonym}
A <matrix> over a <field> $\mathbb F$ is in <row echelon form> when all zero rows follow the nonzero rows, each nonzero row's first nonzero entry lies strictly to the right of the preceding row's first nonzero entry, and all entries below each such leading entry vanish. These leading entries are its <pivot elements>. They need not be one, and entries above them need not vanish.<Interactive Linear Algebra by Dan Margalit and others/Row Reduction>[Interactive Linear Algebra by Dan Margalit and others; §1.2.2, Echelon Forms: three echelon conditions and definition of a pivot]{ref}
The staircase turns a <linear system> into a sequence of simpler equations. For example,
$$
U=\begin{pmatrix}1&2&-1\\0&1&3\\0&0&0\\0&0&0\end{pmatrix}
$$
is in <row echelon form>, with <pivot columns> 1 and 2. Its second equation determines $x_2$ once $x_3$ is chosen; its first then determines $x_1$ by <back substitution>. It is not in <reduced row echelon form>, because the second <pivot column> contains a nonzero entry above its <pivot element>. Neither being square nor having a nonzero entry in every row is required.
<Elementary row operations> bring every <matrix> to <row echelon form>: choose a nonzero entry in the leftmost available nonzero column, interchange rows, clear entries below it, and repeat on the remaining rows and later columns. Skip columns with no remaining nonzero entry. Clearing above each <pivot element> and scaling it to one completes <reduced row echelon form>.<Interactive Linear Algebra by Dan Margalit and others/Row Reduction>[Interactive Linear Algebra by Dan Margalit and others; §1.2.3, The Row Reduction Algorithm, forward steps and Last Step]{ref}
The nonzero rows of an <row echelon form> are <linearly independent>: in a vanishing <linear combination>, inspecting the first <pivot column> forces the first coefficient to be zero, then the next forces the second, and so on. They give a <basis> of the original <row space>. The number of <pivot elements> is both the <row rank> and the <column rank>. To recover a <basis> of the original <column space>, select the corresponding original <pivot columns>; the reduced column <vectors> generally belong to a different <column space>.
Here the arithmetic is exact in the specified <field>. For <floating-point arithmetic>, deciding whether a computed entry counts as zero requires a numerical criterion; see <Tiny-pivot roundoff in Gaussian elimination> and <condition number>. An exact <row echelon form> classification alone does not settle <numerical stability>.
Back to article page
