Sharp condition-number bounds for growth factors of Higham matrices in Gaussian elimination

Abstract

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 ${\rho }_n(A)<2$. In 2013, Drury [Linear Algebra Appl. \textbf{439} (2013), no.~10, 3129--3133] proved that ${\rho }_n(A)\le 2$. In fact, we will see his sectorial determinant method can be refined to give the strict bound ${\rho }_n(A)<2$ for each fixed Higham matrix; however, the resulting constant $1+{\delta }_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.

19 pages. All comments are welcome!