Past exam of the mathematics course of the University of Cambridge / 2006 / ib / Paper 1 / 6D (Numerical Analysis)

Use columnwise partial pivoting: select the largest absolute entry in the current column and interchange rows. In the first column the pivot is $4$, so interchange rows 1 and 2. The multipliers are $1/2$ and $-1/2$, and elimination givesThe second pivot is $5/2$, so interchange the two remaining rows. Their previously stored first-column multipliers must also be interchanged. The final multiplier is $(1/2)/(5/2)=1/5$, giving the LU decompositionThe permutation matrix orders the original rows as $2,3,1$. Multiplication verifies the displayed identity.

If “column pivoting” instead denotes interchanging columns rather than searching within a column, that convention gives $AQ=\tilde{L}\tilde{U}$ withThis second identity uses a different pivot convention; it does not change the row-pivoted answer above.

At the first step of Gaussian elimination, the first column of a nonsingular matrix cannot be zero. Choose a nonzero pivot there using a row interchange and eliminate below it. The resulting matrix has block formElementary elimination and row permutations preserve nonsingularity, so $p\det B\ne 0$ and the trailing matrix $B$ is nonsingular. Its first column again has a nonzero entry. Repeating this argument inductively provides a nonzero pivot at every step and produces an upper-triangular factor. The recorded elimination multipliers, with previous entries permuted when necessary, form the unit lower-triangular factor. Every nonsingular square matrix admits $PA=LU$ under columnwise partial pivoting.

For the column-interchange convention from part (a), use the same induction with a nonzero entry in the first row of each nonsingular trailing matrix. Column interchanges put it in the pivot position, and elimination gives $AQ=LU$. These existence statements are in exact arithmetic; they do not assert that all choices have equally good numerical stability.