Gaussian elimination — forward elimination, back substitution: Foundations

Before you can do elimination you must be fluent in a small alphabet. This page builds every letter of it from nothing. Read top to bottom — each idea is used by the next.

1. A number laid out in a grid — the matrix

The picture: think of a spreadsheet. Each number lives at a fixed street address given by (which row, which column).

Figure — Gaussian elimination — forward elimination, back substitution

2. Naming a single entry — the subscript $a_{ik}$

So $a_{23}$ is row 2, column 3 (the red-boxed entry in Figure 1). Read it as " $a$ sub two three", never "twenty-three".

3. The diagonal and what sits below it

Everything to the lower-left of that line is "below the diagonal". Forward elimination's whole job is to make all of those below-diagonal entries into zero.

4. Bold letters — the vector $x$ and $b$

$x = x y z, b = 8 - 11 - 3$

The bold font is a promise: "this is a whole stack, not one number." A plain $x$ is one number; bold $x$ is the list of all unknowns.

5. Multiplying a grid by a stack — $A x$

For row $i$ : $a_{i 1} x_{1} + a_{i 2} x_{2} + \dots + a_{in} x_{n}$ . That sum is exactly the left-hand side of equation $i$ . (This is why the number of columns $n$ must equal the length of $x$ : each column entry needs a partner in $x$ .)

6. Packing them together — the augmented matrix $[A ∣ b]$

$2 - 3 - 2 1 - 1 1 - 1 22 8 - 11 - 3$

7. The three legal moves — row operations

The arrow $\to$ means "becomes". $R_{i}$ names "row $i$ as a whole line". The two-headed arrow $\leftrightarrow$ means "trade places".

8. The star of the show — the pivot and the multiplier $m_{ik}$

The fraction bar here is ordinary division. We divide the entry we want to kill by the pivot, because that ratio tells us "how many pivot-rows' worth of this column sits in row $i$ ."

9. Sum shorthand — the symbol $\sum$

Once forward elimination finishes, $A$ has become the upper-triangular matrix $U$ , and $b$ has become a new right-hand column we rename $c$ (because every row operation changed it too). We name the pieces of these:

So $\sum_{j = 2}^{3} u_{1 j} x_{j} = u_{12} x_{2} + u_{13} x_{3}$ : just a compact way to write a long " $+ + +$ " chain when we don't know in advance how many terms there are.

10. Reading the final staircase — back substitution

Using the names from Section 9, once $A$ is the staircase $U$ with new right side $c$ , the bottom row has a single unknown, so you solve it directly; then climb, each row up handing you one new unknown.

$x_{n} = \frac{c _{n}}{u _{nn}}, x_{i} = \frac{1}{u _{ii}} (c_{i} - \sum_{j = i + 1}^{n} u_{ij} x_{j}) .$

Here $u_{ii}$ is the diagonal (pivot) entry in row $i$ of $U$ , $u_{ij}$ are the other entries along that row, and $c_{i}$ is the transformed right-hand number. Dividing by $u_{ii}$ is the final "solve for the lone unknown" step — which is exactly why $u_{ii}$ must not be zero.

Recall Symbol speed-check

What does $a_{31}$ point to? ::: Row 3, column 1. What does the bar in $[A ∣ b]$ separate? ::: Coefficients (left) from right-hand-side values (right). Why must a pivot be nonzero? ::: We divide by it in the multiplier $a_{ik} / a_{k k}$ . What do you do if the pivot $a_{k k} = 0$ ? ::: Swap in a lower row with a nonzero entry in that column; if none exists, skip the column (free variable). What is $c$ ? ::: The right-hand column $b$ after forward elimination has transformed it. What does $\sum_{j = i + 1}^{n}$ tell $j$ to do? ::: Run from $i + 1$ up to $n$ , adding each term.

How the foundations feed the topic

Equipment checklist

Cover the right side; you are ready for the parent note only if you can answer each.

I can locate entry $a_{ik}$ in a grid ::: row $i$ , column $k$ — down first, then across.
I know what the index letters mean ::: $i$ = row ( $1 \dots m$ ), $j$ = column ( $1 \dots n$ ), $k$ = current pivot column.
I know why $x$ has length $n$ ::: $A$ has $n$ columns, one per unknown, so $x$ needs $n$ entries; $b$ has $m$ entries, one per row.
I know what "upper-triangular" looks like ::: all zeros below the main diagonal; nonzeros form a triangle on and above it.
I can turn $A x = b$ back into ordinary equations ::: multiply each row of $A$ against $x$ and set equal to the matching entry of $b$ .
I know why we use the augmented matrix ::: so the right-hand side changes together with the coefficients under every row operation.
I can state the three legal row operations ::: swap, scale by nonzero $c$ , and replace $R_{i} \to R_{i} - m R_{j}$ .
I can derive the multiplier without memorising ::: set $a_{ik} - m_{ik} a_{k k} = 0$ , solve to get $m_{ik} = a_{ik} / a_{k k}$ .
I know what to do with a zero pivot ::: swap in a lower row with a nonzero entry; if none, skip the column.
I know the names $u_{ij}$ and $c_{i}$ ::: entries of the finished upper-triangular $U$ and of the transformed right-hand column $c$ .
I can expand a $\sum$ ::: write out each term for $j$ from the start value to the end value and add them.

Connections

Solving Linear Systems — Consistency — what the final staircase tells you about no / one / infinite solutions.
Row Echelon Form / Reduced Row Echelon Form — the tidy shapes these foundations aim at.
LU Decomposition — where the multipliers $m_{ik}$ get stored and reused.
Pivoting and Numerical Stability — why "pivot must be nonzero" grows into "pivot should be large".
Rank of a Matrix — counting the pivots you build here.
Determinant — read off the diagonal of $U$ once the staircase is done.