Why Pivot Choices Matter
Gaussian elimination can produce entries much larger than those in the starting matrix. Such intermediate growth matters in computation: when arithmetic is performed with finite precision, rounding errors can be affected by the sizes of the intermediate quantities. A small pivot is one source of risk. Dividing entries below it by that pivot can create large multipliers, which can then produce large entries in the updated matrix.
Partial pivoting addresses this issue locally. At each elimination step, it chooses as pivot an entry of largest absolute value in the current column among the rows not yet eliminated. This choice ensures that the multipliers used at that step have absolute value at most \(1\). It does not guarantee that all intermediate entries will remain small, so a useful measure must record entries from every stage, not just the final factor.
Consider an \(n\times n\) matrix \(\mathbf{A}\). At stage \(k\), after \(k\) pivots have been used, the active submatrix consists of the entries in rows and columns \(k+1,\dots,n\). Row interchanges made during pivoting are included in the current arrangement of rows. Stage \(0\) is the original matrix. We assume the elimination process can continue through its required pivots; if the active pivot column is zero, elimination breaks down at that stage.
The maximum over stages is essential. Entries in an active submatrix are updated as elimination proceeds; an entry can be large at one stage and later be reduced or eliminated. The final upper triangular matrix \(\mathbf{U}\) records the pivot rows produced along the way, but its largest entry need not equal the largest intermediate entry. The definition above includes the entries that later change.
Partial Pivoting Controls the Multipliers
At stage \(k\), suppose the active pivot column has a nonzero entry. Partial pivoting interchanges rows, if necessary, so that the pivot \(a_{kk}^{(k)}\) has the largest absolute value among the entries \(a_{ik}^{(k)}\) with \(i\ge k\). To eliminate the entry in row \(i>k\), the multiplier is \(m_{ik}=a_{ik}^{(k)}/a_{kk}^{(k)}\). The update to an entry in column \(j>k\) is \(a_{ij}^{(k+1)}=a_{ij}^{(k)}-m_{ik}a_{kj}^{(k)}\).
Proof. By the rule for partial pivoting, \(|a_{kk}^{(k)}|\) is the largest absolute value among the entries in the active part of column \(k\). Therefore, for each \(i>k\), \(|a_{ik}^{(k)}|\le |a_{kk}^{(k)}|\). Since the selected pivot is nonzero, division by its absolute value is valid, and \(|m_{ik}|=|a_{ik}^{(k)}|/|a_{kk}^{(k)}|\le 1\). \(\square\)
This result concerns the multipliers at each step; it is not a claim that the growth factor must be \(1\). Indeed, the update formula shows why large entries can still occur: even when \(|m_{ik}|\le1\), subtracting \(m_{ik}a_{kj}^{(k)}\) can increase the magnitude of an entry. Partial pivoting is a practical safeguard against very large multipliers, not a guarantee that every later entry will be small.
A Small Pivot Can Create Large Growth
Worked Example: No Pivoting Versus Partial Pivoting
Compare the growth factors for \(\mathbf{A}=\begin{bmatrix}\tfrac{1}{100}&1\\1&1\end{bmatrix}\) with no pivoting and with partial pivoting.
First use no pivoting. The first pivot is \(1/100\), so the multiplier for row 2 is \(1/(1/100)=100\). Subtracting \(100\) times row 1 from row 2 gives
The largest entry in the original matrix has magnitude \(1\), and the new active entry \(-99\) has magnitude \(99\). No later stage changes this value, so \(\rho(\mathbf{A})=99\). The associated factors are \(\mathbf{L}=\begin{bmatrix}1&0\\100&1\end{bmatrix}\) and \(\mathbf{U}=\begin{bmatrix}\tfrac{1}{100}&1\\0&-99\end{bmatrix}\).
Check: Multiplying the factors gives \(\mathbf{L}\mathbf{U}= \begin{bmatrix}\tfrac{1}{100}&1\\ 100(\tfrac{1}{100})&100+(-99)\end{bmatrix} = \begin{bmatrix}\tfrac{1}{100}&1\\1&1\end{bmatrix} =\mathbf{A}\).
With partial pivoting, the larger entry in the first column is \(1\), so interchange the two rows. The permutation matrix and permuted matrix are \(\mathbf{P}=\begin{bmatrix}0&1\\1&0\end{bmatrix}\) and \(\mathbf{P}\mathbf{A}=\begin{bmatrix}1&1\\\tfrac{1}{100}&1\end{bmatrix}\). The multiplier is now \(1/100\), and the update gives
Every entry in the active matrices has magnitude at most \(1\), and the original matrix already contains entries of magnitude \(1\). Thus the growth factor with partial pivoting is \(1\). Here \(\mathbf{L}=\begin{bmatrix}1&0\\\tfrac{1}{100}&1\end{bmatrix}\) and \(\mathbf{U}=\begin{bmatrix}1&1\\0&\tfrac{99}{100}\end{bmatrix}\).
Check: \(\mathbf{L}\mathbf{U}= \begin{bmatrix}1&1\\\tfrac{1}{100}&\tfrac{1}{100}+\tfrac{99}{100}\end{bmatrix} = \begin{bmatrix}1&1\\\tfrac{1}{100}&1\end{bmatrix} =\mathbf{P}\mathbf{A}\).
The difference is not that the original systems are different; a row interchange simply changes the order of the equations. The difference is that the first pivot is \(1/100\) without pivoting and \(1\) with partial pivoting. Dividing by the small pivot creates a multiplier of \(100\), and that multiplier turns the second diagonal entry into \(-99\).
A Formula for a Two-by-Two Family
The preceding example illustrates a whole family of matrices. For \(0<\delta<1/2\), consider \(\mathbf{A}_{\delta}=\begin{bmatrix}\delta&1\\1&1\end{bmatrix}\). The next result calculates both growth factors exactly and explains why the choice of pivot matters relative to the other entries in its column.
Proof. The largest magnitude in the original matrix is \(1\). Without pivoting, the first pivot is \(\delta\), and the multiplier is \(1/\delta\). The only new active entry is \(1-(1/\delta)\cdot1=1-1/\delta=-(1-\delta)/\delta\). Since \(\delta<1/2\), \((1-\delta)/\delta>1\). The maximum over the original and updated active matrices is therefore \((1-\delta)/\delta\), so this is the growth factor. With partial pivoting, interchange the two rows. The first pivot is \(1\), the multiplier is \(\delta\), and the new active entry is \(1-\delta\), which satisfies \(0<1-\delta<1\). The original maximum remains \(1\), and no active entry exceeds it. The growth factor is \(1\). \(\square\)
For example, setting \(\delta=1/100\) gives \((1-\delta)/\delta=99\), as in the worked example. The proposition also shows that a pivot should not be judged by its absolute size alone: the matrix could be rescaled, changing all absolute entries. Partial pivoting compares candidate entries within the current pivot column.
Intermediate Growth May Disappear from the Final Factor
Worked Example: An Entry That Later Shrinks
For \(\mathbf{B}=\begin{bmatrix}1&-1&0\\0&1&0\\1&1&1\end{bmatrix}\), perform elimination without pivoting and compare the largest intermediate entry with the largest entry of the final \(\mathbf{U}\).
The initial maximum magnitude is \(1\). At the first step, the multiplier for row 3 is \(1\). Subtract row 1 from row 3:
The active matrix now contains an entry of magnitude \(2\). At the second step, the pivot is \(1\) and the multiplier for row 3 is \(2\). Subtract twice row 2 from row 3:
The final upper triangular matrix has largest entry magnitude \(1\), even though an intermediate active matrix had an entry of magnitude \(2\). The growth factor is therefore \(2/1=2\), not \(1\). The lower triangular factor records the multipliers: \(\mathbf{L}=\begin{bmatrix}1&0&0\\0&1&0\\1&2&1\end{bmatrix}\).
Check: \(\mathbf{L}\mathbf{U}= \begin{bmatrix} 1&-1&0\\ 0&1&0\\ 1&2&1 \end{bmatrix} \begin{bmatrix} 1&-1&0\\ 0&1&0\\ 0&0&1 \end{bmatrix} = \begin{bmatrix} 1&-1&0\\ 0&1&0\\ 1&-1+2&1 \end{bmatrix} =\mathbf{B}\).
This example makes the purpose of the stage-by-stage maximum concrete. The entry \(2\) is updated at the next step and becomes \(0\), so it is absent from \(\mathbf{U}\). Measuring only \(\mathbf{U}\) would miss the largest value used during elimination.
Partial Pivoting in a Three-by-Three Example
Worked Example: Pivot Choices and Multipliers
Apply partial pivoting to \(\mathbf{C}=\begin{bmatrix}2&1&0\\4&5&1\\1&2&3\end{bmatrix}\), and compute its growth factor and factorization.
The first-column magnitudes are \(2,4,1\), so interchange rows 1 and 2. The first pivot is \(4\). The multipliers for the next two rows are \(2/4=1/2\) and \(1/4\). The updated rows are \((2,1,0)-\tfrac12(4,5,1)=(0,-\tfrac32,-\tfrac12)\) and \((1,2,3)-\tfrac14(4,5,1)=(0,\tfrac34,\tfrac{11}{4})\). Thus the active matrix after the first elimination step is
In the second active column, \(\tfrac32>\tfrac34\), so no row interchange is needed. The multiplier is \((3/4)/(-3/2)=-1/2\). Updating row 3 gives \((0,\tfrac34,\tfrac{11}{4})-(-\tfrac12)(0,-\tfrac32,-\tfrac12) =(0,0,\tfrac52)\). Therefore \(\mathbf{U}=\begin{bmatrix}4&5&1\\0&-\tfrac32&-\tfrac12\\0&0&\tfrac52\end{bmatrix}\). The largest magnitude in the original matrix is \(5\); no entry in the later active matrices exceeds \(5\). Hence the growth factor is \(5/5=1\).
The row order in \(\mathbf{P}\mathbf{C}\) is original rows 2, 1, 3. The multipliers give \(\mathbf{L}=\begin{bmatrix}1&0&0\\\tfrac12&1&0\\\tfrac14&-\tfrac12&1\end{bmatrix}\). Thus
Check: The second row of \(\mathbf{L}\mathbf{U}\) is \(\tfrac12(4,5,1)+(0,-\tfrac32,-\tfrac12)=(2,1,0)\). The third row is \(\tfrac14(4,5,1)-\tfrac12(0,-\tfrac32,-\tfrac12)+(0,0,\tfrac52) =(1,\tfrac54,\tfrac14)+(0,\tfrac34,\tfrac14)+(0,0,\tfrac52) =(1,2,3)\). The first row is \((4,5,1)\). This verifies \(\mathbf{P}\mathbf{C}=\mathbf{L}\mathbf{U}\).
Common Mistakes and Practical Interpretation
Mistake: measuring growth from \(\mathbf{U}\) alone. In the previous example, a calculation that takes the largest entry of the final \(\mathbf{U}\) reports \(1\), and dividing by the original maximum \(1\) incorrectly gives growth \(1\). The correction is to inspect every active stage: the intermediate matrix contains the entry \(2\), so the growth factor is \(2\). This is why the numerator in the definition ranges over all stages.
Mistake: choosing a pivot just because it is nonzero. In the \(2\times2\) example, the pivot \(1/100\) is nonzero, so exact elimination is possible. But the resulting multiplier is \(100\), whereas partial pivoting uses the pivot \(1\) and multiplier \(1/100\). In computations with finite precision, exact nonzero pivots are not all equally safe choices. Partial pivoting is a simple rule for avoiding large multipliers caused by choosing a much smaller entry when a larger one is available in the same active column.
Keep the roles of the quantities distinct. A pivot is the diagonal entry used at a step; a multiplier is the quotient used to eliminate an entry beneath it; the growth factor measures the largest magnitude in any active stage relative to the largest magnitude in the original matrix. Partial pivoting bounds the multipliers by \(1\), but it does not, by that fact alone, prove that the growth factor is always small. The practical lesson is narrower and useful: compare pivot candidates in the active column, and assess growth using the entire elimination process rather than only its endpoint.
Check Your Understanding
Use the definition of growth factor and the elimination updates to answer these questions.
- For \(\begin{bmatrix}\tfrac{1}{10}&1\\1&1\end{bmatrix}\), what multiplier occurs without pivoting, and what is the resulting second pivot?
- Why does partial pivoting give \(|m_{ik}|\le1\) at each stage with a nonzero pivot?
- In the \(3\times3\) intermediate-growth example, why does the largest entry of \(\mathbf{U}\) fail to determine the growth factor?
- For \(0<\delta<1/2\), state the growth factors for \(\begin{bmatrix}\delta&1\\1&1\end{bmatrix}\) with and without partial pivoting.
- Does a multiplier bound of \(1\) prove that every intermediate entry has magnitude no greater than every entry of the original matrix? Explain using the update formula.
