On the submatrices with the best-bounded inverses

Mikhail Pautov; Richik Sengupta

arxiv: 2604.05944 · v5 · submitted 2026-04-07 · 🧮 math.NA · cs.NA

On the submatrices with the best-bounded inverses

Richik Sengupta , Mikhail Pautov This is my paper

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

classification 🧮 math.NA cs.NA

keywords orthonormal matrixsubmatrix selectionsmallest singular valuenumerical linear algebracolumn subset selectionwell-conditioned submatrixmaximal volume principle

0 comments

The pith

Any n-by-2 real matrix with orthonormal columns has a 2-by-2 submatrix whose smallest singular value is at least 1/sqrt(n).

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

The authors prove that for any n by 2 matrix U whose columns are orthonormal, there always exist two rows that can be extracted to form a 2 by 2 submatrix Q whose smallest singular value is bounded below by 1 over the square root of n. This bound directly controls the size of the inverse of Q, keeping its operator norm at most sqrt(n). The result confirms the 1997 hypothesis in the special case k=2 for every n greater than 2, after earlier verification only for the tiny instance n=4.

Core claim

If U is an n by 2 real matrix satisfying U transpose U equals the 2 by 2 identity, then there exist two distinct row indices such that the 2 by 2 matrix Q formed by those rows obeys sigma_min of Q at least 1 over square root of n.

What carries the argument

Existence of a 2-row submatrix Q of the n by 2 orthonormal matrix U whose smallest singular value meets the explicit lower bound 1/sqrt(n).

If this is right

The selected submatrix Q satisfies that the Euclidean norm of its inverse is at most sqrt(n).
The result extends the previously known case n=4, k=2 to arbitrary n when there are only two columns.
Such a submatrix supplies a uniformly bounded inverse that can be used for stable restriction of the column space to two coordinates.

Where Pith is reading between the lines

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

The geometric or combinatorial technique used for two columns may extend to produce a proof for three columns with the same bound.
Algorithms that search for well-conditioned row pairs can now be certified to succeed with the explicit constant 1/sqrt(n) when the input is orthonormal.
The same selection idea connects to pivot selection in QR factorization or CUR decompositions where conditioning of the extracted blocks must be controlled.

Load-bearing premise

The matrix U is real and its two columns are orthonormal, so U transpose times U equals the identity matrix, and the claim must hold for every possible choice of such U.

What would settle it

An explicit n by 2 matrix U with orthonormal columns in which every possible 2 by 2 submatrix has smallest singular value strictly less than 1 over square root of n would disprove the claim.

read the original abstract

The following hypothesis was formulated by Goreinov, Tyrtyshnikov, and Zamarashkin in \cite{goreinov1997theory}. If $U$ is $n\times k$ real matrix with the orthonormal columns $(n>k)$, then there exists a submatrix $Q$ of $U$ of size $k\times k$ such that its smallest singular value is at least $\frac{1}{\sqrt{n}}.$ Although this statement is supported by numerical experiments, the problem remains open for all $1<k<n-1,$ except for the case of $n = 4,\ k=2.$ In this work, we provide a proof for the case $k=2$ and arbitrary $n.$

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

They prove the k=2 case of the Goreinov-Tyrtyshnikov-Zamarashkin hypothesis for any n by exhaustive case analysis on the row vectors in R^2.

read the letter

The paper settles the k=2 instance of the GTZ conjecture: any real n by 2 matrix with orthonormal columns has a 2 by 2 submatrix whose smallest singular value is at least 1/sqrt(n). This was the last open special case listed in the literature, so the result is genuinely new even though it leaves the general k problem untouched. The argument works by viewing the rows as vectors in R^2 whose squared norms sum to 2, then showing that some pair must have Gram matrix with smallest eigenvalue at least 1/n. They split into cases based on the possible inner-product values and angles, handling near-zero rows, repeated rows, and obtuse angles separately. The stress-test note indicates the cases are exhaustive and no continuity or genericity assumptions are hidden, which matches what the abstract claims. The write-up is compact, which is fine for a short note but means a few boundary transitions between cases could use one extra sentence of justification. No circularity or fitted parameters appear, and the claim is stated cleanly as an existence result under the orthonormality hypothesis. This is useful for people working on column subset selection or volume sampling bounds in numerical linear algebra; it removes a concrete open question without promising broader technology. I would send it to peer review because the central claim is now checkable by experts in a few hours and the method stays elementary. It is not a breakthrough for the full conjecture, but it is honest progress on the stated problem.

Referee Report

0 major / 2 minor

Summary. The manuscript proves the k=2 case of the Goreinov-Tyrtyshnikov-Zamarashkin hypothesis: for any real n×2 matrix U with orthonormal columns, there exists a 2×2 submatrix Q such that its smallest singular value satisfies σ_min(Q) ≥ 1/√n. The argument considers the n row vectors in R^2 whose squared Euclidean norms sum to 2 and selects a pair whose Gram matrix has smallest eigenvalue at least 1/n, using exhaustive case analysis on all possible inner-product configurations (including linearly dependent, near-zero, and arbitrary-angle rows).

Significance. If the case analysis is complete, the result is significant: it supplies the first general proof for k=2 (previously known only for n=4) and gives an explicit, non-asymptotic guarantee for selecting well-conditioned submatrices. The exhaustive enumeration of configurations, which avoids continuity or genericity assumptions, is a clear strength and may inform attempts at higher k.

minor comments (2)

[Introduction] The introduction would benefit from an explicit outline of the case-division structure (e.g., how the cases on the angle between rows and their norms are partitioned) to help the reader follow the exhaustive analysis.
[Proof section] A short pseudocode or algorithmic description of how to locate the desired pair of rows would make the constructive nature of the proof more transparent for numerical applications.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, recognition of the significance of the k=2 result, and recommendation of minor revision. We appreciate the note that the exhaustive case analysis is a strength.

Circularity Check

0 steps flagged

No significant circularity; proof is self-contained case analysis

full rationale

The paper states an open hypothesis from Goreinov et al. (1997) and supplies an independent proof for the k=2 case. The argument rests on the orthonormality condition U^T U = I_2, decomposes the rows into vectors in R^2 whose squared norms sum to 2, and performs exhaustive case analysis on inner-product configurations to guarantee a pair whose Gram matrix has smallest eigenvalue at least 1/n. No parameter fitting, self-referential definitions, or load-bearing self-citations appear; the cited reference only formulates the conjecture, not the k=2 proof. The derivation therefore does not reduce to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the standard definition of orthonormal columns and the singular-value characterization of the smallest singular value; no free parameters, ad-hoc axioms, or new entities are introduced in the abstract.

axioms (2)

domain assumption U is real n x k with orthonormal columns, i.e., U^T U = I_k
This is the explicit hypothesis setup stated in the abstract.
standard math The smallest singular value of a square matrix Q controls the norm of its inverse
Standard linear-algebra fact used to translate the singular-value bound into a statement about bounded inverses.

pith-pipeline@v0.9.0 · 5417 in / 1247 out tokens · 53165 ms · 2026-05-10T18:28:42.627253+00:00 · methodology

discussion (0)

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Submatrices with the best-bounded inverses: an asymptotically tight upper bound for $\mathbb{C}^{n \times 2}$
math.NA 2026-04 unverdicted novelty 7.0

Proves an asymptotically tight upper bound on the spectral norm of the best-bounded-inverse 2x2 submatrix for arbitrary complex n x 2 orthonormal-column matrices.
Submatrices with the best-bounded inverses: the equality criterion for $\mathbb{R}^{n \times 2}$
math.NA 2026-04 unverdicted novelty 6.0

The equality criterion for submatrices with the best-bounded inverses is established for real n by 2 matrices.

Reference graph

Works this paper leans on

3 extracted references · 3 canonical work pages · cited by 2 Pith papers

[1]

A theory of pseudoskeleton approximations.Linear algebra and its applications, 261(1-3):1–21, 1997

Sergei A Goreinov, Eugene E Tyrtyshnikov, and Nickolai L Zamarashkin. A theory of pseudoskeleton approximations.Linear algebra and its applications, 261(1-3):1–21, 1997

work page 1997
[2]

Submatrices with the best-bounded inverses: revisiting the hypothesis.arXiv preprint arXiv:2303.07492, 2023

Yuri Nesterenko. Submatrices with the best-bounded inverses: revisiting the hypothesis.arXiv preprint arXiv:2303.07492, 2023

work page arXiv 2023
[3]

Nesterenko

Yuri Nesterenko. Submatrices with the best-bounded inverses: StudyingR n×2 andC n×2.arXiv preprint arXiv:2408.16631, 2024. 5

work page arXiv 2024

[1] [1]

A theory of pseudoskeleton approximations.Linear algebra and its applications, 261(1-3):1–21, 1997

Sergei A Goreinov, Eugene E Tyrtyshnikov, and Nickolai L Zamarashkin. A theory of pseudoskeleton approximations.Linear algebra and its applications, 261(1-3):1–21, 1997

work page 1997

[2] [2]

Submatrices with the best-bounded inverses: revisiting the hypothesis.arXiv preprint arXiv:2303.07492, 2023

Yuri Nesterenko. Submatrices with the best-bounded inverses: revisiting the hypothesis.arXiv preprint arXiv:2303.07492, 2023

work page arXiv 2023

[3] [3]

Nesterenko

Yuri Nesterenko. Submatrices with the best-bounded inverses: StudyingR n×2 andC n×2.arXiv preprint arXiv:2408.16631, 2024. 5

work page arXiv 2024