Elementary row operations are three basic, reversible transformations applied to the rows of a matrix: interchanging two rows, multiplying a row by a nonzero scalar, and adding a scalar multiple of one row to another. They are fundamental tools in linear algebra, especially for solving a system of linear equations by Gaussian elimination. Each operation preserves the solution set when applied to the entire augmented matrix of a linear system, although it need not preserve the individual entries, determinant, or eigenvalues of the coefficient matrix.
The three operations
Let be an matrix with entries in a field , and let denote its -th row. The standard elementary row operations are:
| Operation | Notation | Conditions |
|---|---|---|
| Row interchange | ||
| Row scaling | , | |
| Row replacement | , |
In row replacement, only the target row changes; the source row remains unchanged. Some definitions exclude , since it produces no change.
Each operation has an inverse of the same type:
- A row interchange is undone by the same interchange.
- Scaling by is undone by scaling by .
- Adding to is undone by adding to .
The requirement that a scaling factor be nonzero is essential. Multiplying a row by zero can destroy information and cannot generally be reversed.
A replacement such as
can be performed by a scaling followed by a row replacement. It is therefore reversible, but it is not generally counted as one elementary operation under the standard three-operation definition.
Why solutions are preserved
Consider a system written in matrix form as
Its augmented matrix is
which records both the coefficients and the right-hand side.
Interchanging two rows merely changes the order of the equations. Multiplying an equation by a nonzero scalar gives an equivalent equation. Adding a multiple of one equation to another also preserves the simultaneous solutions, because the operation can be reversed.
The reversibility supplies both directions of the equivalence: every solution of the original system satisfies the transformed system, and every solution of the transformed system satisfies the original.
Operations must be applied to the entire augmented row, including the right-hand-side entry. Changing the coefficient matrix without making the corresponding change to generally changes the problem.
Row equivalence and echelon forms
Two matrices of the same size are row equivalent if one can be obtained from the other by a finite sequence of elementary row operations. Row equivalence is an equivalence relation: it is reflexive, symmetric, and transitive.
Every matrix over a field can be transformed into row echelon form, characterized by the following conditions:
- All zero rows occur below all nonzero rows.
- The leading nonzero entry of each nonzero row lies strictly to the right of the leading entry in the preceding row.
- Entries below each leading entry are zero.
The leading entries are called pivots. An echelon form is not generally unique.
Further operations produce reduced row echelon form, in which every pivot equals and is the only nonzero entry in its column. Every matrix has exactly one reduced row echelon form. Consequently, two matrices are row equivalent if and only if they have the same reduced row echelon form.
Gaussian elimination usually obtains echelon form, after which back substitution solves the system. Gauss–Jordan elimination continues by clearing entries above pivots to obtain reduced row echelon form.
Worked example
Consider
Its augmented matrix is
First apply :
Next apply :
Finally apply :
The solution is therefore , .
More generally, a transformed augmented row
expresses the contradiction , so the system has no solution. If the system is consistent, variables associated with nonpivot columns are free variables. Over an infinite field, the presence of a free variable gives infinitely many solutions; over a finite field, it gives a finite family of solutions.
Elementary matrices
An elementary matrix is obtained by applying one elementary row operation to an identity matrix. If is obtained from in this way, then
performs the same operation on any matrix , through ordinary matrix multiplication.
For example,
implements .
Every elementary matrix is invertible, and its inverse is the elementary matrix associated with the reverse operation. Thus a sequence of row operations can be written
where is invertible.
Conversely, if for an invertible matrix , then and are row equivalent: every invertible square matrix can be expressed as a product of elementary matrices.
For a linear system, this representation gives
which provides a compact algebraic proof of solution preservation.
Preserved and nonpreserved properties
Rank, row space, and null space
Elementary row operations preserve rank. In particular, the rank is the number of pivots in an echelon form.
They also preserve the row space, the span of the rows. Each transformed row is a linear combination of the original rows, so the new row space is contained in the original one. Reversibility gives the opposite inclusion.
The null space is also unchanged. If with invertible, then
The column space, however, is generally not preserved as the same subspace of . Instead,
Its dimension is unchanged, and the linear dependence relations among corresponding columns are preserved. Accordingly, pivot-column indices found by row reduction identify columns of the original matrix that form a basis for its column space.
Determinant
For square matrices, the effect on the determinant depends on the operation:
- Interchanging two rows multiplies the determinant by .
- Multiplying a row by multiplies the determinant by .
- Adding a multiple of another row leaves the determinant unchanged.
These rules make it possible to compute determinants by reducing a matrix to triangular form and tracking the changes. The determinant of a triangular matrix is the product of its diagonal entries.
Eigenvalues and related quantities
Row operations do not generally preserve eigenvalues, trace, symmetry, or lengths and angles. For example, scaling one row of an identity matrix can change both its trace and its eigenvalues.
Row equivalence should therefore be distinguished from matrix similarity. Row operations give , whereas a similarity transformation has the form .
Main applications
Solving linear systems and computing rank
Row reduction reveals whether a system is consistent and which variables are determined by pivots. For a consistent system with unknowns and coefficient rank , the solutions can be written
where is a particular solution and the null space has dimension .
Computing matrix inverses
For a square matrix , form the augmented matrix
If row operations transform the left block into , then
yielding the inverse matrix. Indeed, the accumulated operations give , so .
If the left block cannot be reduced to the identity, is singular and has no inverse.
Constructing factorizations
The elimination steps underlying row reduction also lead to LU decomposition. When elimination can proceed without row interchanges, the multipliers can be organized into a lower triangular matrix , giving
with upper triangular. With suitable row interchanges, a common form is
where is a permutation matrix. Such factorizations allow the same coefficient matrix to be used efficiently with several right-hand sides.
Numerical and algebraic limitations
Floating-point computation
Elementary row operations are exact algebraic identities, but implementations using floating-point arithmetic introduce rounding errors. Dividing by a very small pivot can create large intermediate values and amplify those errors.
Partial pivoting addresses this problem by selecting an entry of largest absolute value in the active part of the current pivot column and moving it into the pivot position. This usually improves numerical stability, although it does not eliminate every possible source of numerical error.
For dense square matrices, elimination requires arithmetic operations in the standard implementation. With sparse matrices, elimination may create new nonzero entries, called fill-in, so row and column ordering can strongly affect storage and computational cost.
Coefficient domains
The standard theory assumes coefficients in a field, where every nonzero element has a multiplicative inverse. Over a general ring, reversible row scaling requires the multiplier to be a unit, an element with a multiplicative inverse in that ring.
For example, multiplying an integer row by is reversible over the rational numbers but not by an integer row operation that preserves the integer row module. Problems involving integer solutions therefore require additional care; ordinary row reduction over a field does not by itself encode all integer divisibility constraints.
Relation to column operations
Elementary column operations are defined analogously and correspond to multiplication by elementary matrices on the right. They preserve rank and column space, but generally change the row space and null space.
For solving , row operations replace equations by equivalent equations without changing the variables. Column operations act on the coefficient columns and must be accompanied by an appropriate change of variables if the transformed system is to represent the original problem.