Gaussian Elimination

Order: 13
Subtopic: Systems
Topic: Linear Algebra

Gaussian elimination systematically transforms a linear system into triangular form, making solutions easy to find through back-substitution. It's the fundamental algorithm for solving linear systems, finding inverses, and computing rank—the computational backbone of linear algebra.

Introduction

Solving a system of linear equations by hand means eliminating variables one at a time until the answer becomes obvious. Gaussian elimination is the systematic version: use row operations to create zeros below each pivot, resulting in an upper triangular system.

Once triangular, solve from the bottom up—each equation has only one unknown.

Row Operations

Three operations that don't change the solution set:

1. Swap two rows: (R_i)↔(R_j)

2. Multiply a row by a nonzero constant: (R_i)→c*(R_i)

3. Add a multiple of one row to another: (R_i)→(R_i)+c*(R_j)

These are the tools for elimination. Operation 3 creates zeros.

The Algorithm

Given augmented matrix [[A,b]]:

1. Find the leftmost column with a nonzero entry (pivot column)

2. If needed, swap rows to get nonzero pivot at top of this column

3. Use row operations to create zeros below the pivot

4. Move to the next row and repeat for remaining columns

5. Result: row echelon form (REF)

For reduced row echelon form (RREF): also create zeros above pivots and scale pivots to 1.

Worked Example

Solve the system:

{[x+2*y+z=9],[2*x−y+3*z=8],[3*x+y−z=3])

Form augmented matrix:

[[1,2,1,9],[2,−1,3,8],[3,1,−1,3]]

(R_2)→(R_2)−2*(R_1), (R_3)→(R_3)−3*(R_1):

[[1,2,1,9],[0,−5,1,−10],[0,−5,−4,−24]]

(R_3)→(R_3)-(R_2):

[[1,2,1,9],[0,−5,1,−10],[0,0,−5,−14]]

Back-Substitution

From row 3: −5*z=−14, so z=14/5.

From row 2: −5*y+z=−10, so y=(10+14/5)/5=64/25.

From row 1: x+2*y+z=9, so x=9−2*(64/25)−14/5=31/25.

Solution: x=31/25,y=64/25,z=14/5.

Row Echelon Form (REF)

A matrix is in REF if:

• All zero rows are at the bottom

• Each leading entry (pivot) is to the right of the pivot above it

• All entries below a pivot are zero

Reduced Row Echelon Form (RREF)

RREF adds:

• Each pivot is 1

• Each pivot is the only nonzero entry in its column

RREF is unique for any matrix—it's the canonical form.

Pivots and Rank

The number of pivots equals the rank of the matrix.

Columns without pivots correspond to free variables (infinitely many solutions).

If a pivot appears in the augmented column, the system is inconsistent (no solution).

Computational Cost

For an n×n system: O(n3) operations.

This is efficient — doubling the size increases the work by 8×, not exponentially.

Pivoting Strategies

Partial pivoting: Before eliminating, swap to put the largest magnitude entry in the pivot position. This improves numerical stability.

Without pivoting, small pivots can amplify rounding errors catastrophically.

Applications

Beyond solving systems: computing matrix inverse, finding rank, determining linear independence, and computing determinants (product of pivots, adjusted for swaps).

Summary

Gaussian elimination uses row operations to transform a system into triangular form. Solve by back-substitution. REF has zeros below pivots; RREF also has zeros above and pivots equal to 1. The number of pivots is the rank. Pivoting improves numerical stability. The computational cost is O(n3).