Submatrices with the best-bounded inverses: an asymptotically tight upper bound for $\mathbb{C}^{n \times 2}$

Yuri Nesterenko

arxiv: 2604.24087 · v1 · submitted 2026-04-27 · 🧮 math.NA · cs.NA

Submatrices with the best-bounded inverses: an asymptotically tight upper bound for mathbb{C}^(n times 2)

Yuri Nesterenko This is my paper

Pith reviewed 2026-05-08 02:14 UTC · model grok-4.3

classification 🧮 math.NA cs.NA

keywords submatrix selectionbounded inverseorthonormal columnsspectral normcomplex matricesasymptotically tight boundnumerical linear algebra

0 comments

The pith

Any complex n by 2 matrix with orthonormal columns has a 2 by 2 submatrix whose inverse has spectral norm bounded by a constant independent of n.

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

The paper proves that for any complex matrix with n rows and exactly two orthonormal columns, there always exists a choice of two rows such that the resulting 2 by 2 submatrix has an inverse whose spectral norm is bounded above by a fixed constant that does not depend on n. This bound is shown to be asymptotically tight, meaning it cannot be replaced by a substantially smaller number for large n. A sympathetic reader cares because the result guarantees the existence of a small, stably invertible submatrix inside arbitrarily tall thin data matrices, which supports reliable numerical computations such as row selection or preconditioning without the conditioning deteriorating as height grows. The work completes the complex case of a 1997 hypothesis after the real case was settled recently.

Core claim

The authors establish that for an arbitrary complex n by 2 matrix A whose columns are orthonormal, the quantity min over all pairs of rows of the spectral norm of the inverse of the corresponding 2 by 2 submatrix is bounded above by a constant depending only on the number of columns and not on n, and that this upper bound is asymptotically tight.

What carries the argument

The best-bounded inverse 2 by 2 submatrix, defined as the submatrix formed by selecting the two rows that minimize the spectral norm of its inverse.

Load-bearing premise

The two columns must be exactly orthonormal and the bound concerns only the spectral norm of the inverse.

What would settle it

A counterexample would be an explicit family of complex n by 2 matrices with orthonormal columns, for arbitrarily large n, in which every possible 2 by 2 submatrix has an inverse whose spectral norm exceeds the stated upper bound.

read the original abstract

The long-standing hypothesis formulated by Goreinov, Tyrtyshnikov and Zamarashkin \cite{GTZ1997} has recently been solved affirmatively in the case of real two-column matrices by Sengupta and Pautov \cite{SP2026}. In this paper, we consider the complex variant of this problem and prove the asymptotically tight upper bound for spectral norms of the best-bounded inverse $2 \times 2$ submatrices of an arbitrary complex $n \times 2$ matrix with orthonormal columns.

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 closes the complex case of the GTZ hypothesis with an asymptotically tight bound on the best 2x2 submatrix inverse for orthonormal n-by-2 matrices.

read the letter

The key result is a proof that the complex version of the 1997 Goreinov-Tyrtyshnikov-Zamarashkin question has the same asymptotic bound as the real case solved last year. Nesterenko reduces the problem to a trigonometric optimization over phases on the Grassmannian, applies Jensen-style inequalities to control the complex arguments, and then exhibits a matching lower bound with a deterministic phased construction that looks like a Vandermonde pair. The steps stay elementary and avoid any circular definitions or fitted parameters. The extension from the real proof is non-trivial but handled directly without extra assumptions on the field or the norm. The only real limitation is the restriction to exactly two columns and the spectral norm, which is exactly the setting of the original hypothesis, so it is not a flaw. The argument appears self-contained and the matching lower bound gives the asymptotic tightness that was claimed. This is the sort of paper that people in numerical linear algebra who care about submatrix selection or volume-based pivoting will want to read. It is a clean, self-contained resolution rather than a broad new framework, but the explicit constant and the construction make it usable. I would bring it to a reading group and cite it in any follow-up work on the real or complex GTZ bounds. It deserves peer review; the proof is short enough that referees can check the details without much trouble.

Referee Report

0 major / 2 minor

Summary. The paper claims to prove an asymptotically tight upper bound for the spectral norms of the best-bounded inverse 2×2 submatrices of arbitrary complex n×2 matrices with orthonormal columns, extending the real case solved by Sengupta and Pautov. The argument reduces the problem to a trigonometric optimization over the Grassmannian, derives the bound using Jensen-type inequalities on complex phases, and provides a matching asymptotic lower bound via a phased Vandermonde-type construction.

Significance. If correct, this resolves the complex variant of the Goreinov-Tyrtyshnikov-Zamarashkin hypothesis for the two-column case. The elementary, self-contained proof and the explicit matching lower bound construction are strengths that make the result a solid contribution to numerical linear algebra and matrix theory.

minor comments (2)

[Abstract] Abstract: The abstract refers to 'the asymptotically tight upper bound' without stating its explicit form or the leading constant; adding this would help readers immediately assess the result.
[Main argument] The reduction step to trigonometric optimization over the Grassmannian (mentioned in the proof sketch) would benefit from an explicit parametrization of the complex phases in the first paragraph of the main argument section.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, the recognition that it resolves the complex variant of the Goreinov-Tyrtyshnikov-Zamarashkin hypothesis for the two-column case, and the recommendation for minor revision. We appreciate the note that the elementary proof and explicit lower-bound construction are strengths.

Circularity Check

0 steps flagged

No significant circularity; self-contained proof

full rationale

The manuscript derives the asymptotically tight bound for the complex case via an explicit reduction to trigonometric optimization on the Grassmannian, application of Jensen-type inequalities to phase terms, and a deterministic Vandermonde-style construction for the matching lower bound. All steps are elementary, parameter-free, and independent of any fitted quantities or prior self-citations; the cited real-case result of Sengupta-Pautov serves only as historical context and is not load-bearing for the complex extension. No equation reduces to a redefinition or renaming of its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof relies on standard definitions of the spectral norm, orthonormality over C, and the existence of 2-row submatrices; no new entities or fitted constants are introduced.

axioms (2)

standard math Spectral norm is the largest singular value of a matrix.
Invoked when defining the bounded-inverse property.
domain assumption Columns of the n x 2 matrix are orthonormal, i.e., A^* A = I_2.
Stated in the problem setup.

pith-pipeline@v0.9.0 · 5387 in / 1203 out tokens · 41619 ms · 2026-05-08T02:14:05.001181+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

6 extracted references · 2 canonical work pages · 1 internal anchor

[1]

Berman and R

A. Berman and R. J. Plemmons.Nonnegative Matrices in the Mathematical Sciences. Classics in Applied Mathematics 9. SIAM, 1994

1994
[2]

Goreinov, E.E

S.A. Goreinov, E.E. Tyrtyshnikov, and N.L. Zamarashkin. A theory of pseudo-skeleton approximations.Linear Algebra Appl., 261:1–21, 1997

1997
[3]

Hausmann and A

J.-C. Hausmann and A. Knutson. Polygon spaces and grassmannians.L’Enseignement math´ ematique, 43:173–198, 1997

1997
[4]

R. A. Horn and C. R. Johnson.Matrix Analysis. Cambridge University Press, 2nd edition, 2012

2012
[5]

Nesterenko

Yu. Nesterenko. Submatrices with the best-bounded inverses: StudyingR n×2 andC n×2. ArXiv, 2408.16631, 2024

work page arXiv 2024
[6]

On the submatrices with the best-bounded inverses

R. Sengupta and M. Pautov. On the submatrices with the best-bounded inverses.ArXiv, 2604.05944, 2026. Email address:yuri.r.nesterenko@gmail.com

work page internal anchor Pith review Pith/arXiv arXiv 2026

[1] [1]

Berman and R

A. Berman and R. J. Plemmons.Nonnegative Matrices in the Mathematical Sciences. Classics in Applied Mathematics 9. SIAM, 1994

1994

[2] [2]

Goreinov, E.E

S.A. Goreinov, E.E. Tyrtyshnikov, and N.L. Zamarashkin. A theory of pseudo-skeleton approximations.Linear Algebra Appl., 261:1–21, 1997

1997

[3] [3]

Hausmann and A

J.-C. Hausmann and A. Knutson. Polygon spaces and grassmannians.L’Enseignement math´ ematique, 43:173–198, 1997

1997

[4] [4]

R. A. Horn and C. R. Johnson.Matrix Analysis. Cambridge University Press, 2nd edition, 2012

2012

[5] [5]

Nesterenko

Yu. Nesterenko. Submatrices with the best-bounded inverses: StudyingR n×2 andC n×2. ArXiv, 2408.16631, 2024

work page arXiv 2024

[6] [6]

On the submatrices with the best-bounded inverses

R. Sengupta and M. Pautov. On the submatrices with the best-bounded inverses.ArXiv, 2604.05944, 2026. Email address:yuri.r.nesterenko@gmail.com

work page internal anchor Pith review Pith/arXiv arXiv 2026