Gaussian Elimination

At a Glance

• Frequency: 1 sub-part across 1 of 13 years (2022)
• Priority tier: T4
• Marks (count): 10 (1)
• Average solve time: ~18 min
• Difficulty mix: medium 1
• Section: A | Dominant type: computation

Why This Chapter Matters

Gaussian elimination is the workhorse algorithm for solving linear systems and is tested as a direct computation — write the augmented matrix, apply row operations to reach upper-triangular form, then back-substitute. UPSC 2022 set a $3 \times 3$ or $4 \times 4$ system; the marks are earned by showing each elimination step clearly, not just writing the answer.

Minimum Theory

Problem. Solve $Ax = b$ where $A$ is $n \times n$ and non-singular.

Augmented matrix. Write $[A \mid b]$ and apply elementary row operations:

$R_i \leftarrow R_i - m_{ij}\, R_j, \quad m_{ij} = \frac{a_{ij}}{a_{jj}}$

The scalar $m_{ij}$ is the multiplier for eliminating entry $(i,j)$ using row $j$ as the pivot row.

Forward elimination. For $j = 1, 2, \ldots, n-1$ (pivot columns):

• For each $i = j+1, \ldots, n$ (rows below the pivot):
  • Compute multiplier $m_{ij} = a_{ij}^{(j)} / a_{jj}^{(j)}$.
  • Replace $R_i \leftarrow R_i - m_{ij} R_j$.

After $n-1$ stages the system is upper triangular: $Ux = c$.

Back substitution. Solve from the last equation upward:

$x_n = \frac{c_n}{u_{nn}}, \qquad x_i = \frac{1}{u_{ii}}\!\left(c_i - \sum_{k=i+1}^{n} u_{ik}\, x_k\right), \quad i = n-1, \ldots, 1$

Operation count.

• Forward elimination: $\approx \frac{n^3}{3}$ multiplications/divisions.
• Back substitution: $\approx \frac{n^2}{2}$ operations.

Partial pivoting. Before eliminating column $j$, find the row $r \ge j$ with the largest $|a_{rj}^{(j)}|$ and swap rows $r$ and $j$. This prevents division by a small pivot and improves numerical stability. UPSC problems on small integer systems do not require pivoting, but mentioning it earns method marks.

Distinction from Gauss–Jordan. Gaussian elimination stops at upper-triangular form and uses back substitution. Gauss–Jordan continues to reduced row echelon form (zeros above and below each pivot), obtaining $x$ directly without back substitution. UPSC tests these as separate atoms.

Question Archetypes

solve-system (1 question; 2022)

Recognition Cues

• “Solve the following system of equations using Gaussian elimination.”
• A $3 \times 3$ or $4 \times 4$ integer-coefficient system.
• No instruction to find the inverse — that is Gauss–Jordan.

Solution Template

1. Write the augmented matrix $[A \mid b]$.
2. Use $R_1$ as pivot row; eliminate $x_1$ from rows 2 and 3 (and 4 if $4\times4$).
3. Use $R_2$ (updated) as pivot row; eliminate $x_2$ from remaining rows below.
4. Continue until upper triangular.
5. Back-substitute from the bottom row upward; box each $x_i$.

Worked Example

2022 Paper 2, 2022-P2-Q2a (10 marks)

Solve the system using Gaussian elimination:

$2x + y - z = 8$

$-3x - y + 2z = -11$

$-2x + y + 2z = -3$

Augmented matrix.

$[A \mid b] = \begin{bmatrix} 2 & 1 & -1 & \bigm| & 8 \\ -3 & -1 & 2 & \bigm| & -11 \\ -2 & 1 & 2 & \bigm| & -3 \end{bmatrix}$

Stage 1 — eliminate $x$ from rows 2 and 3 using row 1 as pivot.

Multipliers: $m_{21} = -3/2$, $m_{31} = -2/2 = -1$.

$R_2 \leftarrow R_2 - \left(-\tfrac{3}{2}\right)R_1 = R_2 + \tfrac{3}{2}R_1$

$\text{Row 2: } \left[-3 + \tfrac{3}{2}(2),\ -1 + \tfrac{3}{2}(1),\ 2 + \tfrac{3}{2}(-1)\ \bigm|\ -11 + \tfrac{3}{2}(8)\right] = \left[0,\ \tfrac{1}{2},\ \tfrac{1}{2}\ \bigm|\ 1\right]$

$R_3 \leftarrow R_3 - (-1)R_1 = R_3 + R_1$

$\text{Row 3: } [-2+2,\ 1+1,\ 2+(-1)\ \bigm|\ -3+8] = [0,\ 2,\ 1\ \bigm|\ 5]$

Matrix after stage 1:

$\begin{bmatrix} 2 & 1 & -1 & \bigm| & 8 \\ 0 & \tfrac{1}{2} & \tfrac{1}{2} & \bigm| & 1 \\ 0 & 2 & 1 & \bigm| & 5 \end{bmatrix}$

Stage 2 — eliminate $y$ from row 3 using row 2 as pivot.

Multiplier: $m_{32} = 2 / (1/2) = 4$.

$R_3 \leftarrow R_3 - 4 R_2$

$\text{Row 3: } [0,\ 2-4(\tfrac{1}{2}),\ 1-4(\tfrac{1}{2})\ \bigm|\ 5-4(1)] = [0,\ 0,\ -1\ \bigm|\ 1]$

Upper-triangular system:

$\begin{bmatrix} 2 & 1 & -1 & \bigm| & 8 \\ 0 & \tfrac{1}{2} & \tfrac{1}{2} & \bigm| & 1 \\ 0 & 0 & -1 & \bigm| & 1 \end{bmatrix}$

Back substitution.

Row 3: $-z = 1 \implies z = -1$.

Row 2: $\tfrac{1}{2}y + \tfrac{1}{2}(-1) = 1 \implies \tfrac{1}{2}y = \tfrac{3}{2} \implies y = 3$.

Row 1: $2x + 3 - (-1) = 8 \implies 2x = 4 \implies x = 2$.

$\boxed{x = 2,\quad y = 3,\quad z = -1}$

Verification. $2(2)+3-(-1)=8$ ✓; $-3(2)-3+2(-1)=-11$ ✓; $-2(2)+3+2(-1)=-3$ ✓.

Common Traps

• Arithmetic slip in the multiplier: $m_{ij} = a_{ij}/a_{jj}$ (row $i$ entry divided by pivot, not vice versa).
• Forgetting to update the right-hand side column $b$ during each row operation.
• Applying elimination in the wrong order — always eliminate column $j$ from rows $j+1, \ldots, n$ using row $j$, never from rows above.
• Confusing this with Gauss–Jordan: stop at upper-triangular and back-substitute; do not continue to RREF.

Marks-Aware Writing

For 10 marks in Section A, the examiner expects: (i) the augmented matrix written explicitly, (ii) each row operation labelled with its multiplier, (iii) the resulting matrix after each stage, (iv) back substitution with each variable solved in turn, and (v) a verification line. Skipping to the answer without showing row operations will lose the bulk of the marks.

Practice Set

Only one historical question on this atom (shown above).