Systems of linear equations · Lecture 12

Gaussian and Gauss–Jordan Elimination

The school method of eliminating unknowns, made systematic: forward elimination and back substitution, Gauss–Jordan and the inverse, the operation count, and partial pivoting to keep rounding errors under control.

Md Mahbub E Noor · Assistant Professor
CSE-3107 Numerical Methods · B.Sc. 3rd Year 1st Semester
Department of CSE, University of Barishal

Why this lecture

The problem: temperatures inside a metal plate

The edges of a square plate are held at fixed temperatures. What is the temperature at the four marked interior points?

In steady heat flow, each interior temperature is the average of its four neighbours
Point 1: $T_1 = \tfrac14(100 + 0 + T_2 + T_3)$ , so $4T_1 - T_2 - T_3 = 100$
Four points give four linear equations; Cramer could manage this one
But engineers use a 100 × 100 grid: 10 000 unknowns. We need a method whose work grows like $n^3$ , not $n!$

Edges: 100° (top), 50° (right), 0° (bottom and left)

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

2 / 23

Today's goals

Solve $A\mathbf{x} = \mathbf{b}$ by Gaussian elimination and back substitution
Use Gauss–Jordan elimination, and find $A^{-1}$ from $[A \mid I]$
Count the operations: about $\tfrac23 n^3$ , compared with $n!$ for Cramer
Explain why a small pivot ruins the answer, and fix it with partial pivoting
Choose between elimination methods for a given problem

Last time

Cramer and the inverse: exact formulas, but the cost grows like $n!$ .

Today

Eliminate unknowns column by column; count the cost; add pivoting for safety.

Systems of linear equations · you are here

L11 · Linear Systems, Cramer's Rule and the Inverse→L12 · Gaussian and Gauss–Jordan Elimination→L13 · LU, Cholesky and Tridiagonal Systems→L14 · Iterative Methods

Builds on: L5, L11

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

3 / 23

Start here

The idea in one picture

Three equations with all the unknowns mixed together.Subtract multiples of row 1 from the rows below …… so that column 1 gets zeros below the top entry.Do the same with column 2. Now the matrix is a triangle.The last row has only one unknown: solve it directly.Put that value into the row above: one unknown again.Work upwards to the top. This is back substitution.

In plain words

Use one equation to remove an unknown from the equations below it
Repeat until the last equation has a single unknown
Then solve from the bottom upwards

New words today

pivot: the entry used to eliminate the entries below it
multiplier: how many times the pivot row is subtracted
upper triangular: zeros everywhere below the diagonal
back substitution: solving from the last equation up

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

4 / 23

The idea: reduce to a triangle, then solve upwards

Elementary row operations do not change the solution

R_i \leftrightarrow R_j, \qquad R_i \leftarrow c\,R_i \;(c \ne 0), \qquad R_i \leftarrow R_i - m\,R_k

Forward elimination, column k: multiplier and row update

m_{ik} = \frac{a_{ik}}{a_{kk}}, \qquad R_i \leftarrow R_i - m_{ik}R_k \quad (i = k+1, \dots, n)

Back substitution on the triangular system

x_n = \frac{b_n}{a_{nn}}, \qquad x_i = \frac{1}{a_{ii}}\Big(b_i - \sum_{j=i+1}^{n} a_{ij}x_j\Big)

$a_{kk}$ is the pivot: it must not be zero
After column $k$ , every entry below the pivot is 0
After $n - 1$ columns the matrix is upper triangular, $U$
The last equation has one unknown, the one above it two, and so on

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

5 / 23

The method, step by step

Gaussian elimination, step by step

Write the augmented matrix $[A \mid \mathbf{b}]$
For column $k = 1, \dots, n-1$ : check the pivot $a_{kk} \ne 0$
For each row $i$ below it: $m_{ik} = a_{ik}/a_{kk}$ , then $R_i \leftarrow R_i - m_{ik}R_k$
Now the system is upper triangular: $x_n = b_n/a_{nn}$
Back substitution: $x_i = (b_i - \sum_{j>i} a_{ij}x_j)/a_{ii}$ for $i = n-1, \dots, 1$ ; check by substituting

Pseudocode

input A (n×n), b
for k = 1 … n−1:              # forward
    if a[k][k] = 0: stop (pivot)
    for i = k+1 … n:
        m ← a[i][k] / a[k][k]
        for j = k … n:
            a[i][j] ← a[i][j] − m·a[k][j]
        b[i] ← b[i] − m·b[k]
for i = n … 1:                # backward
    s ← b[i] − Σ_{j>i} a[i][j]·x[j]
    x[i] ← s / a[i][i]

Three nested loops in the forward part: that is where the $n^3$ comes from.

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

6 / 23

Explore: elimination, one row operation at a time

Each Next step is one row operation; the orange box is the pivot
Shaded row: the one that just changed
Faded zeros: entries already eliminated
Try the plate and the zero pivot presets

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

7 / 23

Problem 1: three equations by Gaussian elimination

Solve

2x + y - z = 8

,

\;-3x - y + 2z = -11

,

\;-2x + y + 2z = -3

.

1

Column 1:

m_{21} = -3/2

,

m_{31} = -2/2 = -1

.

\;R_2 \leftarrow R_2 + 1.5R_1

,

R_3 \leftarrow R_3 + R_1

:

\;\left(\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 0.5 & 0.5 & 1 \\ 0 & 2 & 1 & 5\end{array}\right)

2

Column 2:

m_{32} = 2/0.5 = 4

.

\;R_3 \leftarrow R_3 - 4R_2

:

\;\left(\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 0.5 & 0.5 & 1 \\ 0 & 0 & -1 & 1\end{array}\right)

3

Back substitution:

z = 1/(-1) = -1

;

\;y = (1 - 0.5(-1))/0.5 = 3

;

\;x = (8 - 3 - (-1)(-1))/2 = 2

x = 2

,

y = 3

,

z = -1

. Check eq. 2:

-6 - 3 - 2 = -11

✓

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

8 / 23

The method, step by step

Gauss–Jordan elimination, step by step

Eliminate above and below each pivot and scale it to 1. The left part becomes $I$ and the right part is the answer.

Write $[A \mid \mathbf{b}]$ (or $[A \mid I]$ to get the inverse)
For column $k = 1, \dots, n$ : divide row $k$ by the pivot so that $a_{kk} = 1$
Clear column $k$ in every other row: $R_i \leftarrow R_i - a_{ik}R_k$ , for all $i \ne k$
After column $n$ : $[I \mid \mathbf{x}]$ , so read off $\mathbf{x}$ (no back substitution)
With $[A \mid I]$ you end with $[I \mid A^{-1}]$

Pseudocode

input M = [A | B]   # B = b or I
for k = 1 … n:
    if m[k][k] = 0: stop (pivot)
    R_k ← R_k / m[k][k]
    for i = 1 … n, i ≠ k:
        R_i ← R_i − m[i][k]·R_k
return right part of M

About $n^3$ operations: 50% more than Gaussian elimination, because it also clears the entries above the pivots.

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

9 / 23

Problem 2: the inverse by Gauss–Jordan

Find

A^{-1}

for

A = \begin{pmatrix} 1 & 2 & 3 \\ 0 & 1 & 4 \\ 5 & 6 & 0\end{pmatrix}

by reducing

[A \mid I]

.

1

Column 1 (pivot 1):

R_3 \leftarrow R_3 - 5R_1

gives row 3

= (0, -4, -15 \mid -5, 0, 1)

2

Column 2 (pivot 1):

R_1 \leftarrow R_1 - 2R_2

,

R_3 \leftarrow R_3 + 4R_2

: rows

(1, 0, -5 \mid 1, -2, 0)

and

(0, 0, 1 \mid -5, 4, 1)

3

Column 3 (pivot 1):

R_1 \leftarrow R_1 + 5R_3

,

R_2 \leftarrow R_2 - 4R_3

A^{-1} = \begin{pmatrix} -24 & 18 & 5 \\ 20 & -15 & -4 \\ -5 & 4 & 1\end{pmatrix}

; check

AA^{-1} = I

.

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

10 / 23

How much work? The operation count

Column k: (n − k) rows, each 1 division and n − k + 1 multiply–subtract pairs

\sum_{k=1}^{n-1}(n-k)\big(2(n-k) + 3\big) + \underbrace{n^2}_{\text{back subst.}} = \frac{2n^3}{3} + \frac{3n^2}{2} - \frac{7n}{6}

For large n only the first term matters

\begin{aligned} \text{Gauss} &\approx \tfrac23 n^3 \\ \text{Gauss–Jordan} &\approx n^3 \\ \text{Cramer} &\approx e\,(n+1)! \end{aligned}

$n$	Gauss: operations	time	matrix memory
3	28	28 ns	72 B
100	$6.8\times10^5$	0.7 ms	80 KB
1000	$6.7\times10^8$	0.67 s	8 MB
10 000	$6.7\times10^{11}$	11 min	800 MB

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

11 / 23

Classical vs numerical

Same plate, two approaches

Formula

Classical (Cramer's rule)

Five 4×4 determinants
319 operations
$T = (43.75, 56.25, 18.75, 31.25)$

vs

Algorithm

Numerical (Gaussian elimination)

Six row operations, then back substitution
62 operations
$T = (43.75, 56.25, 18.75, 31.25)$

When the classical approach cannot work

A 10 × 10 grid of points: 100 unknowns

Cramer's rule: about $2.6\times10^{160}$ operations, far beyond any computer that could ever be built. Gaussian elimination: 681 550 operations, under a millisecond.

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

12 / 23

Limitation shown failing

The weakness: a tiny pivot destroys the answer

$0.0001x + y = 1$ , $\;x + y = 2$ : exact $x = 1.0001$ , $y = 0.9999$
Pivot 0.0001, so $m_{21} = 10\,000$ : row 2 becomes $1 - 10\,000 = -9999 \to -10\,000$ in 3 digits
Back substitution: $y = 1$ , then $x = (1 - 1)/0.0001 = 0$ . Completely wrong
In double precision the same happens with a pivot of $10^{-20}$ : $x = 0$ , $y = 1$

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

13 / 23

The method, step by step

The fix: partial pivoting

Before eliminating column $k$ , bring the largest $|a_{ik}|$ ( $i \ge k$ ) into the pivot position.

For column $k$ : find the row $p \ge k$ with the largest $|a_{pk}|$
Swap $R_k \leftrightarrow R_p$ (whole rows, including $\mathbf{b}$ )
Eliminate as before; now every $|m_{ik}| \le 1$
If the largest $|a_{pk}|$ is 0, the matrix is singular: stop
Back substitution as before

Added to the pseudocode

for k = 1 … n−1:
    p ← argmax_{i ≥ k} |a[i][k]|
    if a[p][k] = 0: stop (singular)
    swap rows k and p of [A | b]
    for i = k+1 … n:
        m ← a[i][k] / a[k][k]   # |m| ≤ 1
        R_i ← R_i − m·R_k

Multipliers at most 1 in size keep rounding errors from growing. It costs only comparisons, no extra arithmetic.

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

14 / 23

Problem 3: the same system with 3-digit arithmetic

Solve

0.0001x + y = 1

,

\;x + y = 2

keeping 3 significant digits after every operation, without and with pivoting.

	Without pivoting	With partial pivoting
pivot row	$0.0001x + y = 1$	swap: $x + y = 2$ first
multiplier	$m = 1/0.0001 = 10\,000$	$m = 0.0001/1 = 0.0001$
new row 2	$-10\,000\,y = -10\,000$	$1.00\,y = 1.00$
$y$	1.00	1.00
$x$	$(1 - 1)/0.0001 = 0$	$2 - 1 = 1.00$
error in $x$	100%	0.01%

With pivoting, $1 - 0.0001 = 0.9999 \to 1.00$ and $1 - 0.0002 \to 1.00$ : the rounding only touches digits that do not matter.

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

15 / 23

Gaussian elimination with partial pivoting

Works for any $n$ : the matrix is a list of rows (C: a 2-D array)
Pivot search, row swap, elimination, back substitution
Prints the triangular system and the solution
Try the plate (lab task) and a singular matrix

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

16 / 23

Practice

Practice problem

Problem 4"Solve by Gaussian elimination with partial pivoting:

2x + 3y - z = 5

,

\;4x + 4y - 3z = 3

,

\;-2x + 3y - z = 1

."

How to write a complete answer

Column 1: largest $|a_{i1}|$ is 4 (row 2): swap $R_1 \leftrightarrow R_2$ . Then $m_{21} = 0.5$ , $m_{31} = -0.5$
Column 2: entries 1 and 5 below the pivot: swap again so 5 is the pivot; $m_{32} = 0.2$
Triangular system $4x + 4y - 3z = 3$ , $5y - 2.5z = 2.5$ , $z = 3$
Back substitution: $z = 3$ , $y = 2$ , $x = 1$ ; check in an original equation and state every swap you made

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

17 / 23

When to use it

Gaussian elimination: method profile

Best case

Dense systems up to a few thousand unknowns: $\tfrac23 n^3$ , under a second for $n = 1000$
With partial pivoting: reliable for almost every nonsingular matrix met in practice
Exact (up to rounding) in a fixed number of steps; no starting guess, no convergence question

Worst case

A zero or tiny pivot without pivoting: failure or garbage
Ill-conditioned $A$ : pivoting cannot recover digits the problem itself loses
$n = 10^6$ : $6.7\times10^{17}$ operations and 8 TB of memory

Best suited for

One system with a dense matrix
Inside other algorithms: each Newton step for a system (Lecture 10), least squares (Lecture 23)
Gauss–Jordan: inverses, RREF, rank

Avoid when

The same $A$ with many right-hand sides (factor once: LU, Lecture 13)
Banded or tridiagonal matrices with the full algorithm (Thomas, Lecture 13)
Huge sparse systems (iterative methods, Lecture 14)

Rule of thumb: for one dense system, Gaussian elimination with partial pivoting is the default; switch only when the matrix has special structure.

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

18 / 23

Comparative analysis: elimination methods

Method	Operations	$n = 1000$	Stable?	Gives $A^{-1}$ ?	Typical use
Cramer (cofactors)	$e\,(n+1)!$	impossible	no	via adjugate	2×2, 3×3 by hand
Gauss, no pivoting	$\tfrac23 n^3$	0.67 s	no (tiny pivots)	no	diagonally dominant or SPD matrices
Gauss, partial pivoting	$\tfrac23 n^3$ + comparisons	0.67 s	yes (in practice)	no	the default solver
Gauss–Jordan	$n^3$	1.0 s	yes, with pivoting	yes	inverses, RREF
Inverse, then $A^{-1}\mathbf{b}$	$2n^3$	2.0 s	less accurate	yes	avoid for solving

Without pivoting, elimination is still safe for diagonally dominant and for symmetric positive definite matrices: the pivots can never become small. Lecture 13 uses this.

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

19 / 23

Roadmap

Limitations, and where we fix them

Elimination is the workhorse, but it treats every matrix as dense and every right-hand side as new.

What it does well (keep this)

$\tfrac23 n^3$ operations, a fixed number of steps
Partial pivoting: multipliers $|m| \le 1$
Gauss–Jordan for inverses and RREF
Works for any nonsingular matrix

LimitationHow it is overcomeWhere

Same

A

, many right-hand sides: repeats all the work

→

Keep the multipliers:

A = LU

, then

2n^2

per new

\mathbf{b}

Lecture 13 →

Symmetric positive definite

A

: half the work is wasted

→

Cholesky,

A = LL^T

:

\tfrac13 n^3

Lecture 13 →

Tridiagonal

A

: almost all entries are 0

→

Thomas algorithm:

8n

operations

Lecture 13 →

10^6

unknowns: memory and

n^3

time

→

Iterative methods: Jacobi, Gauss–Seidel, SOR

Lecture 14 →

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

20 / 23

Applications

Where this method runs in the real world

Click a card to see elimination at work inside a real computation.

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

21 / 23

Checkpoint

Checkpoint · think, then discuss with your neighbourEliminate

x

from

3x + 6y = 9

,

\;2x + 5y = 8

. What is the new second row?

A

(0, \; 1 \mid 2)

B

(0, \; 9 \mid 14)

C

(0, \; 1 \mid -1)

D

(0, \; -1 \mid 2)

A.

m_{21} = 2/3

:

5 - \tfrac23(6) = 1

and

8 - \tfrac23(9) = 2

. So

y = 2

and

x = (9 - 12)/3 = -1

.

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

22 / 23

Summary

Key points

Forward elimination with multipliers $m_{ik} = a_{ik}/a_{kk}$ , then back substitution
Gauss–Jordan clears above and below: $[I \mid \mathbf{x}]$ , or $[I \mid A^{-1}]$ from $[A \mid I]$
Cost about $\tfrac23 n^3$ (Gauss–Jordan $n^3$ ), compared with $e(n+1)!$ for Cramer
Partial pivoting (largest pivot, $|m| \le 1$ ) prevents small pivots from destroying the answer

Opening problem: solved

Elimination of the plate system gives $T_1 = 43.75°$ , $T_2 = 56.25°$ , $T_3 = 18.75°$ , $T_4 = 31.25°$ in 62 operations. A 100 × 100 grid (10 000 unknowns) takes about 11 minutes this way: Lecture 14 does better.

Homework

Solve $x + 2y + 3z = 14$ , $\;2x + 5y + 2z = 18$ , $\;3x + y + 5z = 20$ by Gaussian elimination.
Find the inverse of $\begin{pmatrix} 2 & 1 & 1 \\ 1 & 3 & 2 \\ 1 & 0 & 0\end{pmatrix}$ by Gauss–Jordan.
Solve $0.00001x + y = 1$ , $x + y = 2$ with 4-digit arithmetic, without and with partial pivoting. Check with the lab tool.
How long does Gaussian elimination take for $n = 5000$ at $10^9$ operations per second?

Next lecture

LU, Cholesky and tridiagonal systems. Keep the multipliers and solve for many right-hand sides cheaply; exploit symmetry and sparsity.

Md Mahbub E Noor

Lecture 12: Gaussian and Gauss–Jordan Elimination

University of Barishal

23 / 23

Gaussian and Gauss–Jordan Elimination

The problem: temperatures inside a metal plate

Today's goals

The idea in one picture

The idea: reduce to a triangle, then solve upwards

Gaussian elimination, step by step

Explore: elimination, one row operation at a time

Problem 1: three equations by Gaussian elimination

Gauss–Jordan elimination, step by step

Problem 2: the inverse by Gauss–Jordan

How much work? The operation count

Same plate, two approaches

Classical (Cramer's rule)

Numerical (Gaussian elimination)

A 10 × 10 grid of points: 100 unknowns

The weakness: a tiny pivot destroys the answer

The fix: partial pivoting

Problem 3: the same system with 3-digit arithmetic

Gaussian elimination with partial pivoting

Practice problem

Gaussian elimination: method profile

Comparative analysis: elimination methods

Limitations, and where we fix them

Where this method runs in the real world

🌡️ Heat in a metal plate

📉 A curve through data points

⚗️ Balancing a chemical equation

🐍 numpy.linalg.solve

Checkpoint

Summary