Gaussian elimination — forward elimination, back substitution

What are we actually solving?

Forward elimination — building the staircase

HOW (the multiplier formula). To clear the entry $a_{ik}$ that sits below pivot $a_{kk}$ , choose multiplier $m_{ik}=\frac{a_{ik}}{a_{kk}}$ then do $R_i \to R_i - m_{ik}R_k$ .

Figure — Gaussian elimination — forward elimination, back substitution

Back substitution — climbing back up

Worked Example 1 — a clean $3\times3$

Solve $\begin{aligned}2x+y-z&=8\\ -3x-y+2z&=-11\\ -2x+y+2z&=-3\end{aligned}$

Augmented matrix: $\left[\begin{array}{ccc|c}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}\right]$

Step A. Pivot $a_{11}=2$ . Clear column 1.

$m_{21}=-3/2$ , so $R_2\to R_2-(-\tfrac32)R_1$ . Why? This makes the $-3$ become $0$ .
$m_{31}=-2/2=-1$ , so $R_3\to R_3-(-1)R_1=R_3+R_1$ . Why? Kills the $-2$ .

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

Step B. Pivot $a_{22}=\tfrac12$ . Clear below it.

$m_{32}=2/(1/2)=4$ , so $R_3\to R_3-4R_2$ . Why? Makes the $2$ in column 2 become $0$ .

$\left[\begin{array}{ccc|c}2&1&-1&8\\0&\tfrac12&\tfrac12&1\\0&0&-1&1\end{array}\right]$ Now it's upper-triangular — forward elimination is done.

Back substitution.

Row 3: $-z=1\Rightarrow z=-1$ . Why this step? Last row has one unknown.
Row 2: $\tfrac12 y+\tfrac12 z=1\Rightarrow \tfrac12 y-\tfrac12=1\Rightarrow y=3$ . Why? $z$ now known, only $y$ left.
Row 1: $2x+y-z=8\Rightarrow 2x+3+1=8\Rightarrow x=2$ . Why? Only $x$ remains.

Answer: $\boxed{x=2,\ y=3,\ z=-1}$ . (Check row 2 original: $-6-3-2=-11$ ✓.)

Worked Example 2 — pivoting needed

Solve $\left[\begin{array}{cc|c}0&2&4\\1&3&5\end{array}\right]$ Step. Pivot position $(1,1)$ is $0$ — division by zero! Why is a swap forced? A pivot must be nonzero. Swap $R_1\leftrightarrow R_2$ : $\left[\begin{array}{cc|c}1&3&5\\0&2&4\end{array}\right]$ Already triangular. Back-sub: $2y=4\Rightarrow y=2$ ; $x+3(2)=5\Rightarrow x=-1$ .

Worked Example 3 — no/infinite solutions

$\left[\begin{array}{cc|c}1&2&3\\2&4&7\end{array}\right]\xrightarrow{R_2\to R_2-2R_1}\left[\begin{array}{cc|c}1&2&3\\0&0&1\end{array}\right]$ Row 2 says $0=1$ — impossible, so the system is inconsistent (no solution). Why does elimination reveal this? It produces $0=$ nonzero only when equations contradict. If instead the last entry were $0$ (row $0\,0\mid0$ ), we'd have a free variable and infinitely many solutions.

Common mistake Steel-manned common errors

1. Forgetting to apply the operation to the RHS column. Why it feels right: you focus on "triangularising $A$ ." Fix: always operate on the augmented matrix; the $\mathbf{b}$ entry rides along with each row.

2. Wrong sign in the multiplier. People write $R_i \to R_i + m R_k$ with $m=a_{ik}/a_{kk}$ and get the wrong result. Why it feels right: "add to combine." Fix: the safe template is $R_i \to R_i - \frac{a_{ik}}{a_{kk}}R_k$ — minus, because we're subtracting away the unwanted part.

3. Dividing by a zero pivot. Why it feels right: the algorithm "just marches down columns." Fix: if a pivot is $0$ , swap in a lower row; if none exists in that column, move to the next column (free variable).

4. Doing back-substitution top-down. Why it feels right: we read top to bottom. Fix: triangular structure only isolates one variable at the bottom — start there and climb.

Recall Feynman: explain to a 12-year-old

Imagine three friends who together know your secret number through riddles, but each riddle mixes all clues. You rewrite the first riddle and subtract it from the others so the second riddle no longer mentions the first clue, and so on — until the last riddle mentions only one clue and you can read it straight off. Then you go back up: "Now I know the last number, I plug it in and the previous riddle reveals the next number." Keep climbing until you know them all. That's it.

Recall checkpoint

What shape does forward elimination produce?

Upper-triangular matrix

U

(all zeros below the diagonal).

Multiplier to eliminate entry

a_{ik}

below pivot

a_{kk}

m_{ik}=a_{ik}/a_{kk}

, then

R_i\to R_i-m_{ik}R_k

Why is

R_i\to R_i-mR_j

a legal operation?

It preserves the solution set and is reversible (adding a multiple of a true equation keeps it true).

What forces a row swap during elimination?

A zero pivot (can't divide by it); partial pivoting also swaps in the largest entry for numerical accuracy.

Back-substitution formula for

x_i

x_i=\dfrac{1}{u_{ii}}\left(c_i-\sum_{j>i}u_{ij}x_j\right)

Which variable is solved first in back substitution?

The last one,

x_n=c_n/u_{nn}

, from the bottom row.

After elimination a row reads

0\ 0\ \dots\mid d

with

d\neq0

. What does it mean?

System is inconsistent — no solution.

After elimination a row is entirely zero (

0\dots0\mid0

). What does it mean?

A free variable exists — infinitely many solutions.

Why operate on the augmented matrix

[A\mid b]

So row operations transform the right-hand side consistently with the coefficients.

Connections

LU Decomposition — storing the multipliers $m_{ik}$ gives $A=LU$ .
Row Echelon Form / Reduced Row Echelon Form — the goal shapes of elimination.
Pivoting and Numerical Stability — why we swap rows in practice.
Rank of a Matrix — number of pivots = rank.
Determinant — product of pivots (with sign from swaps) gives $\det A$ .
Solving Linear Systems — Consistency — interpreting no/one/infinite solutions.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, Gaussian elimination ka core idea bahut simple hai. Jab tumhare paas teen equations hain aur har equation mein x, y, z teeno mix ho rahe hain, tab solve karna mushkil hota hai. Toh hum ek trick lagate hain: ek equation ko use karke baaki equations se ek variable ko "kill" kar dete hai. Isko bolte hain forward elimination. Column by column chalte hain — pehle column ke pivot se neeche sab zero banao, phir doosre column ka, aur aise hi. End mein matrix upper-triangular ban jaata hai, yaani diagonal ke neeche sab zero.

Multiplier ka formula yaad rakhne ki zaroorat hi nahi — wo khud derive ho jaata hai. Agar pivot $a_{kk}$ hai aur uske neeche wala entry $a_{ik}$ ko zero karna hai, toh multiplier $m=a_{ik}/a_{kk}$ lo aur $R_i \to R_i - m R_k$ karo. Bas, "jitna chahiye utna subtract karo taaki cancel ho jaaye." Yahi logic hai.

Phir aata hai back substitution — neeche se upar. Last row mein sirf ek variable bachta hai (jaise $-z=1$ , toh $z=-1$ ). Use ko upar plug karo, ab next variable nikal aata hai. Aise climb karte raho top tak. Important: hamesha augmented matrix $[A|b]$ pe kaam karo, RHS ko bhi saath mein change karo, warna answer galat aayega.

Ek aur baat — agar pivot zero aa jaaye toh row swap maaro (partial pivoting), kyunki zero se divide nahi kar sakte. Aur agar elimination ke baad koi row $0\,0\,0\,|\,5$ jaisi aaye, matlab system ka koi solution nahi (inconsistent). Ye sab concepts LU decomposition aur rank mein bhi kaam aate hain, isliye yeh foundation pakka karna zaroori hai.

Gaussian elimination — forward elimination, back substitution

What are we actually solving?

Forward elimination — building the staircase

Back substitution — climbing back up

Worked Example 1 — a clean $3\times3$

Worked Example 2 — pivoting needed

Worked Example 3 — no/infinite solutions

Recall checkpoint

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Linear Algebra (Full)

Connections