Pivoting

Gaussian elimination computes a multiplier $m_{ik} = a_{ik} / a_{kk}$ at every step, where $a_{kk}$ is the diagonal entry used to eliminate the column below it. This diagonal entry is called the pivot. If the pivot is exactly zero, the formula produces a division by zero and the algorithm fails. Pivoting is the strategy of rearranging the matrix before each elimination step to ensure a non-zero (and preferably large) element sits in the pivot position.

---

The Problem: A Zero Pivot

Consider the system below, where $a_{11} = 0$:

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

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

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

In matrix form:

$\begin{bmatrix}0&2&1\\1&-2&2\\2&12&-2\end{bmatrix}\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\end{bmatrix}=\begin{bmatrix}4\\2\\4\end{bmatrix}$

Since $a_{11} = 0$, computing $m_{21} = a_{21}/a_{11}$ would require dividing by zero. We must rearrange the matrix before proceeding. There are two ways to do this.

---

Case 1: Partial Pivoting (Row Swapping)

Partial pivoting fixes a zero pivot by scanning down the current column and swapping the offending row with any row below it that has a non-zero entry in that column position.

Key rule: Swapping two rows simply changes the order of the equations. The variables $x$ stay in exactly the same order, but the right-hand side constants $b$ must be swapped along with their corresponding rows.

Step-by-step

Starting from the augmented matrix:

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

The pivot position $a_{11} = 0$. Looking down column 1, Row 2 has $a_{21} = 1 \ne 0$. Swap Row 1 and Row 2.

Apply $R_1 \leftrightarrow R_2$:

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

The resulting system is:

$\begin{bmatrix}1&-2&2\\0&2&1\\2&12&-2\end{bmatrix}\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\end{bmatrix}=\begin{bmatrix}2\\4\\4\end{bmatrix}$

The new pivot is $a_{11} = 1 \ne 0$. Gaussian elimination can now proceed normally. Notice that the constants vector changed from $\begin{bmatrix}4\\2\\4\end{bmatrix}$ to $\begin{bmatrix}2\\4\\4\end{bmatrix}$ — the swap affected $b$ but left the variable order in $x$ untouched.

Note

In practice, partial pivoting is applied even when the pivot is non-zero but small. A very small pivot amplifies rounding errors when used as a divisor. The standard strategy is to always swap to bring the largest-magnitude element in the current column to the pivot position. This is called scaled partial pivoting.

---

Case 2: Complete Pivoting (Column Swapping)

Complete pivoting fixes a zero pivot by scanning across the current row and swapping the offending column with any column to its right that has a non-zero entry in that row position.

Key rule: Swapping two columns changes the order of the variables. The right-hand side $b$ remains unchanged, but the variable vector $x$ must have its corresponding entries swapped to reflect the new column ordering. At the end of the solve, the variables must be swapped back to report the answer in the original order.

Step-by-step

Starting from the original system:

$\begin{bmatrix}0&2&1\\1&-2&2\\2&12&-2\end{bmatrix}\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\end{bmatrix}=\begin{bmatrix}4\\2\\4\end{bmatrix}$

The pivot position $a_{11} = 0$. Looking across Row 1, Column 2 has $a_{12} = 2 \ne 0$. Swap Column 1 and Column 2 in $A$, and simultaneously swap $x_1$ and $x_2$ in $x$.

Apply $C_1 \leftrightarrow C_2$ to $A$ and $x_1 \leftrightarrow x_2$ to $x$:

$\begin{bmatrix}2&0&1\\-2&1&2\\12&2&-2\end{bmatrix}\begin{bmatrix}x_{2}\\x_{1}\\x_{3}\end{bmatrix}=\begin{bmatrix}4\\2\\4\end{bmatrix}$

The new pivot is $a_{11} = 2 \ne 0$. Gaussian elimination can now proceed.

Important: After completing the elimination and back substitution on this reordered system, the first component of the solution vector will correspond to $x_2$, and the second to $x_1$. The values must be unswapped before stating the final answer.

Caution

Complete pivoting requires searching the entire remaining submatrix (not just one column or one row) to find the largest-magnitude element to use as the pivot. This gives the best numerical stability but requires more bookkeeping. In most practical implementations, partial pivoting is preferred because it provides sufficient stability at much lower overhead.