A new upper bound for the growth factor in Gaussian elimination with complete pivoting (Q6982278)

Consider the linear system \(Ax=b\) and the classical technique of using Gauss elimination to solve it. The classical idea performs a sequence of rank-one transformations. More precisely, the famous technique produces a sequence of matrices \(A^{(k)}\in\mathbb C^{k\times k}\) for \(1\leq k\leq n\) which satisfy:\N\[\NA^{(k)}=M^{(2,2)}-M^{(2,1)}[M^{(1,1)}]^{-1}M^{(1,2)}.\N\]\NHere,\N\[\NA:= \begin{bmatrix} M^{(1,1)} & M^{(1,2)} \\\NM^{(2,1)} & M^{(2,2)} \end{bmatrix}\N\]\Nwith growth factor\N\[\Ng(A):=\frac{{\max}_k\|A^{(k)}\|_{{\max}}}{\|A\|_{{\max}}}\N\]\Nwhere \(\|\cdot\|\) is the entry-wise matrix infinity norm. In the matrix \(A\), the first column is \(n-k\) and the second \(k\). The first row is \(n-k\) and the second is \(k\).\N\NThe growth factor \(g\) measures how large the entries of an LU factorization can be relative to the entries of the original matrix. The authors establish an upper bound of \(n^{0.2079\ln n+0.91}\) for the growth factor in Gaussian elimination with complete pivoting which is the first improvement upon Wilkinson's original 1961 bound of \(2n^{0.25\ln n+0.5}\).