Elementary Row Operations, Echelon Forms and Matrix Equivalence

The three elementary row operations (swap two rows, multiply a row by a nonzero number, add a multiple of one row to another) transform any matrix into a row echelon form, and then into a unique reduced row echelon form (RREF); two matrices are row equivalent if one can be obtained from the other by such operations. In brief: the matrix [[1, 2, 1, 4], [2, 4, 0, 2], [1, 2, 3, 10]] reduces to [[1, 2, 0, 1], [0, 0, 1, 3], [0, 0, 0, 0]], which has two pivots, so its rank is 2.

Row reduction is the basic algorithm of linear algebra: it solves systems, finds inverses and ranks, and tests independence. This guide defines the operations, the echelon forms and pivots, the uniqueness of the RREF, elementary matrices, and the notions of row equivalence and matrix equivalence, with worked examples and a table.

What are the elementary row operations?

There are three types, each reversible by an operation of the same type:

• Swap two rows: R_i ↔ R_j.
• Scale a row by a nonzero number c: R_i → c R_i.
• Add a multiple of one row to another: R_i → R_i + c R_j.

These operations do not change the solution set of a system whose augmented matrix is being transformed, and they do not change the row space.

What are echelon and reduced echelon forms?

A matrix is in row echelon form (REF) if all zero rows are at the bottom and the first nonzero entry of each row (its leading entry, or pivot) is strictly to the right of the pivot in the row above. It is in reduced row echelon form (RREF) if additionally every pivot equals 1 and is the only nonzero entry in its column. The columns containing pivots are pivot columns. Every matrix is row equivalent to exactly one matrix in RREF, so the RREF is a canonical form; the echelon form (REF) itself is not unique.

Example 1: recognizing the forms

[[1, 3, 0, 2], [0, 0, 1, 4], [0, 0, 0, 0]] is in RREF (pivots in columns 1 and 3). [[2, 1, 5], [0, 3, 1]] is in REF but not RREF, since the pivots are 2 and 3, and the first row has the extra entry 1 above the second pivot. [[0, 1], [1, 0]] is not in any echelon form: the second pivot is to the left of the first.

How do you reduce a matrix step by step?

Work column by column from the left: choose a pivot (swap a nonzero entry into the pivot position), clear the entries below it using the third operation (forward elimination) to reach REF, and then, working from the bottom, scale the pivots to 1 and clear the entries above them to reach RREF.

Example 2: a rank-deficient matrix

A = [[1, 2, 1, 4], [2, 4, 0, 2], [1, 2, 3, 10]].

• R₂ → R₂ − 2R₁ = (0, 0, −2, −6), and R₃ → R₃ − R₁ = (0, 0, 2, 6).
• R₃ → R₃ + R₂ = (0, 0, 0, 0). Now the matrix is in REF with the pivots in columns 1 and 3.
• R₂ → −R₂/2 = (0, 0, 1, 3), then R₁ → R₁ − R₂ = (1, 2, 0, 1).

The RREF is [[1, 2, 0, 1], [0, 0, 1, 3], [0, 0, 0, 0]], with the rank 2.

Example 3: reduction to the identity

B = [[0, 2, 1], [1, 1, 0], [2, 1, 3]]. Swap R₁ ↔ R₂: [[1, 1, 0], [0, 2, 1], [2, 1, 3]]. R₃ → R₃ − 2R₁: (0, −1, 3). R₂ → R₂/2: (0, 1, 1/2). R₃ → R₃ + R₂: (0, 0, 7/2). R₃ → (2/7)R₃: (0, 0, 1). R₂ → R₂ − (1/2)R₃: (0, 1, 0). R₁ → R₁ − R₂: (1, 0, 0). The result is the identity matrix, so B has the rank 3 and is invertible.

What are elementary matrices?

An elementary matrix is obtained by applying one row operation to the identity matrix. Multiplying A on the left by it performs that operation on A. For 3 × 3 matrices: R₂ → R₂ − 2R₁ corresponds to E = [[1, 0, 0], [−2, 1, 0], [0, 0, 1]]; the swap R₁ ↔ R₂ corresponds to [[0, 1, 0], [1, 0, 0], [0, 0, 1]]. Each elementary matrix is invertible, and its inverse is the elementary matrix of the reverse operation: E⁻¹ = [[1, 0, 0], [2, 1, 0], [0, 0, 1]].

Example 4: an elementary matrix at work

For A = [[1, 2], [3, 4]], the operation R₂ → R₂ − 3R₁ is [[1, 0], [−3, 1]] · A = [[1, 2], [0, −2]] ✓. A matrix is invertible exactly when it is a product of elementary matrices.

What does matrix equivalence mean?

Matrices A and B are row equivalent if B = PA for an invertible P (a product of elementary matrices). They are equivalent (in the broad sense) if B = PAQ with invertible P and Q, which allows column operations too. Two m × n matrices are equivalent exactly when they have the same rank. Every matrix of rank r is equivalent to the canonical matrix [[I_r, O], [O, O]]. Row equivalence is finer: it additionally preserves the row space and the null space, and two matrices are row equivalent exactly when they have the same RREF.

Example 5: testing row equivalence

M = [[1, 2], [2, 4]] has the RREF [[1, 2], [0, 0]]. N = [[3, 6], [1, 2]] has the RREF [[1, 2], [0, 0]]. The RREFs agree, so M and N are row equivalent. K = [[1, 0], [0, 0]] has the same rank 1, so it is equivalent to M, but its RREF is different, so K is not row equivalent to M.

Table of operations

Where does row reduction come from?

An elimination procedure on arrays of numbers appears in the Chinese text Nine Chapters on the Mathematical Art (compiled around the first century AD), centuries before it was associated with Gauss. Carl Friedrich Gauss used elimination in his work on least squares at the beginning of the nineteenth century, and Wilhelm Jordan popularized the version that reduces to a diagonal form (1888). The description in terms of matrices and elementary matrices belongs to the matrix algebra developed from Cayley’s work in the second half of the nineteenth century.

Which mistakes are common?

Forgetting that scaling needs a nonzero number

Multiplying a row by 0 is not an elementary operation: it destroys information and is not reversible.

Operating on two rows at once

Do one operation at a time, or make sure that the rows used are not being changed in the same step.

Confusing REF with RREF

The REF is not unique, the RREF is. When comparing matrices, compare RREFs.

Applying column operations to a system

Column operations change the unknowns and, unlike row operations, do not preserve the solution set of the system.