Proof that partial pivoting algorithm works for all invertible matrices

Question

I am trying to prove this statement above. I know that the partial pivoting algorithm will fail if there is a column such that the diagonal and all the elements below the diagonal are 0. How can I show that this situation doesn’t occur if the matrix is invertible? I can’t think of a rigorous way to show this.... Thanks!

Answer 1

When performing Gaussian elimination with partial pivoting you gradually transform the matrix $A$ to upper triangular form through a sequence of elementary row operations. Let $A^{(k)}$ denote the matrix obtained after clearing the first $k$ columns, i.e.,$$A^{(k)} = \begin{bmatrix} A_{11}^{(k)} & A_{12}^{(k)} \\ 0 & A_{22}^{(k)} \end{bmatrix},$$ where $A_{11}^{(k)}$ is a $k$ by $k$ (upper triangular) matrix and the trailing submatrix $A_{22}^{(k)}$ has dimension $n-k$. The operations used to produce $A^{(k)}$ are all invertible transformations. Hence, $A^{(k)}$ is nonsingular if and only if $A$ is nonsingular. Since $A^{(k)}$ is block triangular, we have $$\text{det}(A^{(k)}) = \text{det}(A_{11}^{(k)})\text{det}(A_{22}^{(k)}).$$ It follows, that the trailing submatrix $A_{22}^{(k)}$ is nonsingular. In particular, its leading column can not be the zero vector.

EDIT: When performing Gaussian elimination with partial pivoting we perform a sequences of elementary row operations. There are three types of elementary row operations:

1. Row scalings, which is especially useful for humans who seek to produce nice intermediate results.
2. Row permutations, which are always needed to move pivots to the top row of the current submatrix.
3. Adding a multiple of one row to another in order to nullify an entry in the leading column of the current submatrix.

These operations all correspond to invertible linear transformations. For the sake of simplicity, I will present examples which correspond to $n=3$. Scaling row 1 with a nonzero scalar $\alpha$ is accomplished by left multiplication with the matrix $$E_{r_1 \gets \alpha r_1} = \begin{bmatrix} \alpha & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}.$$ Swapping rows $2$ and $3$ is accomplished by left multiplication with the matrix $$E_{r_2 \leftrightarrow r_3}= \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}.$$ Finally adding $\alpha$ times row $2$ to row $3$ is accomplished by left multiplication with the matrix $$ E_{r_3 \gets r_3 + \alpha r_2} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & \alpha & 1 \end{bmatrix}.$$ It is important to notice that this operation (obviously) preserves row $2$.

Each type of elementary row operation is invertible. Scaling a row with $\alpha \not = 0$ is undone by scaling the same row with $\alpha^{-1}$. Swapping a pair of rows is undone by swapping the same rows again. Adding $\alpha$ times row $i$ to row $j$ is undone by adding $-\alpha$ times row $i$ to row $j$.

Processing the first column of matrix typically involves swapping two rows to move the pivotal row to the top and then nullifying elements below the pivot. In terms of matrices we start with $A^{(0)} = A$ and produce the matrix $A^{(1)}$ given by $$ A^{(1)} = E_n E_{n-1} E_{n-2} \dots E_2 E_1 A^{(0)}.$$ Here $E_1$ is a permutation matrix which represents the row swap, while matrix $E_j$ represent the elementary row operation which nullifies entry $(j,1)$.