Every real or complex square matrix admits a PLU factorisation, and the first failed pivot marks the singular boundary

For $n=1$, either $A=[a]$ with $a\mathrm{\ne }0$ or $a=0$. In both cases $I_{1}A=(1)[a]$ is a PLU factorisation, and the zero-pivot case is exactly the singular case.

Assume $n>1$. After an initial row swap, write $PA=\left(\begin{array}{cc}a& r^{\mathsf{T}}\\ c& C\end{array}\right),$ where $\mathrm{\mid }a\mathrm{\mid }$ is maximal in the first column below the swap position. If $a\mathrm{\ne }0$, perform the first elimination step. This produces $\left(\begin{array}{cc}a& r^{\mathsf{T}}\\ 0& S\end{array}\right)$ with multipliers $c\mathrm{/}a$. By the induction hypothesis, the trailing block $S$ has a PLU factorisation. Reassembling the first elimination step and the recursive factorisation gives $P^{\mathrm{\prime }}A=LU$ for suitable $P^{\mathrm{\prime }},L,U$. If $a=0$, then the whole first column is zero, so $PA$ already has the block form $\left(\begin{array}{cc}0& r^{\mathsf{T}}\\ 0& C\end{array}\right)$; by the induction hypothesis $C$ has a PLU factorisation, and adjoining the zero first column yields a PLU factorisation of $PA$, hence of $A$.

If the first failed pivot occurs at stage $k$, then after the previous row swaps and eliminations the active matrix has the form $\left(\begin{array}{cc}\ast & \ast \\ 0& T\end{array}\right),$ where the first column of $T$ is zero. Therefore $T$ is singular because $T{e}_0=0$ for a nonzero standard basis vector $e_0$. The whole active matrix is then singular, hence so are all earlier row permutations and elimination preimages, including $A$.

Claim 1 is steps 1.1-1.2. Step 2.1 proves claim 2, and its contrapositive is the final sentence: an invertible matrix cannot reach a zero pivot under partial pivoting.