Chapter 9. Gaussian Elimination

Gaussian elimination is the standard method for solving systems of linear equations by row reduction. It transforms an augmented matrix into row echelon form by using elementary row operations. Once the matrix has echelon form, the solution is obtained by back substitution. The same procedure also exposes pivots, free variables, inconsistent rows, rank, and triangular structure. Gaussian elimination uses row operations to create zeros below each pivot, producing a row-equivalent system with the same solution set.

9.1 Purpose of Gaussian Elimination

Given a linear system

Gaussian elimination rewrites the system in a simpler equivalent form.

The goal is to transform the augmented matrix

into row echelon form:

where $U$ has zeros below its pivots.

The new system

has the same solutions as the original system, but it is easier to solve because the equations have a triangular structure.

9.2 Row Echelon Target

A matrix is in row echelon form when:

For example,

is in row echelon form.

It represents

The last equation gives $z$. The second equation then gives $y$. The first equation then gives $x$.

9.3 The Basic Elimination Step

Suppose the pivot is $a_{kk}\ne 0$. To eliminate an entry $a_{ik}$ below it, replace row $i$ by

The new entry in position $(i,k)$ is

This formula is the central arithmetic step of Gaussian elimination.

For example, in

the first pivot is $2$. The entry below it is $6$. Use

Then

The second equation is now simpler.

9.4 Forward Elimination

Forward elimination is the first phase of Gaussian elimination. It creates zeros below successive pivots.

The process is:

Forward elimination works from left to right and from top to bottom.

It does not usually eliminate entries above pivots. That extra work belongs to Gauss-Jordan elimination.

9.5 Back Substitution

Back substitution solves a system after forward elimination has produced echelon form.

For example,

represents

Start from the bottom:

so

Substitute into the second equation:

so

Substitute into the first equation:

Thus

so

and

Back substitution solves from the last pivot upward.

9.6 Worked Example with a Unique Solution

Consider the system

The augmented matrix is

Use the first row as the first pivot row.

Eliminate the $2$ below the first pivot:

Eliminate the $1$ below the first pivot:

This gives

Swap rows $2$ and $3$:

Then

Eliminate the entry below the second pivot:

Then

This is row echelon form.

Back substitution gives

so

Then

gives

so

Finally,

gives

so

The solution is

9.7 Pivots

A pivot is a leading nonzero entry used to eliminate entries below it.

In the echelon matrix

the pivot entries are

The pivot columns are columns $1$, $2$, and $3$. Since every variable column contains a pivot, the system has a unique solution.

Pivots measure how many independent constraints the system contains.

9.8 Row Swapping

A pivot entry must be nonzero. If the entry in the intended pivot position is zero, one must swap with a lower row containing a nonzero entry in the same column.

For example,

cannot use the first row, first column as a pivot. Swap the two rows:

Then

Now the pivot is $3$.

Row swapping preserves the solution set. It only changes the order of equations.

9.9 Free Variables

If a column has no pivot, the corresponding variable is free.

Consider

The pivot columns are $1$ and $3$. Therefore $x_1$ and $x_3$ are leading variables. The variable $x_2$ is free.

The equations are

Thus

Let

Then

so

The solution set is

The system has infinitely many solutions.

9.10 Inconsistent Systems

Gaussian elimination detects inconsistency by producing a row of the form

This row represents

which is impossible.

For example,

after

becomes

The second row says

Therefore the system is inconsistent.

9.11 Infinitely Many Solutions

A consistent system with at least one free variable has infinitely many solutions.

Consider

Use

Then

There is one pivot and three variables. Therefore there are two free variables.

The equation is

Let

Then

Thus

Equivalently,

9.12 Gaussian Elimination Algorithm

For an augmented matrix with $m$ rows and $n$ variable columns, the algorithm is:

row = 1

for col = 1 to n:
    find a row r >= row with a nonzero entry in column col

    if no such row exists:
        continue to next column

    swap row r with current row

    for each row i below current row:
        factor = A[i, col] / A[row, col]
        R_i = R_i - factor * R_row

    row = row + 1

After this process, the matrix is in row echelon form. Then one checks for contradictions and performs back substitution.

The exact pivot choice may vary. In exact arithmetic, any nonzero pivot is valid. In floating point arithmetic, pivot choice affects numerical stability.

9.13 Partial Pivoting

Partial pivoting chooses a pivot with large absolute value among the available entries in the pivot column.

Instead of using the first nonzero entry below the current row, one chooses the row $r$ for which

is largest among rows still available.

Then that row is swapped into the pivot position.

Partial pivoting is used in numerical computation because small pivots can magnify rounding error. Choosing a larger pivot generally improves stability when computations are performed with floating point arithmetic.

9.14 Exact Arithmetic and Floating Point Arithmetic

Gaussian elimination can be studied in exact arithmetic or floating point arithmetic.

In exact arithmetic, fractions and integers are represented without rounding. The main concern is algebraic correctness.

In floating point arithmetic, numbers are rounded after operations. The main concerns are accuracy, stability, and conditioning.

For example, if a pivot is very small, then the factor

may be very large. Large factors can amplify errors in the row entries. Pivoting reduces this risk.

Numerical linear algebra studies these issues systematically.

9.15 Operation Count

For a dense $n\times n$ system, Gaussian elimination requires on the order of

arithmetic operations.

More precisely, the leading cost of forward elimination is approximately

floating point operations for large $n$, with lower-order costs for back substitution.

The cubic cost is acceptable for moderate dense systems. For very large systems, especially sparse systems, specialized methods may be needed. Gaussian elimination has cubic arithmetic complexity for dense systems.

9.16 Gaussian Elimination and Rank

Gaussian elimination also computes rank.

The rank of a matrix is the number of pivot positions in an echelon form. Since row operations preserve rank, reducing a matrix to echelon form makes the rank visible.

For example,

Use

Then

Swap rows $2$ and $3$:

There are two nonzero rows in echelon form. Therefore

9.17 Gaussian Elimination and Determinants

For square matrices, Gaussian elimination can help compute determinants.

Row operations affect determinants as follows:

After reducing a matrix to triangular form, the determinant is the product of the diagonal entries, adjusted for row swaps and scalings.

This use of elimination will be developed fully in the chapter on determinants.

9.18 Gaussian Elimination and Inverses

Gaussian elimination can also compute matrix inverses.

For an $n\times n$ matrix $A$, form the augmented matrix

Then row reduce. If $A$ can be reduced to $I$, then the right-hand side becomes $A^{-1}$:

If $A$ cannot be reduced to $I$, then $A$ is not invertible.

This method is a direct application of row operations and will be studied in detail later.

9.19 Relation to Gauss-Jordan Elimination

Gaussian elimination stops after reaching row echelon form and then uses back substitution.

Gauss-Jordan elimination continues until reduced row echelon form is reached. It eliminates entries above pivots as well as below pivots.

Gaussian elimination usually does less row-reduction work when one only needs to solve a system. Gauss-Jordan elimination gives a more explicit final matrix form.

9.20 Common Mistakes

Several mistakes occur often in Gaussian elimination.

Gaussian elimination is mechanical, but small arithmetic errors can change the final classification.

9.21 Summary

Gaussian elimination solves a linear system by reducing its augmented matrix to row echelon form. It uses elementary row operations to create zeros below pivots. The resulting triangular system is solved by back substitution.

The main phases are:

The possible outcomes are:

Gaussian elimination is more than a method for solving equations. It is also a method for revealing the structure of a matrix: pivots, rank, dependence, invertibility, and triangular form.