Skip to content

Chapter 10. Gauss-Jordan Elimination

Gauss-Jordan elimination is the row-reduction method that carries an augmented matrix all the way to reduced row echelon form. Gaussian elimination stops at row echelon form and then uses back substitution. Gauss-Jordan elimination continues the reduction until each pivot is 11 and each pivot column has zeros everywhere except at the pivot. In this final form, the solution can be read directly.

10.1 Purpose

Given a linear system

Ax=b, Ax=b,

Gauss-Jordan elimination transforms the augmented matrix

[A∣b] [A\mid b]

into reduced row echelon form.

The target has the form

[R∣c], [R\mid c],

where RR is reduced as far as row operations allow. The resulting system is equivalent to the original system, but the equations are arranged so that leading variables are already isolated.

For example,

[1002010−10015] \left[ \begin{array}{ccc|c} 1&0&0&2\\ 0&1&0&-1\\ 0&0&1&5 \end{array} \right]

directly represents

x1=2,x2=−1,x3=5. x_1=2,\qquad x_2=-1,\qquad x_3=5.

No back substitution is needed.

10.2 Reduced Row Echelon Form

A matrix is in reduced row echelon form when it satisfies the following conditions:

ConditionMeaning
Zero rows are at the bottomEmpty equations appear last
Each nonzero row has a leading 11The first nonzero entry of each nonzero row is normalized
Leading 11’s move rightwardEach pivot is to the right of the pivot above it
Each pivot column has zeros elsewhereA leading 11 is the only nonzero entry in its column

These conditions define the final target of Gauss-Jordan elimination.

For example,

[103001−200001] \begin{bmatrix} 1&0&3&0\\ 0&1&-2&0\\ 0&0&0&1 \end{bmatrix}

is in reduced row echelon form.

The matrix

[120013] \begin{bmatrix} 1&2&0\\ 0&1&3 \end{bmatrix}

is in row echelon form, but not reduced row echelon form, because the pivot in the second column has a nonzero entry above it.

10.3 Difference from Gaussian Elimination

Gaussian elimination and Gauss-Jordan elimination use the same elementary row operations. They differ in the stopping point.

MethodFinal formFinal step
Gaussian eliminationRow echelon formBack substitution
Gauss-Jordan eliminationReduced row echelon formRead solution directly

Gaussian elimination creates zeros below pivots. Gauss-Jordan elimination creates zeros below and above pivots.

For the echelon matrix

[12−1401350012], \left[ \begin{array}{ccc|c} 1&2&-1&4\\ 0&1&3&5\\ 0&0&1&2 \end{array} \right],

Gaussian elimination would solve by back substitution. Gauss-Jordan elimination continues by eliminating the entries above the pivot in column 33, then above the pivot in column 22.

10.4 The Basic Gauss-Jordan Step

Suppose a pivot has been normalized to 11 in row kk and column jj. To eliminate another entry aija_{ij} in the same column, replace row ii by

Ri←Ri−aijRk. R_i \leftarrow R_i-a_{ij}R_k.

The new entry in column jj is

aij−aij⋅1=0. a_{ij}-a_{ij}\cdot 1=0.

This same formula works for entries below the pivot and above the pivot. Gaussian elimination uses it only below pivots. Gauss-Jordan elimination uses it throughout the pivot column.

10.5 Algorithm

For an augmented matrix, Gauss-Jordan elimination proceeds as follows:

row = 1

for each column from left to right:
    find a nonzero entry in or below the current row

    if no such entry exists:
        continue to the next column

    swap that row into the current row position

    scale the current row so that the pivot equals 1

    eliminate every other entry in the pivot column

    move to the next row

When the process stops, the matrix is in reduced row echelon form.

The algorithm uses only elementary row operations: row swaps, nonzero row scalings, and row replacements. Since each operation is reversible, the final system is equivalent to the original system.

10.6 Example with a Unique Solution

Consider

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

The augmented matrix is

[11162−11312−12]. \left[ \begin{array}{ccc|c} 1&1&1&6\\ 2&-1&1&3\\ 1&2&-1&2 \end{array} \right].

Eliminate below the first pivot:

R2←R2−2R1,R3←R3−R1. R_2\leftarrow R_2-2R_1, \qquad R_3\leftarrow R_3-R_1.

Then

[11160−3−1−901−2−4]. \left[ \begin{array}{ccc|c} 1&1&1&6\\ 0&-3&-1&-9\\ 0&1&-2&-4 \end{array} \right].

Swap rows 22 and 33:

[111601−2−40−3−1−9]. \left[ \begin{array}{ccc|c} 1&1&1&6\\ 0&1&-2&-4\\ 0&-3&-1&-9 \end{array} \right].

Eliminate the entry below the second pivot:

R3←R3+3R2. R_3\leftarrow R_3+3R_2.

This gives

[111601−2−400−7−21]. \left[ \begin{array}{ccc|c} 1&1&1&6\\ 0&1&-2&-4\\ 0&0&-7&-21 \end{array} \right].

Scale the third row:

R3←−17R3. R_3\leftarrow -\frac17R_3.

Then

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

Eliminate entries above the third pivot:

R2←R2+2R3,R1←R1−R3. R_2\leftarrow R_2+2R_3, \qquad R_1\leftarrow R_1-R_3.

Then

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

Eliminate the entry above the second pivot:

R1←R1−R2. R_1\leftarrow R_1-R_2.

Thus

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

The solution is

[123]. \begin{bmatrix} 1\\ 2\\ 3 \end{bmatrix}.

10.7 Reading a Unique Solution

When the left side of an augmented matrix reduces to the identity matrix, the solution is the right-hand side.

If

[A∣b]⟶[I∣c], [A\mid b]\longrightarrow [I\mid c],

then

x=c. x=c.

For example,

[1004010−20017] \left[ \begin{array}{ccc|c} 1&0&0&4\\ 0&1&0&-2\\ 0&0&1&7 \end{array} \right]

represents

x1=4,x2=−2,x3=7. x_1=4,\qquad x_2=-2,\qquad x_3=7.

The solution vector is

x=[4−27]. x= \begin{bmatrix} 4\\ -2\\ 7 \end{bmatrix}.

10.8 Free Variables in Reduced Form

Reduced row echelon form makes free variables explicit.

Consider

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

The pivot columns are columns 11 and 22. The third variable is free.

The equations are

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

Let

x3=t. x_3=t.

Then

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

Thus

x=[3−2t4+tt]=[340]+t[−211]. x= \begin{bmatrix} 3-2t\\ 4+t\\ t \end{bmatrix} = \begin{bmatrix} 3\\ 4\\ 0 \end{bmatrix} + t \begin{bmatrix} -2\\ 1\\ 1 \end{bmatrix}.

The reduced form separates the particular solution from the homogeneous direction.

10.9 Inconsistent Systems in Reduced Form

An inconsistent system produces a row of the form

[00⋯0b],b≠0. \left[ \begin{array}{cccc|c} 0&0&\cdots&0&b \end{array} \right], \qquad b\ne 0.

This row represents

0=b. 0=b.

For example,

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

contains the equation

0=4. 0=4.

Therefore the system has no solution.

10.10 Pivot Columns and Leading Variables

Each pivot column corresponds to a leading variable. Each nonpivot column corresponds to a free variable.

In

[1030−1201−204500016−3], \left[ \begin{array}{ccccc|c} 1&0&3&0&-1&2\\ 0&1&-2&0&4&5\\ 0&0&0&1&6&-3 \end{array} \right],

the pivot columns are 11, 22, and 44. Thus

x1,x2,x4 x_1,\quad x_2,\quad x_4

are leading variables.

The nonpivot columns are 33 and 55. Thus

x3,x5 x_3,\quad x_5

are free variables.

Let

x3=s,x5=t. x_3=s,\qquad x_5=t.

Then the equations give

x1=2−3s+t, x_1=2-3s+t, x2=5+2s−4t, x_2=5+2s-4t, x4=−3−6t. x_4=-3-6t.

So the solution set is

x=[2−3s+t5+2s−4ts−3−6tt]. x= \begin{bmatrix} 2-3s+t\\ 5+2s-4t\\ s\\ -3-6t\\ t \end{bmatrix}.

10.11 Homogeneous Systems

For a homogeneous system

Ax=0, Ax=0,

the augmented matrix has a zero right-hand side:

[A∣0]. [A\mid 0].

Row operations preserve the zero right-hand side. Therefore the reduced row echelon form also has zero in the augmented column:

[R∣0]. [R\mid 0].

The system always has the trivial solution

x=0. x=0.

If every variable column has a pivot, the trivial solution is the only solution. If at least one variable is free, the system has infinitely many solutions.

For example,

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

gives

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

Let

x3=t. x_3=t.

Then

x1=2t,x2=−3t. x_1=2t, \qquad x_2=-3t.

Thus

x=t[2−31]. x=t \begin{bmatrix} 2\\ -3\\ 1 \end{bmatrix}.

10.12 Computing an Inverse

Gauss-Jordan elimination gives a direct method for computing the inverse of a square matrix.

For an n×nn\times n matrix AA, form

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

Then row reduce.

If

[A∣In]⟶[In∣B], [A\mid I_n]\longrightarrow [I_n\mid B],

then

B=A−1. B=A^{-1}.

If the left side cannot be reduced to InI_n, then AA is not invertible.

This works because the row operations applied to AA are also applied to InI_n. The accumulated row operations form the inverse matrix.

10.13 Example: Inverse of a 2×22\times 2 Matrix

Let

A=[1235]. A= \begin{bmatrix} 1&2\\ 3&5 \end{bmatrix}.

Form

[A∣I]=[12103501]. [A\mid I] = \left[ \begin{array}{cc|cc} 1&2&1&0\\ 3&5&0&1 \end{array} \right].

Eliminate below the first pivot:

R2←R2−3R1. R_2\leftarrow R_2-3R_1.

Then

[12100−1−31]. \left[ \begin{array}{cc|cc} 1&2&1&0\\ 0&-1&-3&1 \end{array} \right].

Scale row 22:

R2←−R2. R_2\leftarrow -R_2.

Then

[1210013−1]. \left[ \begin{array}{cc|cc} 1&2&1&0\\ 0&1&3&-1 \end{array} \right].

Eliminate above the second pivot:

R1←R1−2R2. R_1\leftarrow R_1-2R_2.

Thus

[10−52013−1]. \left[ \begin{array}{cc|cc} 1&0&-5&2\\ 0&1&3&-1 \end{array} \right].

Therefore

A−1=[−523−1]. A^{-1} = \begin{bmatrix} -5&2\\ 3&-1 \end{bmatrix}.

One may check:

[1235][−523−1]=[1001]. \begin{bmatrix} 1&2\\ 3&5 \end{bmatrix} \begin{bmatrix} -5&2\\ 3&-1 \end{bmatrix} = \begin{bmatrix} 1&0\\ 0&1 \end{bmatrix}.

10.14 Rank from Reduced Row Echelon Form

The rank of a matrix is the number of pivot positions in its row echelon form. Since reduced row echelon form makes pivots explicit, it also makes rank explicit.

For example,

R=[103001−2000010000] R= \begin{bmatrix} 1&0&3&0\\ 0&1&-2&0\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix}

has three pivots. Therefore

rank⁡(R)=3. \operatorname{rank}(R)=3.

Any matrix row equivalent to RR has rank 33.

10.15 Uniqueness of Reduced Row Echelon Form

Every matrix is row equivalent to exactly one reduced row echelon matrix.

This is a useful distinction. A matrix may have many possible echelon forms because pivot choices and row swaps may vary. But its reduced row echelon form is unique.

Thus the notation

rref⁡(A) \operatorname{rref}(A)

is meaningful: it refers to the unique reduced row echelon form of AA.

10.16 Column Information and a Caution

Row reduction preserves row relations and solution sets of augmented systems. It does not preserve the actual columns of the original matrix.

For example, pivot columns in the reduced form identify which columns of the original matrix are pivot columns. But the columns in the reduced matrix are usually not the same as the original columns.

This distinction matters when finding a basis for the column space. One uses the pivot column positions found from row reduction, then returns to the corresponding original columns of AA.

10.17 Computational Cost

For a dense n×nn\times n system, Gauss-Jordan elimination has cubic arithmetic cost, like Gaussian elimination. It usually performs more arithmetic than Gaussian elimination because it eliminates both below and above pivots.

For solving a single system, Gaussian elimination followed by back substitution is often more efficient. For finding reduced row echelon form or computing inverses by [A∣I][A\mid I], Gauss-Jordan elimination is the natural method.

10.18 Common Mistakes

MistakeCorrection
Stopping at echelon formGauss-Jordan continues to reduced row echelon form
Forgetting to scale pivots to 11Every leading entry in RREF must be 11
Eliminating only below pivotsRREF requires zeros above pivots too
Applying row operations only to AA in [A∣b][A\mid b]Apply each operation to the whole augmented matrix
Treating free variables as zero without saying soFree variables must be parameterized
Using reduced columns as original column-space basis vectorsUse pivot positions to select columns from the original matrix

10.19 Summary

Gauss-Jordan elimination is the row-reduction process that produces reduced row echelon form. It uses elementary row operations to create leading 11’s and zeros everywhere else in each pivot column.

The method gives direct access to:

OutputHow it appears in RREF
Unique solutionLeft side becomes identity
No solutionA row 0=b0=b, b≠0b\ne 0
Infinitely many solutionsAt least one free variable
RankNumber of pivots
InvertibilitySquare matrix reduces to identity
Inverse[A∣I]→[I∣A−1][A\mid I]\to[I\mid A^{-1}]

Gaussian elimination is usually preferred for solving one system efficiently. Gauss-Jordan elimination is preferred when the reduced form itself is needed.