Past exam of the mathematics course of the University of Cambridge / 2006 / ib / Paper 1 / 6D / b / Solution

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.