Recipe

Solve a linear system by Gaussian elimination with partial pivoting

Use when: you're solving a linear system by hand and need the pivot order itself to control round-off growth, not just reach a correct answer

Goal: the numeric value of every unknown, reached by a pivot order that keeps every multiplier no larger than 1 in magnitude

Taught in Partial pivoting and why it's necessary

1. 1

   Stack the system's coefficients and constants into one matrix, exactly as ordinary Gaussian elimination does.

   Example

   For x_1+2x_2-x_3=-3,\ 3x_1-x_2+2x_3=13,\ 2x_1+x_2+4x_3=15: \left[\begin{array}{ccc|c}1&2&-1&-3\\3&-1&2&13\\2&1&4&15\end{array}\right]

   Why: this is the same object ordinary elimination works on -- pivoting only changes the ORDER rows are used in, not the setup.

2. 2

   Compare |a_{kk}|,|a_{k+1,k}|,\dots,|a_{nk}| among rows not yet used as a pivot. Don't just check whether the current entry happens to be nonzero.

   Example

   Column 1's candidates are |1|,|3|,|2| (rows 1, 2, 3) — the largest is 3, in row 2.

   ⚡ Shortcut

   Suppose A is already diagonally dominant: |a_{ii}|>\sum_{j\ne i}|a_{ij}| in every row, so the diagonal entry outweighs the rest of its own row combined. Then the natural, un-swapped pivot order is ALREADY the largest-magnitude order at every stage, and this comparison never actually finds a swap worth making. For A=\begin{bmatrix}10&1&2\\1&8&1\\1&2&9\end{bmatrix}: column 1's candidates are 10,1,1 — already largest in row 1, so no swap. Eliminating with pivot 10 leaves row 2 at 7.9 and row 3 at 1.9 in column 2. Row 2 is still the larger one, so no swap happens there either. This doesn't mean diagonal dominance makes the comparison unnecessary to run — it means the comparison keeps passing on its own, every time, for this specific kind of matrix.

   Why: choosing the largest available pivot, not merely a nonzero one, is what keeps the NEXT step's multipliers small. A pivot that passes an "is it zero?" check can still be dangerously small -- that's Section 1's whole point.

3. 3

   Move the winning row into the current pivot row. Carry its entire row along with it -- every coefficient AND its right-hand-side entry.

   Example

   Swap R_1\leftrightarrow R_2: \left[\begin{array}{ccc|c}3&-1&2&13\\1&2&-1&-3\\2&1&4&15\end{array}\right]

   Why: a row's constant term belongs to that row's own equation. Moving the coefficients without it would pair one equation's left side with a different equation's right side.

4. 4

   Use the replace operation to zero out every entry below the pivot. This is the same move as any Gaussian elimination.

   Example

   m_{21}=\frac{1}{3}, m_{31}=\frac{2}{3}: \left[\begin{array}{ccc|c}3&-1&2&13\\0&\frac{7}{3}&-\frac{5}{3}&-\frac{22}{3}\\0&\frac{5}{3}&\frac{8}{3}&\frac{19}{3}\end{array}\right]

   Why: this step is identical to plain Gaussian elimination. Pivoting only changed which row got used as the pivot, not what elimination does with it.

5. 5

   Partial pivoting isn't a single check performed once at the start. Redo "find the largest available entry" at EVERY column, among only the rows not yet used as a pivot.

   Example

   Column 2's remaining candidates are \left|\frac{7}{3}\right|\approx2.33 and \left|\frac{5}{3}\right|\approx1.67 — row 2 is already the larger one, so no swap happens this time.

   • two candidates tie in magnitude — either may be chosen; the final answer comes out the same either way.
   • every remaining candidate in a column is (numerically) zero — the matrix is singular from this point on; elimination cannot continue.

   Why: a pivot chosen once at column 1 says nothing about column 2. Each column's own multipliers depend only on THAT column's pivot, so each one needs its own comparison.

6. 6

   Solve from the bottom row up, exactly as ordinary Gaussian elimination finishes.

   Example

   \frac{27}{7}x_3=\frac{81}{7}\Rightarrow x_3=3; then x_2=-1; then x_1=2.

   Why: reaching row echelon form is the whole point of every step above. Back-substitution recovers the unknowns from it exactly as it always does.