= 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 form
$$
\begin{pmatrix}p&r\\0&B\end{pmatrix},\qquad p\ne0.
$$
Elementary elimination and row <permutations> preserve nonsingularity, so $p\det B\ne0$ 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. \b[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.
Back to article page
