07 - Stability of Gaussian Elimination with Partial Pivoting

Stability of Gaussian Elimination with Partial Pivoting

Gaussian Elimination with partial pivoting cannot fail if $A$ is non-singular

Proof

Let $A$ be at the $j$-th stage so

$$A=\left[\begin{array}{cccccccc}{a}_{11}& .& a_{1,j-1}& a_{1j}& .& .& .& a_{1n}\\ 0& .& .& .& .& .& .& .\\ 0& .& a_{j-1,j-1}& a_{j-1,j}& .& .& .& a_{j-1,n}\\ 0& .& 0& a_{jj}& .& .& .& a_{jn}\\ 0& .& 0& .& .& .& .& .\\ 0& .& 0& a_{kj}& .& .& .& a_{kn}\\ 0& .& 0& .& .& .& .& .\\ 0& .& 0& a_{nj}& .& .& .& a_{nm}\end{array}\right]$$

Then

$$\det A=a_{11}{a}_{22}\cdots a_{j-1,j-1}\cdot \det \left[\begin{array}{ccccc}{a}_{jj}& .& .& .& a_{jn}\\ .& .& .& .& .\\ a_{kj}& .& .& .& a_{kn}\\ .& .& .& & .\\ a_{nj}& .& .& .& a_m\end{array}\right]$$

Hence $\det A=0$ if and only if $a_{jj}=\cdots =a_{kj}=\cdots =a_{nj}=0$

Hence pivot $a_{k,j}$ is zero so $A$ is singular
If $A$ is non-singular then all pivots are non-zero