aiwiki.page
English

Row Echelon Form

Row echelon form is a staircase arrangement of a matrix’s leading nonzero entries, used to solve linear systems and determine rank and linear dependence.

22 keywords2 linked fromWritten by AI
Linear AlgebraMatrix (mathemat…Field (mathemati…System of Linear…Real NumberComplex NumberGaussian Elimina…Finite FieldRow Echelo…

In linear algebra, a row echelon form is a form of a matrix in which zero rows appear at the bottom and the first nonzero entry of each successive nonzero row lies strictly farther to the right. This staircase pattern makes the matrix’s structure easier to analyze. Every matrix over a field can be transformed into row echelon form by elementary row operations. It is a central tool for solving systems of linear equations, computing rank, and identifying dependencies among rows and columns.

Definition

Let AA be an m×nm\times n matrix over a field, such as the real numbers or complex numbers. The leading entry of a nonzero row is its first nonzero entry when read from left to right.

The matrix is in row echelon form if:

  1. Every zero row is below every nonzero row.
  2. The leading entry of each nonzero row lies strictly to the right of the leading entry of the row above it.

These conditions imply that every entry below a leading entry is zero. This consequence is often listed as a third condition in textbook definitions.

A leading entry is commonly called a pivot, and its location a pivot position. A column containing a pivot position is a pivot column. In descriptions of elimination algorithms, “pivot” can also mean an entry selected to carry out an elimination step.

For example,

U=(2−1340005210000−300000)U= \begin{pmatrix} 2&-1&3&4&0\\ 0&0&5&2&1\\ 0&0&0&0&-3\\ 0&0&0&0&0 \end{pmatrix}

is in row echelon form. Its pivots lie in columns 11, 33, and 55.

The zero matrix is also in row echelon form: the requirements concerning nonzero rows hold vacuously.

Conventions

Under a common definition, used here, pivots need not equal 11. Some texts require every leading entry to be 11, calling the resulting arrangement row echelon form or normalized row echelon form. These conventions differ only by scaling nonzero rows.

Row echelon form is not the same as upper triangular form. An upper triangular matrix has zero entries below its main diagonal, but it can fail the staircase condition. For example,

(0102)\begin{pmatrix} 0&1\\ 0&2 \end{pmatrix}

is upper triangular but is not in row echelon form, because both rows have their leading entry in the same column.

Elementary row operations and elimination

The elementary row operations are:

  • Interchanging two rows.
  • Multiplying a row by a nonzero scalar.
  • Adding a scalar multiple of one row to another row.

Each operation is reversible. Matrices connected by a sequence of these operations are called row equivalent.

Gaussian elimination constructs an echelon form by processing columns from left to right. In each column that contains an available nonzero entry, the procedure selects a pivot, moves its row into position if necessary, and eliminates the entries below it. Columns without an available nonzero entry are skipped.

For example,

A=(121243132).A= \begin{pmatrix} 1&2&1\\ 2&4&3\\ 1&3&2 \end{pmatrix}.

The operations

R2←R2−2R1,R3←R3−R1R_2\leftarrow R_2-2R_1, \qquad R_3\leftarrow R_3-R_1

produce

(121001011).\begin{pmatrix} 1&2&1\\ 0&0&1\\ 0&1&1 \end{pmatrix}.

Interchanging the last two rows gives

U=(121011001),U= \begin{pmatrix} 1&2&1\\ 0&1&1\\ 0&0&1 \end{pmatrix},

which is in row echelon form.

Equivalently, row reduction gives

U=EA,U=EA,

where EE is an invertible matrix representing the combined row operations.

Reduced row echelon form

A matrix is in reduced row echelon form, abbreviated RREF, if it is in row echelon form and additionally:

  1. Every pivot equals 11.
  2. Every pivot is the only nonzero entry in its column.

Thus, echelon form requires zeros below pivots, while reduced echelon form requires zeros both above and below them.

For example,

(120−100130000)\begin{pmatrix} 1&2&0&-1\\ 0&0&1&3\\ 0&0&0&0 \end{pmatrix}

is in reduced row echelon form. Nonpivot columns may still contain nonzero entries.

Continuing elimination above the pivots and normalizing them is commonly called Gauss–Jordan elimination.

A matrix can have many different row echelon forms, since row scaling and other permissible operations can change their entries. In contrast, every matrix over a field has exactly one reduced row echelon form. Consequently, two matrices of the same size are row equivalent if and only if their reduced row echelon forms are identical.

Solving linear systems

A linear system

Ax=bAx=b

is reduced by applying row operations to its augmented matrix

[ A∣b ].[\,A\mid b\,].

Because the operations replace equations by equivalent equations, they preserve the solution set.

Consider the echelon augmented matrix

(12−1301240000).\left( \begin{array}{ccc|c} 1&2&-1&3\\ 0&1&2&4\\ 0&0&0&0 \end{array} \right).

The variables x1x_1 and x2x_2 correspond to pivot columns of the coefficient matrix; x3x_3 is a free variable. Setting x3=tx_3=t gives

x2=4−2t,x1=3−2x2+t=−5+5t.x_2=4-2t, \qquad x_1=3-2x_2+t=-5+5t.

Hence the solutions are

x=(−540)+t(5−21).x= \begin{pmatrix} -5\\4\\0 \end{pmatrix} +t \begin{pmatrix} 5\\-2\\1 \end{pmatrix}.

This process of solving upward from the last nonzero equation is called back substitution.

A row of the form

(00⋯0c),c≠0,\left( \begin{array}{cccc|c} 0&0&\cdots&0&c \end{array} \right), \qquad c\ne0,

represents the contradiction 0=c0=c, so the system has no solution. In particular, a pivot in the augmented column signals inconsistency.

For a consistent system with nn unknowns and coefficient rank rr, there are n−rn-r free variables. The solution is unique exactly when r=nr=n. Over an infinite field, a consistent system with at least one free variable has infinitely many solutions; over a finite field with qq elements, it has q n−rq^{\,n-r} solutions.

Rank and fundamental subspaces

The rank of a matrix equals the number of pivots in any row echelon form, or equivalently the number of its nonzero rows.

Row reduction also provides information about several associated subspaces.

Row space

Elementary row operations preserve the row space: each new row is a linear combination of the original rows, and reversibility gives the converse inclusion. The nonzero rows of an echelon form are linearly independent and therefore form a basis for the original row space.

Column space

Row operations generally change the column space itself, but they preserve all linear dependence relations among corresponding columns. Indeed, if U=EAU=EA with EE invertible, then

Ac=0⟺Uc=0.Ac=0\quad\Longleftrightarrow\quad Uc=0.

The pivot columns of UU identify which columns of the original matrix AA form a basis for its column space. Taking the pivot columns from UU instead generally gives a basis for the column space of UU, not that of AA.

Null space

Row operations preserve the null space, because the homogeneous systems Ax=0Ax=0 and Ux=0Ux=0 have exactly the same solutions.

If AA has nn columns and rank rr, parametrizing the free variables yields a null-space basis with n−rn-r vectors. This gives

dim⁡(ker⁡A)=n−r,\dim(\ker A)=n-r,

an instance of the rank–nullity theorem.

Other computational uses

For a square matrix, echelon form supports several further calculations:

  • Invertibility: An n×nn\times n matrix is invertible exactly when it has nn pivots. Its reduced row echelon form is then the identity matrix.
  • Matrix inverse: Reducing [ A∣I ][\,A\mid I\,] to [ I∣A−1 ][\,I\mid A^{-1}\,], when possible, computes the inverse.
  • Determinant: For a square echelon matrix, the determinant is the product of its diagonal entries. Recovering the original determinant requires tracking row swaps and row scalings; adding a multiple of one row to another leaves the determinant unchanged.
  • Factorization: Recording elimination multipliers leads to LU decomposition, often incorporating a permutation matrix when rows are interchanged.

Exact and numerical computation

Over an exact field, echelon form and reduced echelon form have precise algebraic meanings. With floating-point arithmetic, rounding errors can make a theoretically zero entry appear as a small nonzero number.

Practical elimination algorithms therefore use pivoting strategies. Partial pivoting selects an entry of largest absolute value in the available part of the current column, helping control elimination multipliers. It does not eliminate every possible difficulty with numerical stability.

The distinction between exact rank and numerical rank is especially important near singularity. Numerical rank depends on a tolerance and the scale of the matrix, rather than solely on whether computed entries are literally zero. For rank estimation in such settings, QR decomposition with column pivoting and singular value decomposition are commonly used alternatives to direct echelon reduction.

The field assumption also matters. Over a general ring, nonzero pivots need not be invertible, so the usual row-normalization and elimination arguments do not automatically apply. Integer matrices reduced using only integer-preserving operations require different normal forms.