Gaussian Elimination

Gaussian elimination is the fundamental algorithm for solving $Ax = b$ without ever computing $A^{-1}$. It works by applying systematic row operations to transform $A$ into a triangular form. Once in triangular form, the system is easy to solve by simple substitution — each equation contains one fewer unknown than the one below it, so we can unwind the solution one variable at a time.

---

Triangular Matrices

Two special matrix shapes make substitution trivial.

A lower triangular matrix $L$ has zeros everywhere above the main diagonal:

$L=\begin{bmatrix}l_{11}&0&\dots&0\\l_{21}&l_{22}&\dots&0\\\vdots&\vdots&\ddots&\vdots\\l_{n1}&l_{n2}&\dots&l_{nn}\end{bmatrix}$

An upper triangular matrix $U$ has zeros everywhere below the main diagonal:

$U=\begin{bmatrix}u_{11}&u_{12}&\dots&u_{1n}\\0&u_{22}&\dots&u_{2n}\\\vdots&\vdots&\ddots&\vdots\\0&0&\dots&u_{nn}\end{bmatrix}$

---

Forward Substitution

When the system $Lx = b$ is lower triangular, we can solve it top-down: find $x_1$ from the first equation, substitute into the second to find $x_2$, and so on. This is called forward substitution.

Using a $4 \times 4$ lower triangular system:

$\begin{bmatrix}l_{11}&0&0&0\\l_{21}&l_{22}&0&0\\l_{31}&l_{32}&l_{33}&0\\l_{41}&l_{42}&l_{43}&l_{44}\end{bmatrix}\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\end{bmatrix}=\begin{bmatrix}b_{1}\\b_{2}\\b_{3}\\b_{4}\end{bmatrix}$

Row 1: $l_{11}x_{1} = b_{1}$

$x_{1}=\frac{b_{1}}{l_{11}} \qquad \text{(1 division)}$

Row 2: $l_{21}x_{1}+l_{22}x_{2}=b_{2}$

$x_{2}=\frac{b_{2}-l_{21}x_{1}}{l_{22}} \qquad \text{(1 div, 1 mult, 1 sub)}$

Row 3: $l_{31}x_{1}+l_{32}x_{2}+l_{33}x_{3}=b_{3}$

$x_{3}=\frac{b_{3}-l_{31}x_{1}-l_{32}x_{2}}{l_{33}} \qquad \text{(1 div, 2 mult, 2 sub)}$

Row 4: $l_{41}x_{1}+l_{42}x_{2}+l_{43}x_{3}+l_{44}x_{4}=b_{4}$

$x_{4}=\frac{b_{4}-l_{41}x_{1}-l_{42}x_{2}-l_{43}x_{3}}{l_{44}} \qquad \text{(1 div, 3 mult, 3 sub)}$

Because we solve from $x_1$ down to $x_n$, this is called a top-down approach.

---

Operation Count

For the $j$-th variable, we always need 1 division, $(j-1)$ multiplications, and $(j-1)$ subtractions. The total number of arithmetic operations across all $n$ variables is:

$\text{Total operations}=\sum_{j=1}^{n}\bigl[1+2(j-1)\bigr]$

$=\sum_{j=1}^{n}(2j-1)$

$=2\sum_{j=1}^{n}j-\sum_{j=1}^{n}1$

$=2\cdot\frac{n(n+1)}{2}-n$

$=n(n+1)-n$

$\boxed{= n^{2}}$

Forward substitution on a lower triangular $n \times n$ system costs exactly $n^2$ arithmetic operations.

---

Applying Gaussian Elimination

To solve a general $Ax = b$, we first transform $A$ into upper triangular form using row operations. The key operation is: for each column $k$, eliminate all entries below the diagonal by subtracting a scaled multiple of row $k$ from every row below it.

Starting from a general $4 \times 4$ matrix, the column-by-column elimination looks like this:

$\begin{bmatrix}X&X&X&X\\X&X&X&X\\X&X&X&X\\X&X&X&X\end{bmatrix}\rightarrow\begin{bmatrix}X&X&X&X\\0&X&X&X\\0&X&X&X\\0&X&X&X\end{bmatrix}\rightarrow\begin{bmatrix}X&X&X&X\\0&X&X&X\\0&0&X&X\\0&0&X&X\end{bmatrix}\rightarrow\begin{bmatrix}X&X&X&X\\0&X&X&X\\0&0&X&X\\0&0&0&X\end{bmatrix}$

Each arrow represents one round of row operations that zeroes out one column below the diagonal. After $n-1$ rounds the matrix is in upper triangular form and the system can be solved by back substitution (the top-down logic in reverse: solve $x_n$ first, then substitute upward).

The diagonal element used to eliminate entries below it in each round is called the pivot. A non-zero pivot is required for each step to proceed.

The general formula for the multiplier used to eliminate entry $a_{ik}$ in column $k$ is:

$m_{ik} = \frac{a_{ik}}{a_{kk}}$

And the row operation applied to row $i$ is:

$R_i \leftarrow R_i - m_{ik} R_k$

---

Worked Example: Augmented Matrix

Problem: Solve the following system using Gaussian elimination.

$x_{1}+2x_{2}+x_{3}=0$

$x_{1}-2x_{2}+2x_{3}=4$

$2x_{1}+12x_{2}-2x_{3}=4$

Step 1 — Set up the augmented matrix

Write $A$ and $b$ side by side, separated by a vertical bar:

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

Step 2 — First round of elimination (clear column 1 below the pivot)

The pivot is $a_{11} = 1$. Compute multipliers $m_{21} = \dfrac{a_{21}}{a_{11}} = \dfrac{1}{1} = 1$ and $m_{31} = \dfrac{a_{31}}{a_{11}} = \dfrac{2}{1} = 2$.

Apply $R_2 \leftarrow R_2 - m_{21}\,R_1$ and $R_3 \leftarrow R_3 - m_{31}\,R_1$:

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

Step 3 — Second round of elimination (clear column 2 below the pivot)

The new pivot is $a_{22} = -4$. Compute multiplier $m_{32} = \dfrac{a_{32}}{a_{22}} = \dfrac{8}{-4} = -2$.

Apply $R_3 \leftarrow R_3 - m_{32}\,R_2$:

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

The matrix is now upper triangular. The corresponding system is:

$x_1 + 2x_2 + x_3 = 0$

$-4x_2 + x_3 = 4$

$-2x_3 = 12$

Step 4 — Back substitution

Solve from the bottom equation upward.

From row 3:

$-2x_{3}=12 \implies x_{3}=-6$

From row 2:

$-4x_{2}+x_{3}=4 \implies -4x_{2}+(-6)=4 \implies -4x_{2}=10 \implies x_{2}=-2.5$

From row 1:

$x_{1}+2x_{2}+x_{3}=0 \implies x_{1}+2(-2.5)+(-6)=0 \implies x_{1}-11=0 \implies x_{1}=11$

Step 5 — Solution

$\boxed{x_1 = 11,\quad x_2 = -2.5,\quad x_3 = -6}$

Note

When applying row operations to the augmented matrix, the right-hand side column is updated at every step along with the coefficient columns. This keeps $Ax = b$ consistent throughout the process — the augmented form ensures we are solving the same system at every stage.