Exercises — Solving linear systems — Gaussian elimination with partial pivoting

WHAT partial pivoting asks: among the entries in column 1, from the current row down, find the one with the largest absolute value. Column-1 entries are $2,-5,3$. Their absolute values are $|2|=2$, $|-5|=5$, $|3|=3$. The biggest is $5$, in row 2. WHY absolute value and not the value itself? A large magnitude (positive or negative) is what keeps the multiplier small; the sign is irrelevant to how "big" the number is as a divisor. Answer: swap row 2 into row 1.

WHAT the multiplier is: the number $m_{31}$ chosen so that $a_{31}-m_{31}{a}_{11}=0$. Solving, $m_{31}=\frac{a_{31}}{a_{11}}=\frac{-2}{4}=-0.5$. WHAT IT LOOKS LIKE: we subtract $-0.5\times (\text{pivot row})$ from row 3, i.e. we add half the pivot row. Since $|-0.5|\le 1$, this is a well-behaved (stable) step — exactly what pivoting guarantees.

WHAT "upper-triangular" means: every entry below the main diagonal is zero. $P$: below-diagonal entries are $(2,1)=0,(3,1)=0,(3,2)=0$ — all zero. ✅ $Q$: entry $(3,2)=1\ne 0$ — still a variable to kill. ❌ Answer: only $P$. Back-substitution needs each row (bottom-up) to expose exactly one new unknown; $Q$'s bottom two rows still tangle $x_2$ and $x_3$.

Augmented matrix: $\left[\begin{array}{ccc}2& 4& 10\\ 4& 3& 15\end{array}\right]$. Step 1 — pivot column 1. $|2|$ vs $|4|$ → biggest is $4$ (row 2). Swap: $\left[\begin{array}{ccc}4& 3& 15\\ 2& 4& 10\end{array}\right]$ Step 2 — eliminate. $m_{21}=\frac{2}{4}=0.5$ (note $|m_{21}|\le 1$ — the pivot paid off). Row${}_2\leftarrow$ Row${}_2-0.5\cdot$Row${}_1$: $a_{22}=4-0.5(3)=2.5$, $b_2=10-0.5(15)=2.5$. $\left[\begin{array}{ccc}4& 3& 15\\ 0& 2.5& 2.5\end{array}\right]$ Step 3 — back-substitute (bottom-up). $x_2=\frac{2.5}{2.5}=1$; $x_1=\frac{15-3(1)}{4}=\frac{12}{4}=3$. Answer: $x_1=3,x_2=1$. Check eq 2: $4(3)+3(1)=15$ ✅.

Column 1: $|1|$ vs $|-4|$ → biggest magnitude is $4$ (row 2). Swap: $\left[\begin{array}{ccc}-4& 1& 5\\ 1& -2& -3\end{array}\right]$ A negative pivot is completely fine — pivoting cares about magnitude, not sign. $m_{21}=\frac{1}{-4}=-0.25$. Row${}_2\leftarrow$Row${}_2-(-0.25)$Row${}_1=$Row${}_2+0.25$Row${}_1$: $a_{22}=-2+0.25(1)=-1.75$, $b_2=-3+0.25(5)=-1.75$. $\left[\begin{array}{ccc}-4& 1& 5\\ 0& -1.75& -1.75\end{array}\right]$ Back-sub: $x_2=\frac{-1.75}{-1.75}=1$; $x_1=\frac{5-1(1)}{-4}=\frac{4}{-4}=-1$. Answer: $x_1=-1,x_2=1$. Check eq 1: $-1-2(1)=-3$ ✅.

The naive pivot $a_{11}=0$ would force division by zero. This is exactly the emergency pivoting is built for. Column 1: $|0|$ vs $|3|$ → biggest is $3$ (row 2). Swap: $\left[\begin{array}{ccc}3& 1& 5\\ 0& 2& 4\end{array}\right]$ The system is already upper-triangular — no elimination needed! Back-sub: $x_2=\frac{4}{2}=2$; $x_1=\frac{5-1(2)}{3}=1$. Answer: $x_1=1,x_2=2$. A zero on the diagonal is not a dead end unless every entry below it is also zero.

Column 1. $|1|,|2|,|-1|$ → biggest $2$ (row 2). Swap rows 1,2: $\left[\begin{array}{cccc}2& -1& 3& 9\\ 1& 1& 1& 6\\ -1& 2& 1& 2\end{array}\right]$ $m_{21}=\frac{1}{2}=0.5$, $m_{31}=\frac{-1}{2}=-0.5$. Row${}_2\leftarrow$Row${}_2-0.5$Row${}_1$: $(0,1-0.5(-1),1-0.5(3)|6-0.5(9))=(0,1.5,-0.5|1.5)$. Row${}_3\leftarrow$Row${}_3+0.5$Row${}_1$: $(0,2+0.5(-1),1+0.5(3)|2+0.5(9))=(0,1.5,2.5|6.5)$. $\left[\begin{array}{cccc}2& -1& 3& 9\\ 0& 1.5& -0.5& 1.5\\ 0& 1.5& 2.5& 6.5\end{array}\right]$ Column 2 (rows 2,3): $|1.5|$ vs $|1.5|$ — a tie. On a tie we may keep the current row (no swap needed for stability). $m_{32}=\frac{1.5}{1.5}=1$. Row${}_3\leftarrow$Row${}_3-1\cdot$Row${}_2$: $(0,0,2.5-(-0.5)|6.5-1.5)=(0,0,3|5)$. $\left[\begin{array}{cccc}2& -1& 3& 9\\ 0& 1.5& -0.5& 1.5\\ 0& 0& 3& 5\end{array}\right]$ Back-sub. $x_3=\frac{5}{3}\approx 1.6667$; $x_2=\frac{1.5-(-0.5)x_3}{1.5}=\frac{1.5+0.5(5/3)}{1.5}=\frac{1.5+0.8333}{1.5}=1.5556$; $x_1=\frac{9-(-1)x_2-3x_3}{2}=\frac{9+1.5556-3(1.6667)}{2}=\frac{9+1.5556-5}{2}=2.7778$. Answer: $x_1\approx 2.7778,x_2\approx 1.5556,x_3\approx 1.6667$ (exactly $\frac{25}{9},\frac{14}{9},\frac{5}{3}$).

WHAT a multiplier is: $m_{ik}=\frac{a_{ik}}{a_{kk}}$ for rows $i>k$. WHAT pivoting guarantees: we swapped in the row whose column-$k$ entry has the largest absolute value among rows $k\dots n$. So the pivot satisfies $|a_{kk}|={\max }_{i\ge k}|a_{ik}|\ge |a_{ik}|\text{for every }i>k.$ Divide both sides by $|a_{kk}|>0$: $\frac{|a_{ik}|}{|a_{kk}|}\le 1⟹|m_{ik}|=\left|\frac{a_{ik}}{a_{kk}}\right|\le 1.$ WHY it matters: small multipliers mean the elimination step shrinks rather than amplifies existing round-off in each row — the numerical heart of stability. See Condition Number and Numerical Stability.

Column 1: $|0.001|$ vs $|1.00|$ → biggest $1.00$ (row 2). Swap — the whole point: $\left[\begin{array}{ccc}1.00& 2.00& 3.00\\ 0.001& 1.00& 1.00\end{array}\right]$ $m_{21}=\frac{0.001}{1.00}=0.001$ (tiny, $|m|\le 1$ ✅). $a_{22}=1.00-0.001(2.00)=1.00-0.002=0.998$ (3 s.f.). $b_2=1.00-0.001(3.00)=1.00-0.003=0.997$. Back-sub: $x_2=\frac{0.997}{0.998}=0.999$; $x_1=\frac{3.00-2.00(0.999)}{1.00}=3.00-1.998=1.00$. Answer (3 s.f.): $x_1\approx 1.00,x_2\approx 0.999$ — matches exact $1.001,0.999$ to full displayed precision. Contrast: without swapping, $m_{21}=1/0.001=1000$, and $a_{22}=1.00-1000(2.00)\approx -2000$ swamps the useful digits. Pivoting salvaged the accuracy. See Round-off Error in Floating Point.

The permutation swapped rows 1,2, so $P=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$ and $PA=\left[\begin{array}{cc}4& 3\\ 2& 4\end{array}\right].$ The single multiplier was $m_{21}=0.5$. In LU form, $L$ holds the multipliers below its unit diagonal, $U$ holds the eliminated (upper-triangular) result: $L=\left[\begin{array}{cc}1& 0\\ 0.5& 1\end{array}\right],U=\left[\begin{array}{cc}4& 3\\ 0& 2.5\end{array}\right].$ Check $LU$: $\left[\begin{array}{cc}1& 0\\ 0.5& 1\end{array}\right]\left[\begin{array}{cc}4& 3\\ 0& 2.5\end{array}\right]=\left[\begin{array}{cc}4& 3\\ 2& 4\end{array}\right]=PA$ ✅. WHY this is the same computation: partial-pivoted Gaussian elimination is the algorithm that produces $PA=LU$. See LU Decomposition; solving then splits into Back-substitution and Forward-substitution.

KEY fact: row operations of type "add a multiple of a row to another" do not change the determinant; each row swap flips the sign. After elimination we reached the upper-triangular $U=\left[\begin{array}{ccc}2& -1& 3\\ 0& 1.5& -0.5\\ 0& 0& 3\end{array}\right].$ The determinant of an upper-triangular matrix is the product of its diagonal: $\det U=2\cdot 1.5\cdot 3=9.$ We performed one row swap (column 1), so $\det A=(-1{)}^1\det U=-9.$ Check (direct expansion): $\det A=1(-1-6)-1(2+3)+1(4-1)=-7-5+3=-9$ ✅. See Determinants.

$\det A=2(3)-4(4)=6-16=-10.$ Replace column 1 by $\mathbf{b}=(10,15)$: $\det A_1=\left|\begin{array}{cc}10& 4\\ 15& 3\end{array}\right|=10(3)-4(15)=30-60=-30.$ Replace column 2: $\det A_2=\left|\begin{array}{cc}2& 10\\ 4& 15\end{array}\right|=2(15)-10(4)=30-40=-10.$ $x_1=\frac{\det A_1}{\det A}=\frac{-30}{-10}=3,x_2=\frac{\det A_2}{\det A}=\frac{-10}{-10}=1.$ Answer matches ✅. WHY prefer elimination for large $n$: Cramer's Rule needs $n+1$ determinants ($\sim n\cdot n!$ work); elimination is $\sim \frac{2}{3}{n}^3$ — vastly cheaper as $n$ grows.

Column 1: $|1|,|2|,|1|$ → biggest $2$ (row 2). Swap rows 1,2: $\left[\begin{array}{cccc}2& 4& 6& 12\\ 1& 2& 3& 6\\ 1& 1& 1& 3\end{array}\right]$ $m_{21}=0.5,m_{31}=0.5$. Row${}_2\leftarrow$Row${}_2-0.5$Row${}_1$: $(0,2-2,3-3|6-6)=(0,0,0|0)$. Row${}_3\leftarrow$Row${}_3-0.5$Row${}_1$: $(0,1-2,1-3|3-6)=(0,-1,-2|-3)$. $\left[\begin{array}{cccc}2& 4& 6& 12\\ 0& 0& 0& 0\\ 0& -1& -2& -3\end{array}\right]$ Column 2 (rows 2,3): candidates $0$ and $-1$ → biggest $|-1|$ (row 3). Swap: $\left[\begin{array}{cccc}2& 4& 6& 12\\ 0& -1& -2& -3\\ 0& 0& 0& 0\end{array}\right]$ The last pivot is $0$ — column 3, row 3, entry $0$, and there is nothing below to swap in. $A$ is singular. What it means: the bottom row reads $0\cdot x_3=0$ — always true, so the system has infinitely many solutions (the equations were linearly dependent: row 2 was $2\times$ row 1). The $0=0$ (not $0=\text{nonzero}$) tells us consistent-but-not-unique, not "no solution". A zero pivot always signals $\det A=0$.

Design idea: put a tiny number where the first pivot sits. Take $\{\begin{array}{l}0.00100x_1+1.00x_2=1.00\\ 1.00x_1+1.00x_2=2.00\end{array}$ Exact solution: subtract — $(1-0.001)x_1=2-1$, $x_1=\frac{1}{0.999}=1.001\approx 1$, $x_2=2-1.001=0.999\approx 1$. Good. Route A — NO pivoting (3 s.f.): $m_{21}=\frac{1.00}{0.00100}=1000$. $a_{22}=1.00-1000(1.00)=-999$; $b_2=2.00-1000(1.00)=-998$. $x_2=\frac{-998}{-999}=0.999$; then $x_1=\frac{1.00-1.00(0.999)}{0.00100}=\frac{0.001}{0.001}$. But at 3 s.f., $1.00-0.999$ rounds to $\approx 0.00$ (catastrophic cancellation) → $x_1\approx \frac{0}{0.001}=0$. Wrong ($x_1=0$ instead of $1$). Route B — WITH pivoting. Swap (row 2 has $|1.00|>|0.001|$): $\left[\begin{array}{cccc}1& 1& |& 2\\ 0.001& 1& |& 1\end{array}\right]$, $m_{21}=0.001$, $a_{22}=1-0.001=0.999$, $b_2=1-0.002=0.998$. $x_2=\frac{0.998}{0.999}=0.999$; $x_1=\frac{2-0.999}{1}=1.00$. Correct ✅. Moral: the tiny pivot forces a subtraction of two near-equal numbers in back-substitution — pivoting reorders so the divisor is $O(1)$ and the cancellation never happens.

Column 1 magnitudes: $|0.2|=0.2,|7|=7,|-3|=3$. Biggest is $7$ → row 2 becomes the pivot row (swap rows 1,2). After swapping, the pivot is $a_{11}=7$; remaining column-1 entries are $0.2$ (old row 1, now row 2) and $-3$ (row 3). $m_{21}=\frac{0.2}{7}\approx 0.02857,m_{31}=\frac{-3}{7}\approx -\mathrm{0.42857.}$ Both satisfy $|m|\le 1$ ✅ — exactly the guarantee of L3.2. Had we not pivoted, the divisor would have been $0.2$, giving $m_{21}=35$ and $m_{31}=-15$: monster multipliers, unstable.

• Deeper stability theory → Condition Number and Numerical Stability
• When elimination is too slow → Iterative Methods (Jacobi, Gauss-Seidel)
• The factorization view → LU Decomposition and Back-substitution and Forward-substitution