Sharp condition-number bounds for growth factors of Higham matrices in Gaussian elimination
Provides a quantitative refinement of a known theoretical bound for the stability of Gaussian elimination for a specific class of matrices, which is an incremental advance in numerical linear algebra.
This paper establishes sharp condition-number-dependent bounds for the growth factors of Higham matrices in Gaussian elimination, refining Drury's result that the growth factor is less than 2. The bounds are proven via a sharp scalar Schur-complement inequality.
Higham's conjecture on the growth factor of complex symmetric positive definite matrices is a longstanding problem in the stability theory of Gaussian elimination without pivoting. It asserts that every complex matrix $A=B+iC$ with $B$ and $C$ real symmetric positive definite, is called Higham matrix and has growth factor $ρ_n(A)<2$. In 2013, Drury [Linear Algebra Appl. \textbf{439} (2013), no.~10, 3129--3133] proved that $ρ_n(A)\le 2$. In fact, we will see his sectorial determinant method can be refined to give the strict bound $ρ_n(A)<2$ for each fixed Higham matrix; however, the resulting constant $1+δ_A^2$ depends on the matrix $A$. In this paper, we establish sharp condition-number-dependent lower and upper bounds for the growth factors of Higham matrices, thereby providing a quantitative refinement of Drury's result. The main ingredient is a sharp scalar Schur-complement inequality, proved via a two-dimensional domination.We also obtain corresponding sharp scalar and diagonal estimates for accretive-dissipative matrices, and an improved entrywise growth bound for that broader class.