Reduced row echelon form (RREF)

A row echelon form is in reduced row echelon form when every pivot element is one and is the only nonzero entry in its column.^[ref] This extra reduction displays each pivot unknown directly in terms of the free variables in a linear system. The zero matrix also satisfies the definition: it has no pivot elements.

Every matrix has exactly one reduced row echelon form under elementary row operations, with its size and column order held fixed.^[ref] Ordinary row echelon form is not unique: multiplying a nonzero row by two over the rational numbers keeps the staircase but changes the matrix. The reduced conditions remove that freedom.

For a fixed number of columns, each row space has a unique reduced matrix after zero rows are removed; at a fixed full size, the number of appended zero rows is also determined. Thus reduced row echelon form represents a vector subspace independently of the starting basis. This is the uniqueness used by Gaussian binomial coefficients to count vector subspaces over a finite field.

The fixed column order matters. Elementary column operations can change the row space, the kernel and the resulting reduced row echelon form. For instance, swapping the columns of $(12)$ over the rational numbers gives $(21)$, whose reduced row echelon form is $(11/2)$ instead of $(12)$. When solving a linear system, a column interchange also requires tracking the corresponding interchange of unknowns.

For row reduction with a parameterized right-hand side at $\tau =5$, the nonzero reduced equations areColumn 3 has no pivot element, so $x_3$ is a free variable in a linear system. Taking $x_3=t$ gives every solution:There is no further restriction on $t$. Independent substitution into the original linear system givesConversely, the two reduced equations force exactly these coordinate formulas, so no solutions have been omitted. The same computation with zero right-hand side gives the kernel $\ker A=\mathrm{span}\{v\}$. Its dimension is one. The rank-nullity theorem appears here as $2+1=3$: two pivot columns and one freely chosen coordinate account for the three unknowns.^[ref]

In general a consistent linear system has solution set $x_0+\ker A$. Subtracting $A{x}_0=b$ from $Ax=b$ proves this description in both directions. The particular solution places the affine subspace, and the kernel supplies its directions.^[ref] Over the real numbers this example is an entire line; over the rational numbers the same formula uses rational $t$. A free variable in a linear system over a finite field instead has only finitely many choices.

The pivot columns identify a different object: the original column space. Here they selectwhich form its basis, while $a_3=-7a_1+3a_2$. The corresponding reduced columns are $(1,0,0,0{)}^T$ and $(0,1,0,0{)}^T$; their linear span is a different plane. For example, every original output satisfies $y_3=y_1+y_2$, but $(1,0,0,0{)}^T$ does not. Since $E$ is an invertible matrix, column linear relations survive $EA=R$ even though the output vectors move. This is why choosing original columns at the reduced pivot positions works.

Here is a short proof that uses only the row space. For a vector subspace $W\subseteq {\mathbb{F}}^n$, let $d_j$ be the dimension of its projection map onto the first $j$ coordinates, with $d_0=0$. In any reduced row echelon form with row space $W$, $d_j$ counts the pivot columns among those first $j$ columns: later-pivot rows project to zero, while earlier-pivot rows remain linearly independent. Thus the positions where $d_j-d_{j-1}=1$ determine all pivot positions from $W$ alone.

If those positions are $p_1,\dots ,p_r$, the map sending $w\in W$ to $(w_{p_1},\dots ,w_{p_r})$ is an isomorphism $W\to {\mathbb{F}}^r$: the reduced nonzero rows map to the standard basis. Its $i$th row is therefore the unique vector of $W$ with pivot-coordinate values equal to the $i$th standard basis vector. Any other reduced row echelon form with that row space has identical nonzero rows in identical order. At a fixed matrix size, the remaining rows must be zero. Together with existence by Gaussian elimination, this proves uniqueness.