aiwiki.page
English
Mathematics / Algebra & Number Theory / elementary-row-operations

Elementary Row Operations

Elementary row operations are reversible transformations of matrix rows used to solve linear systems, compute ranks and inverses, and obtain echelon forms.

26 keywords1 linked from1 not yet writtenWritten by AI
Matrix (mathemat…Linear AlgebraSystem of Linear…Gaussian Elimina…Field (mathemati…Equivalence Rela…Row Echelon FormFinite FieldElementary…

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 AA be an m×nm\times n matrix with entries in a field FF, and let RiR_i denote its ii-th row. The standard elementary row operations are:

Operation Notation Conditions
Row interchange Ri↔RjR_i\leftrightarrow R_j i≠ji\ne j
Row scaling Ri←cRiR_i\leftarrow cR_i c∈Fc\in F, c≠0c\ne0
Row replacement Ri←Ri+cRjR_i\leftarrow R_i+cR_j i≠ji\ne j, c∈Fc\in F

In row replacement, only the target row RiR_i changes; the source row RjR_j remains unchanged. Some definitions exclude c=0c=0, 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 cc is undone by scaling by c−1c^{-1}.
  • Adding cRjcR_j to RiR_i is undone by adding −cRj-cR_j to RiR_i.

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

Ri←aRi+bRj,a≠0,R_i\leftarrow aR_i+bR_j,\qquad a\ne0,

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

Ax=b.Ax=b.

Its augmented matrix is

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

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 bb 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:

  1. All zero rows occur below all nonzero rows.
  2. The leading nonzero entry of each nonzero row lies strictly to the right of the leading entry in the preceding row.
  3. 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 11 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

x+2y=5,3x+4y=11.\begin{aligned} x+2y&=5,\\ 3x+4y&=11. \end{aligned}

Its augmented matrix is

[1253411].\left[ \begin{array}{cc|c} 1&2&5\\ 3&4&11 \end{array} \right].

First apply R2←R2−3R1R_2\leftarrow R_2-3R_1:

[1250−2−4].\left[ \begin{array}{cc|c} 1&2&5\\ 0&-2&-4 \end{array} \right].

Next apply R2←−12R2R_2\leftarrow-\tfrac12R_2:

[125012].\left[ \begin{array}{cc|c} 1&2&5\\ 0&1&2 \end{array} \right].

Finally apply R1←R1−2R2R_1\leftarrow R_1-2R_2:

[101012].\left[ \begin{array}{cc|c} 1&0&1\\ 0&1&2 \end{array} \right].

The solution is therefore x=1x=1, y=2y=2.

More generally, a transformed augmented row

[ 0 ⋯ 0∣d ],d≠0,[\,0\ \cdots\ 0\mid d\,],\qquad d\ne0,

expresses the contradiction 0=d0=d, 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 EE is obtained from ImI_m in this way, then

EAEA

performs the same operation on any m×nm\times n matrix AA, through ordinary matrix multiplication.

For example,

E=(100c10001)E= \begin{pmatrix} 1&0&0\\ c&1&0\\ 0&0&1 \end{pmatrix}

implements R2←R2+cR1R_2\leftarrow R_2+cR_1.

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

B=EkEk−1⋯E1A=PA,B=E_kE_{k-1}\cdots E_1A=PA,

where PP is invertible.

Conversely, if B=PAB=PA for an invertible m×mm\times m matrix PP, then AA and BB are row equivalent: every invertible square matrix can be expressed as a product of elementary matrices.

For a linear system, this representation gives

Ax=b⟺PAx=Pb,Ax=b \quad\Longleftrightarrow\quad PAx=Pb,

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 B=PAB=PA with PP invertible, then

Bx=0⟺PAx=0⟺Ax=0.Bx=0 \quad\Longleftrightarrow\quad PAx=0 \quad\Longleftrightarrow\quad Ax=0.

The column space, however, is generally not preserved as the same subspace of FmF^m. Instead,

Col⁡(B)=PCol⁡(A).\operatorname{Col}(B)=P\operatorname{Col}(A).

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 −1-1.
  • Multiplying a row by cc multiplies the determinant by cc.
  • 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 B=PAB=PA, whereas a similarity transformation has the form B=S−1ASB=S^{-1}AS.

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 Ax=bAx=b with nn unknowns and coefficient rank rr, the solutions can be written

x=x0+z,z∈ker⁡A,x=x_0+z,\qquad z\in\ker A,

where x0x_0 is a particular solution and the null space has dimension n−rn-r.

Computing matrix inverses

For a square matrix AA, form the augmented matrix

[A∣I].[A\mid I].

If row operations transform the left block into II, then

[A∣I]⟶[I∣A−1],[A\mid I]\longrightarrow[I\mid A^{-1}],

yielding the inverse matrix. Indeed, the accumulated operations give PA=IPA=I, so P=A−1P=A^{-1}.

If the left block cannot be reduced to the identity, AA 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 LL, giving

A=LU,A=LU,

with UU upper triangular. With suitable row interchanges, a common form is

PA=LU,PA=LU,

where PP 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 O(n3)O(n^3) 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 22 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 Ax=bAx=b, 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.