Gauss–Jordan elimination is an algorithm in linear algebra that transforms a matrix into reduced row echelon form through elementary row operations. It is used to solve systems of linear equations, compute matrix inverses, determine ranks, and describe solution spaces. Unlike ordinary Gaussian elimination, which typically eliminates entries below each pivot and then uses back substitution, Gauss–Jordan elimination eliminates entries both below and above each pivot, making the final relationships between variables directly readable.
Elementary row operations
The method uses three reversible operations:
- Interchange two rows.
- Multiply a row by a nonzero scalar.
- Add a scalar multiple of one row to another row.
For a linear system written as
these operations are applied to the entire augmented matrix
Each operation changes the equations without changing their common solution set. For example, replacing one equation by itself plus a multiple of another equation is reversible by subtracting the same multiple.
The algorithm works over any field, including the real numbers, complex numbers, rational numbers, and finite fields. The essential requirement is that every nonzero pivot has a multiplicative inverse. Over a general ring, a nonzero element need not be invertible, so the same procedure is not always available.
Reduced row echelon form
A matrix is in reduced row echelon form when:
- All zero rows appear below all nonzero rows.
- The first nonzero entry in each nonzero row is , called a leading or pivot.
- Each pivot lies strictly to the right of the pivot in the preceding row.
- A pivot is the only nonzero entry in its column.
For example,
is in reduced row echelon form. Its pivot columns are the first, second, and fourth columns.
Every matrix over a field has a unique reduced row echelon form. Different valid choices of row operations may therefore produce different intermediate matrices but give the same final matrix in exact arithmetic. Ordinary row echelon form, which does not require zeros above pivots or unit pivots, is not unique.
Algorithm
A direct version of Gauss–Jordan elimination processes columns from left to right while maintaining a current pivot-row position.
- Find a pivot. In the current column, search for a nonzero entry at or below the current pivot row. If none exists, skip the column.
- Move the pivot into position. Interchange rows if necessary.
- Normalize the pivot row. Divide the entire row by its pivot entry.
- Clear the pivot column. For every other row, subtract its entry in the pivot column times the normalized pivot row.
- Advance. Move to the next row and continue searching in subsequent columns.
If is the normalized pivot row in column , the elimination step is
Earlier pivot columns remain unchanged because the new pivot row has zeros in those columns. The procedure stops when all columns have been processed or no further pivot rows are available.
Another implementation first obtains row echelon form by forward elimination, then works upward to normalize pivots and eliminate entries above them. Both approaches produce the same reduced form in exact arithmetic.
When solving a system, pivot searches can be restricted to the coefficient columns. A remaining row with zero coefficients and a nonzero augmented entry then signals inconsistency. If the goal is the reduced row echelon form of the entire augmented matrix, the augmented column is processed as well.
Worked example
Consider
The augmented matrix is
Apply and :
The second pivot is already . Clear its column using and :
Finally, divide the third row by , then eliminate the entries above its pivot:
The solution is therefore
Reading the solution set
For a system with unknowns, row reduction distinguishes three possibilities.
No solution
A row of the form
represents the impossible equation .
Equivalently, the system is consistent precisely when
where rank is the number of pivots.
A unique solution
A consistent system has a unique solution if every variable column contains a pivot:
There are then no free variables.
Free variables
If a consistent system has rank , there are free variables. For example,
gives
Over the real or complex numbers, this describes infinitely many solutions. Over a finite field with elements, a consistent system with free variables instead has exactly solutions.
More generally, the solution set of a consistent system is an affine space:
where is any particular solution and is the null space of . Its dimension is , as expressed by the rank–nullity theorem.
Matrix inverses and subspaces
Computing an inverse
For a square matrix, augment with the identity matrix:
If is invertible, Gauss–Jordan elimination produces
The same row operations that transform into transform the identity matrix into the inverse matrix. If the left block cannot be reduced to , then is singular.
Several systems with the same coefficient matrix can similarly be processed together:
when is invertible.
Finding bases
Row reduction also provides information about fundamental subspaces:
- The nonzero rows of the reduced matrix form a basis for the original matrix’s row space.
- The pivot-column indices identify columns of the original matrix that form a basis for its column space.
- Setting each free variable in turn to , with the other free variables set to , produces a basis for the null space of a homogeneous system.
The distinction between original and reduced columns is important: row operations preserve relationships of linear dependence among columns, but generally change the column space itself.
Computational cost and numerical limitations
For a dense matrix, standard Gauss–Jordan elimination requires arithmetic operations, using big-O notation. Storing the matrix requires entries. These are arithmetic-operation estimates; exact rational calculations may also incur substantial costs as numerators and denominators grow.
For solving a single nonsingular system, Gaussian elimination followed by back substitution generally requires less arithmetic. In practical numerical linear algebra, LU decomposition is commonly used, particularly when the same coefficient matrix is paired with several right-hand sides. Explicitly forming an inverse is generally unnecessary for solving such systems.
With floating-point arithmetic, very small pivots can magnify rounding errors. Partial pivoting selects an entry of largest absolute value among the available entries in the current column and swaps its row into the pivot position. This avoids division by an unnecessarily small entry in that column, although it does not eliminate every possible source of numerical error.
Numerical stability must be distinguished from conditioning. An ill-conditioned system can have a solution highly sensitive to small changes in the input even when the computational method is stable; this sensitivity is described by its condition number.
Numerical rank determination presents a related difficulty. A computed entry close to zero may reflect rounding error rather than an exact algebraic dependency. Tolerances therefore depend on scale and precision. For difficult rank decisions, singular value decomposition or rank-revealing forms of QR factorization are generally more appropriate than simply counting apparently nonzero Gauss–Jordan pivots.
For a sparse matrix, elimination can create nonzero entries where zeros previously occurred, a phenomenon called fill-in. Clearing entries both above and below pivots can therefore be costly in storage as well as arithmetic.
Historical terminology
The name combines Carl Friedrich Gauss, whose name is associated with elimination methods, and Wilhelm Jordan, a German geodesist who described a related elimination procedure in the nineteenth century. The Jordan in this name is not the French mathematician Camille Jordan.
The underlying idea of eliminating unknowns is much older than either namesake. Modern terminology distinguishes Gaussian elimination, usually ending in echelon or triangular form, from Gauss–Jordan elimination, which continues to reduced row echelon form.