arxiv: 2604.23024 · v1 · submitted 2026-04-24 · 🧮 math.NA · cs.NA

Recognition: unknown

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

Teng Zhang

Authors on Pith no claims yet

Pith reviewed 2026-05-08 10:18 UTC · model grok-4.3

classification 🧮 math.NA cs.NA

keywords Higham matricesgrowth factorGaussian eliminationcondition numberSchur complementaccretive-dissipative matricesnumerical stabilitycomplex symmetric matrices

0 comments

The pith

Higham matrices have growth factors bounded sharply above and below in terms of their condition numbers.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes sharp condition-number-dependent lower and upper bounds on the growth factor of Higham matrices during Gaussian elimination without pivoting. This refines Drury's 2013 result that the factor is at most 2 by making the bound depend explicitly on the matrix and proving it is strictly less than 2. A sympathetic reader would care because the bounds quantify how matrix conditioning controls the risk of numerical instability in this setting. The work also derives analogous sharp estimates for the wider class of accretive-dissipative matrices and an improved entrywise growth bound.

Core claim

For a Higham matrix A = B + iC with B and C real symmetric positive definite, the growth factor ρ_n(A) satisfies sharp lower and upper bounds that depend on the condition number of A. This furnishes a quantitative refinement of the uniform upper bound of 2. The derivation rests on a sharp scalar Schur-complement inequality obtained through a two-dimensional domination argument. Corresponding sharp scalar and diagonal estimates are obtained for accretive-dissipative matrices together with an improved entrywise growth bound for that class.

What carries the argument

The sharp scalar Schur-complement inequality proved via a two-dimensional domination argument.

If this is right

The growth factor satisfies the strict inequality ρ_n(A) < 2 with the gap controlled by the condition number.
Sharp scalar and diagonal estimates hold for the broader class of accretive-dissipative matrices.
An improved entrywise growth bound applies to accretive-dissipative matrices.
These results give a more precise tool for assessing stability of Gaussian elimination without pivoting on these matrix families.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The condition-number dependence suggests that well-conditioned Higham matrices should exhibit growth factors noticeably below 2, a prediction that can be checked by direct computation for modest dimensions.
The two-dimensional domination technique used for the Schur inequality may apply to related dominance arguments in matrix analysis.
Tighter bounds could inform the choice of when pivoting is necessary for complex symmetric positive definite systems.

Load-bearing premise

The matrices must satisfy the Higham property and the two-dimensional domination must hold in the scalar Schur-complement inequality.

What would settle it

A concrete Higham matrix whose computed growth factor lies outside the derived condition-number-dependent bounds, or a sequence of Higham matrices with growing condition numbers whose growth factors fail to approach the stated upper limit.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper turns Drury's non-quantitative bound of at most 2 into explicit lower and upper bounds on growth factors that depend on the condition number, using a new scalar inequality.

read the letter

The main takeaway is that the authors refine Drury's 2013 result for Higham matrices by producing sharp bounds on the growth factor that depend on cond(A), along with a strict inequality whose constant depends on the matrix itself. They do this through a scalar Schur-complement inequality derived via two-dimensional domination, and they extend the approach to accretive-dissipative matrices with an improved entrywise bound as well. That condition-number dependence and the explicit constant are the concrete advances over the earlier non-quantitative work. The derivation is presented as independent and not circular. The two-dimensional domination step is the central new tool, and if it holds as stated it gives a clean way to make the bound quantitative without extra assumptions beyond the Higham property. The paper stays focused on the math and does not overreach into broader claims about general matrices. The soft spot is exactly the domination argument flagged in the stress test. It is load-bearing for both the strict inequality and the sharpness, and any looseness there (for example if it implicitly needs angle restrictions or fails to stay tight for large n) would make the constants less general than advertised. A referee would need to check that step line by line, since the abstract only outlines the strategy. No other gaps like fitted parameters or self-referential definitions show up. This work is for numerical linear algebra specialists who care about growth-factor bounds in Gaussian elimination without pivoting. A reader already familiar with Drury's result or Higham matrices will see immediate value in the explicit forms. It is worth sending to peer review so the domination technique and the resulting constants can be verified in detail.

Referee Report

2 major / 2 minor

Summary. The paper claims to establish sharp condition-number-dependent lower and upper bounds on the growth factor ρ_n(A) for Higham matrices A = B + iC (B, C real symmetric positive definite), providing a quantitative refinement of Drury's ρ_n(A) ≤ 2 result. The central ingredient is a sharp scalar Schur-complement inequality derived via a two-dimensional domination argument; the work also gives corresponding estimates for accretive-dissipative matrices and an improved entrywise growth bound.

Significance. If the two-dimensional domination step is valid and produces bounds that depend only on cond(A) without hidden parameters, the result supplies a concrete quantitative improvement to the stability theory of Gaussian elimination without pivoting for this class of complex matrices. The explicit dependence on the condition number would allow sharper a priori estimates than the uniform bound of 2.

major comments (2)

[Proof of the main scalar inequality (Section 3 or equivalent)] The two-dimensional domination argument for the scalar Schur-complement inequality (identified in the abstract as the main ingredient) is load-bearing for both the strict inequality ρ_n(A) < 2 and the claimed dependence solely on cond(A). The manuscript must verify that the resulting constants are independent of any implicit angle or entrywise constraints between the positive-definite parts B and C; otherwise the bounds may not be sharp or condition-number-only for general n.
[Derivation of condition-number bounds (following the Schur-complement inequality)] The transition from the matrix-dependent constant 1 + δ_A² (obtained by refining Drury's sectorial determinant method) to explicit bounds in terms of cond(A) requires an explicit majorization or estimate showing how δ_A is controlled by the condition number; this step is not visible from the abstract and is essential for the quantitative refinement claim.

minor comments (2)

[Introduction] Clarify the precise definition of the growth factor ρ_n(A) at the outset (e.g., whether it is the standard max |a_ij^(k)| / max |a_ij| over elimination stages) to avoid any ambiguity with related quantities in the literature.
[Abstract / final section] The abstract mentions 'corresponding sharp scalar and diagonal estimates for accretive-dissipative matrices'; a brief comparison table or statement of how these differ from the Higham case would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. The points raised help us strengthen the presentation of the two-dimensional domination argument and the explicit condition-number estimates. We have revised the paper accordingly and respond to each major comment below.

read point-by-point responses

Referee: [Proof of the main scalar inequality (Section 3 or equivalent)] The two-dimensional domination argument for the scalar Schur-complement inequality (identified in the abstract as the main ingredient) is load-bearing for both the strict inequality ρ_n(A) < 2 and the claimed dependence solely on cond(A). The manuscript must verify that the resulting constants are independent of any implicit angle or entrywise constraints between the positive-definite parts B and C; otherwise the bounds may not be sharp or condition-number-only for general n.

Authors: We thank the referee for emphasizing this key requirement. In the proof of the scalar Schur-complement inequality (Theorem 3.1), the two-dimensional domination is applied directly to the quadratic forms induced by the positive-definite matrices B and C on a two-dimensional subspace. No angle between B and C or entrywise constraints are assumed or used; the argument relies solely on the positive-definiteness to dominate the relevant expressions. The resulting constants are therefore uniform and depend only on eigenvalue ratios that are later controlled by cond(A). We have inserted a new remark immediately after the proof of Theorem 3.1 that explicitly states this independence and confirms the bounds hold for arbitrary Higham matrices of any order n. revision: yes
Referee: [Derivation of condition-number bounds (following the Schur-complement inequality)] The transition from the matrix-dependent constant 1 + δ_A² (obtained by refining Drury's sectorial determinant method) to explicit bounds in terms of cond(A) requires an explicit majorization or estimate showing how δ_A is controlled by the condition number; this step is not visible from the abstract and is essential for the quantitative refinement claim.

Authors: We agree that the passage from the matrix-dependent bound 1 + δ_A² to a condition-number-only expression must be fully explicit. After refining Drury's sectorial determinant method to obtain the strict inequality ρ_n(A) < 1 + δ_A², we bound δ_A by relating it to the numerical range of the scaled matrix A. Because B and C are positive definite, the deviation parameter satisfies δ_A ≤ (κ(A) − 1)/(κ(A) + 1), where κ(A) is the condition number. This majorization follows from the eigenvalue bounds on the Hermitian parts and is independent of other matrix features. We have expanded the relevant derivation (now in Section 4) with the complete estimate, including the short proof that δ_A is controlled solely by κ(A), thereby making the quantitative refinement transparent. revision: yes

Circularity Check

0 steps flagged

No circularity: bounds derived from independent 2D domination argument for Schur inequality

full rationale

The paper's central derivation establishes condition-number-dependent bounds on the growth factor ρ_n(A) for Higham matrices by proving a sharp scalar Schur-complement inequality via a two-dimensional domination argument. This step is presented as a self-contained mathematical construction that does not reduce to the target growth-factor result by definition, fitting, or self-citation. Drury's 2013 result (ρ_n(A) ≤ 2) is cited as an external upper bound that is then refined quantitatively; the refinement does not presuppose the new bounds. No self-definitional loops, fitted inputs renamed as predictions, or load-bearing self-citations appear in the derivation chain. The argument remains independent of the final explicit constants and applies for general n under the stated Higham property.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard definition of Higham matrices and the new Schur-complement inequality proved inside the paper; no free parameters or invented entities are introduced.

axioms (2)

domain assumption B and C are real symmetric positive definite matrices
Definition of Higham matrix invoked throughout the abstract.
standard math Standard properties of Schur complements and determinants for positive definite matrices
Background linear-algebra facts used to derive the growth-factor bounds.

pith-pipeline@v0.9.0 · 5514 in / 1262 out tokens · 39049 ms · 2026-05-08T10:18:30.030944+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 12 canonical work pages

[1]

S. W. Drury,Fischer determinantal inequalities and Higham’s conjecture, Linear Algebra Appl.439(2013), no. 10, 3129–3133, doi:10.1016/j.laa.2013.08.031

work page doi:10.1016/j.laa.2013.08.031 2013
[2]

George and Kh

A. George and Kh. D. Ikramov,On the growth factor in Gaussian elimination for matrices with sharp angular field of values, Calcolo41(2004), no. 1, 27–36, doi:10.1007/s10092-004-0082-9

work page doi:10.1007/s10092-004-0082-9 2004
[3]

George and Kh

A. George and Kh. D. Ikramov,On the properties of accretive-dissipative matrices, Math. Notes77(2005), 767–776, doi:10.1007/s11006-005-0077-0

work page doi:10.1007/s11006-005-0077-0 2005
[4]

George, Kh

A. George, Kh. D. Ikramov, and A. B. Kucherov,On the growth factor in Gaussian elimination for generalized Higham matrices, Numer. Linear Algebra Appl.9(2002), no. 2, 107–114, doi:10.1002/nla.258

work page doi:10.1002/nla.258 2002
[5]

Guo, X.-M

Q.-P. Guo, X.-M. Gu, and H.-B. Li,A note on the growth factor in Gaussian elimination for Higham matrices, Math. Comp., published electronically 1 April 2026, doi:10.1090/mcom/4202. Earlier versions: arXiv:1305.5211v1 [math.NA], 2013, and arXiv:1305.5211v2 [math.NA], 2025, doi:10.48550/arXiv.1305.5211

work page doi:10.1090/mcom/4202 2026
[6]

N. J. Higham,Factorizing complex symmetric matrices with positive definite real and imaginary parts, Math. Comp.67(1998), no. 224, 1591–1599, doi:10.1090/S0025-5718-98-00978-8

work page doi:10.1090/s0025-5718-98-00978-8 1998
[7]

N. J. Higham,Accuracy and Stability of Numerical Algorithms, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002, doi:10.1137/1.9780898718027

work page doi:10.1137/1.9780898718027 2002
[8]

Kh. D. Ikramov,Determinantal inequalities for accretive-dissipative matrices, J. Math. Sci. (N.Y.)121 (2004), no. 4, 2458–2464, doi:10.1023/B:JOTH.0000026283.92486.1c

work page doi:10.1023/b:joth.0000026283.92486.1c 2004
[9]

Kh. D. Ikramov and A. B. Kucherov,Bounding the growth factor in Gaussian elimination for Buckley’s class of complex symmetric matrices, Numer. Linear Algebra Appl.7(2000), no. 5, 269–274, doi:10.1002/1099- 1506(200007/08)7:5<269::AID-NLA197>3.0.CO;2-8

work page doi:10.1002/1099- 2000
[10]

Lin,A note on the growth factor in Gaussian elimination for accretive-dissipative matrices, Calcolo51 (2014), no

M. Lin,A note on the growth factor in Gaussian elimination for accretive-dissipative matrices, Calcolo51 (2014), no. 3, 363–366, doi:10.1007/s10092-013-0089-1

work page doi:10.1007/s10092-013-0089-1 2014
[11]

Xue and X

J. Xue and X. Hu,On Fischer-type determinantal inequalities for accretive-dissipative matrices, J. Inequal. Appl.2015(2015), Paper No. 194, 5 pp., doi:10.1186/s13660-015-0721-5

work page doi:10.1186/s13660-015-0721-5 2015
[12]

Yang,A refinement on the growth factor in Gaussian elimination for accretive-dissipative matrices, Ital

J. Yang,A refinement on the growth factor in Gaussian elimination for accretive-dissipative matrices, Ital. J. Pure Appl. Math.33(2014), 273–278.https://ijpam.uniud.it/online_issue/201433/23-Yang.pdf

2014
[13]

Zhang,Equivalence of the Wielandt inequality and the Kantorovich inequality, Linear Multilinear Algebra 48(2001), no

F. Zhang,Equivalence of the Wielandt inequality and the Kantorovich inequality, Linear Multilinear Algebra 48(2001), no. 3, 275–279, doi:10.1080/03081080108818673

work page doi:10.1080/03081080108818673 2001
[14]

Zhang,A Matrix Decomposition and Its Applications, presentation at WONRA, Sanya, China, July 28–August 1, 2014

F. Zhang,A Matrix Decomposition and Its Applications, presentation at WONRA, Sanya, China, July 28–August 1, 2014. Available at:https://cklixx.people.wm.edu/wonra14/Zhang.pdf. AppendixA.Drury’s determinant proof of Higham’s conjecture This appendix records the determinant route due to Drury [1]. It is independent of the direct proof above and is included ...

2014