Gaussian Elimination and Pivoting

Solving a portfolio-optimization system $Ax = b$ for optimal weights $x$ means solving several linear equations simultaneously. Gaussian elimination is the systematic procedure — the same one taught in introductory algebra — for reducing that system, equation by equation, to a form that's trivial to solve by back-substitution. It's mechanical and always works in exact arithmetic, but on a computer, doing the steps in the wrong order can quietly wreck the accuracy of the answer, which is exactly the problem pivoting exists to fix.

An analogy: tidying a messy system by canceling variables

Imagine three equations in three unknowns, and you want to solve them by hand: pick one equation, use it to eliminate the first variable from the other two equations, then use one of the remaining two to eliminate the second variable from the last one — leaving one equation in one unknown, easily solved. Then substitute that answer back up the chain to get the rest. This is exactly Gaussian elimination: a step-by-step reduction from "many unknowns tangled together" to "one unknown, then unwind."

The math, one piece at a time

Given $Ax = b$, Gaussian elimination systematically zeroes out entries below the diagonal, column by column, using row operations: subtracting a multiple of one row from another. To eliminate the entry $A_{i1}$ in row $i$ using row 1's leading entry (the pivot) $A_{11}$, subtract $\frac{A_{i1}}{A_{11}}$ times row 1 from row $i$:

$$\text{row}_i \; \leftarrow \; \text{row}_i - \frac{A_{i1}}{A_{11}} \, \text{row}_1 .$$

In words: this row operation is designed to make the new $A_{i1}$ exactly zero, while keeping the system's true solution unchanged, because subtracting a scaled copy of one true equation from another true equation produces another true equation. Repeating this for every row below, then moving to the second column and repeating, eventually leaves $A$ in upper triangular form — zeros everywhere below the diagonal — from which $x$ is found by back-substitution, solving the last (simplest) equation first and working upward.

Pivoting addresses what happens when the pivot $A_{11}$ (or any pivot along the way) is small relative to the entries it's dividing into. Dividing by a small number amplifies whatever rounding error is already present in the other entries — the same kind of error explosion seen in catastrophic cancellation. Partial pivoting fixes this by, before each elimination step, swapping rows so the largest available entry (in absolute value) in the current column becomes the pivot — mathematically this changes nothing about the solution (swapping equations doesn't change the system), but it keeps every division well-conditioned, controlling the growth of rounding error throughout the whole procedure.

Worked example 1: elimination by hand

Solve $\begin{pmatrix}2&1\\4&3\end{pmatrix}\begin{pmatrix}x_1\\x_2\end{pmatrix}=\begin{pmatrix}5\\11\end{pmatrix}$. Eliminate the entry below the pivot: $\text{row}_2 \leftarrow \text{row}_2 - \frac{4}{2}\text{row}_1 = \text{row}_2 - 2\,\text{row}_1$, giving row 2 as $(4-2\cdot2,\;3-2\cdot1 \mid 11-2\cdot5) = (0,\;1\mid 1)$. Back-substitute: $x_2 = 1$; then row 1 gives $2x_1 + 1(1) = 5 \Rightarrow x_1 = 2$. Check: $2(2)+1(1)=5$ ✓, $4(2)+3(1)=11$ ✓.

Worked example 2: why pivoting matters, with real numbers

Solve $\begin{pmatrix}0.0001&1\\1&1\end{pmatrix}\begin{pmatrix}x_1\\x_2\end{pmatrix}=\begin{pmatrix}1\\2\end{pmatrix}$ using only 4 significant digits of precision. Without pivoting, the pivot is $0.0001$: $\text{row}_2 \leftarrow \text{row}_2 - \frac{1}{0.0001}\text{row}_1 = \text{row}_2 - 10{,}000\,\text{row}_1$, giving $(1-10{,}000(0.0001),\; 1-10{,}000(1) \mid 2-10{,}000(1)) = (0,\;-9999\mid-9998)$, rounded to 4 digits: $(0, -9999 \mid -9998)$, giving $x_2 \approx 0.9999$, then $x_1 = (1-0.9999)/0.0001 \approx 1.0$ — actually recoverable here, but with slightly worse-conditioned numbers this same procedure loses several digits of accuracy fast. With partial pivoting, swap rows first so $1$ (the larger entry) becomes the pivot: eliminating with a modest multiplier of $0.0001$ keeps every computed number well-scaled and avoids the huge multiplier entirely, giving a far more numerically robust path to the same exact answer $x_1 \approx 1.0001, x_2 \approx 0.9999$.

What this means in practice

Gaussian elimination with partial pivoting is what actually runs underneath most solve(A, b) calls in numerical libraries — it's the standard, general-purpose method for solving portfolio optimization systems, calibrating models that reduce to linear systems, and any $Ax=b$ problem without special structure that would justify a more specialized method. Pivoting isn't an optional refinement; production-grade linear solvers essentially always pivot, because an un-pivoted implementation can fail silently on inputs that look perfectly reasonable.