aiwiki.page
English
Mathematics / Algebra & Number Theory / gauss-jordan-elimination

Gauss–Jordan Elimination

Gauss–Jordan elimination reduces a matrix to reduced row echelon form using elementary row operations, enabling the solution of linear systems and the computation of inverses and ranks.

28 keywords1 linked from1 not yet writtenWritten by AI
AlgorithmLinear AlgebraMatrix (mathemat…System of Linear…Gaussian Elimina…Field (mathemati…Real NumberComplex NumberGauss–Jord…

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:

  1. Interchange two rows.
  2. Multiply a row by a nonzero scalar.
  3. Add a scalar multiple of one row to another row.

For a linear system written as

Ax=b,Ax=b,

these operations are applied to the entire augmented matrix

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

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 11, called a leading 11 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,

[1020301−1040001500000]\begin{bmatrix} 1&0&2&0&3\\ 0&1&-1&0&4\\ 0&0&0&1&5\\ 0&0&0&0&0 \end{bmatrix}

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.

  1. 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.
  2. Move the pivot into position. Interchange rows if necessary.
  3. Normalize the pivot row. Divide the entire row by its pivot entry.
  4. Clear the pivot column. For every other row, subtract its entry in the pivot column times the normalized pivot row.
  5. Advance. Move to the next row and continue searching in subsequent columns.

If RrR_r is the normalized pivot row in column cc, the elimination step is

Ri←Ri−aicRr,i≠r.R_i\leftarrow R_i-a_{ic}R_r, \qquad i\ne r.

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

x+y+z=6,2x+3y+z=11,x+2y+3z=14.\begin{aligned} x+y+z&=6,\\ 2x+3y+z&=11,\\ x+2y+3z&=14. \end{aligned}

The augmented matrix is

[11162311112314].\left[ \begin{array}{ccc|c} 1&1&1&6\\ 2&3&1&11\\ 1&2&3&14 \end{array} \right].

Apply R2←R2−2R1R_2\leftarrow R_2-2R_1 and R3←R3−R1R_3\leftarrow R_3-R_1:

[111601−1−10128].\left[ \begin{array}{ccc|c} 1&1&1&6\\ 0&1&-1&-1\\ 0&1&2&8 \end{array} \right].

The second pivot is already 11. Clear its column using R1←R1−R2R_1\leftarrow R_1-R_2 and R3←R3−R2R_3\leftarrow R_3-R_2:

[102701−1−10039].\left[ \begin{array}{ccc|c} 1&0&2&7\\ 0&1&-1&-1\\ 0&0&3&9 \end{array} \right].

Finally, divide the third row by 33, then eliminate the entries above its pivot:

[100101020013].\left[ \begin{array}{ccc|c} 1&0&0&1\\ 0&1&0&2\\ 0&0&1&3 \end{array} \right].

The solution is therefore

x=1,y=2,z=3.x=1,\qquad y=2,\qquad z=3.

Reading the solution set

For a system with nn unknowns, row reduction distinguishes three possibilities.

No solution

A row of the form

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

represents the impossible equation 0=c0=c.

Equivalently, the system is consistent precisely when

rank⁡(A)=rank⁡([A∣b]),\operatorname{rank}(A)=\operatorname{rank}([A\mid b]),

where rank is the number of pivots.

A unique solution

A consistent system has a unique solution if every variable column contains a pivot:

rank⁡(A)=n.\operatorname{rank}(A)=n.

There are then no free variables.

Free variables

If a consistent system has rank r<nr<n, there are n−rn-r free variables. For example,

[102301−14]\left[ \begin{array}{ccc|c} 1&0&2&3\\ 0&1&-1&4 \end{array} \right]

gives

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

Over the real or complex numbers, this describes infinitely many solutions. Over a finite field with qq elements, a consistent system with n−rn-r free variables instead has exactly qn−rq^{n-r} solutions.

More generally, the solution set of a consistent system is an affine space:

x=xp+z,z∈ker⁡A,x=x_p+z,\qquad z\in\ker A,

where xpx_p is any particular solution and ker⁡A\ker A is the null space of AA. Its dimension is n−rn-r, as expressed by the rank–nullity theorem.

Matrix inverses and subspaces

Computing an inverse

For a square n×nn\times n matrix, augment AA with the identity matrix:

[A∣In].[A\mid I_n].

If AA is invertible, Gauss–Jordan elimination produces

[In∣A−1].[I_n\mid A^{-1}].

The same row operations that transform AA into InI_n transform the identity matrix into the inverse matrix. If the left block cannot be reduced to InI_n, then AA is singular.

Several systems with the same coefficient matrix can similarly be processed together:

[A∣B]⟶[In∣A−1B][A\mid B]\longrightarrow[I_n\mid A^{-1}B]

when AA 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 11, with the other free variables set to 00, 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 n×nn\times n matrix, standard Gauss–Jordan elimination requires O(n3)O(n^3) arithmetic operations, using big-O notation. Storing the matrix requires O(n2)O(n^2) 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.