Gaussian Elimination

Overview

Gaussian elimination is a systematic method for solving systems of linear equations by reducing the augmented matrix to row echelon form through elementary row operations.

Elementary Row Operations

Operation	Notation	Description
Swap	$R_i \leftrightarrow R_j$	Interchange rows $i$ and $j$
Scale	$cR_i \to R_i$	Multiply row $i$ by non-zero scalar $c$
Replace	$R_i + cR_j \to R_i$	Add $c$ times row $j$ to row $i$

Algorithm

Forward Elimination

1. Find the leftmost non-zero column (pivot column)
2. If necessary, swap rows to get a non-zero entry at the top
3. Use row replacement to create zeros below the pivot
4. Repeat for the remaining submatrix

Back Substitution

After reaching echelon form:

1. Solve for the last variable
2. Substitute back to find remaining variables

Example

Solve:

$x + 2y + 3z = 6$ $2x + 5y + 3z = 8$ $x + 8z = 9$

Step 1: Augmented Matrix

$\left[\begin{array}{ccc|c} 1 & 2 & 3 & 6 \\ 2 & 5 & 3 & 8 \\ 1 & 0 & 8 & 9 \end{array}\right]$

Step 2: Eliminate Below First Pivot

$R_2 - 2R_1 \to R_2$:

$\left[\begin{array}{ccc|c} 1 & 2 & 3 & 6 \\ 0 & 1 & -3 & -4 \\ 1 & 0 & 8 & 9 \end{array}\right]$

$R_3 - R_1 \to R_3$:

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

Step 3: Eliminate Below Second Pivot

$R_3 + 2R_2 \to R_3$:

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

Step 4: Back Substitution

From row 3: $-z = -5 \Rightarrow z = 5$

From row 2: $y - 3(5) = -4 \Rightarrow y = 11$

From row 1: $x + 2(11) + 3(5) = 6 \Rightarrow x = -31$

Solution: $x = -31$, $y = 11$, $z = 5$

Pivot Positions

A pivot is the leading non-zero entry in a row of echelon form.

Pivot Column

Column containing a pivot.

Pivot Strategy

For numerical stability, choose the largest absolute value in the column as pivot (partial pivoting).

Detecting Solution Types

After forward elimination:

Row Pattern	Meaning
$[0 \; 0 \; \cdots \; 0 \mid b]$ with $b \neq 0$	No solution
More variables than pivots	Infinitely many solutions
# pivots = # variables	Unique solution

Gaussian Elimination vs Gauss-Jordan

Method	Target Form	When to Stop
Gaussian	Row echelon form	Forward elimination only
Gauss-Jordan	Reduced row echelon form	Continue to get leading 1s and zeros above pivots

Computational Considerations

Operation Count

For an $n \times n$ system, Gaussian elimination requires:

• Approximately $n^3/3$ multiplications
• Approximately $n^3/3$ additions

Numerical Stability

• Use partial pivoting to avoid small pivots
• Scaled partial pivoting for better accuracy
• Full pivoting for maximum stability (rarely needed)

Special Cases

No Solution

$\left[\begin{array}{cc|c} 1 & 2 & 3 \\ 2 & 4 & 8 \end{array}\right] \to \left[\begin{array}{cc|c} 1 & 2 & 3 \\ 0 & 0 & 2 \end{array}\right]$

$0 = 2$ is a contradiction → no solution

Infinitely Many Solutions

$\left[\begin{array}{cc|c} 1 & 2 & 3 \\ 2 & 4 & 6 \end{array}\right] \to \left[\begin{array}{cc|c} 1 & 2 & 3 \\ 0 & 0 & 0 \end{array}\right]$

$x = 3 - 2t$, $y = t$ (free variable)