OP-00175 Partially resolved

The Goreinov–Tyrtyshnikov–Zamarashkin conjecture on square-submatrix inverse norms

For integers $1 \le r < n$ and $U \in \mathbb{R}^{n \times r}$ with $U^{\mathsf T} U = I_r$, write $U_I$ for the $r \times r$ submatrix of $U$ with rows in $I \subseteq \{1, \dots, n\}$, $|I| = r$, and $\|\cdot\|_2$ for the spectral norm. Let $$t(r,n) = \max_{U} \, \min_{I} \, \|U_I^{-1}\|_2,$$ the maximum over all such $U$ and the minimum over the $I$ for which $U_I$ is nonsingular (there is one, since $U$ has rank $r$). Goreinov, Tyrtyshnikov and Zamarashkin bound the error of pseudoskeleton approximations in terms of $t(r,n)$. They showed $t(r,n) \le \sqrt{r(n-r)+1}$, by taking $U_I$ of maximal volume, and $t(r,n) \ge \sqrt{n}$ whenever $r + 1$ divides $n$. Equality holds in their upper bound for $r = 1$ and $r = n - 1$. Nesterenko reports, for every $1 \le r < n$, such $U$ all of whose nonsingular $r \times r$ submatrices have $\|U_I^{-1}\|_2 = \sqrt{n}$, so $t(r,n) \ge \sqrt{n}$ always; and $t(r,n) = t(n-r,n)$ by orthogonal completion. Sengupta and Pautov proved $t(2,n) \le \sqrt{n}$ for every $n \ge 3$, after Nesterenko's case $n = 4$.

Problem. Is $t(r,n) \le \sqrt{n}$ for all integers $1 \le r < n$, that is, does every $U \in \mathbb{R}^{n \times r}$ with $U^{\mathsf T} U = I_r$ have a nonsingular $r \times r$ submatrix $U_I$ with $\|U_I^{-1}\|_2 \le \sqrt{n}$?

Source: Goreinov, Zamarashkin and Tyrtyshnikov (1995); hypothesis (2.6) of Goreinov, Tyrtyshnikov and Zamarashkin (1997).

Imported from github.com/ajt60gaibb/OpenProblemsInNLA.

Classification

Primary: NA — Numerical Analysis
Secondary: FA
Keywords: column subset selection, OpenProblemsInNLA, pseudoskeleton approximations
Literature checked: Oct. 8, 2026 by clemens-admin

References

@article{goreinov1997,
  author  = {Goreinov, S. A. and Tyrtyshnikov, E. E. and Zamarashkin, N. L.},
  title   = {A theory of pseudoskeleton approximations},
  journal = {Linear Algebra Appl.},
  volume  = {261},
  number  = {1--3},
  year    = {1997},
  pages   = {1--21},
  doi     = {10.1016/S0024-3795(96)00301-1},
}
@misc{sengupta2026,
  author        = {Sengupta, Richik and Pautov, Mikhail},
  title         = {On the submatrices with the best-bounded inverses},
  year          = {2026},
  eprint        = {2604.05944},
  archivePrefix = {arXiv},
}
@misc{nesterenko2023,
  author        = {Nesterenko, Yuri},
  title         = {Submatrices with the best-bounded inverses: revisiting the hypothesis},
  year          = {2023},
  eprint        = {2303.07492},
  archivePrefix = {arXiv},
}
@article{goreinov1995,
  author  = {Goreinov, S. A. and Zamarashkin, N. L. and Tyrtyshnikov, E. E.},
  title   = {Pseudo-skeleton approximations of matrices},
  journal = {Dokl. Akad. Nauk},
  volume  = {343},
  number  = {2},
  year    = {1995},
  pages   = {151--152},
  note    = {In Russian},
}
@misc{nesterenko2025,
  author        = {Nesterenko, Yuri},
  title         = {About subspaces the most deviating from the coordinate ones},
  year          = {2025},
  eprint        = {2511.02387},
  archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ra18,
  author       = {Townsend, Alex},
  title        = {{RA-18}: The Goreinov–Tyrtyshnikov–Zamarashkin conjecture on square-submatrix inverse norms},
  howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
  year         = {2026},
  url          = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/randomized-and-low-rank-approximation/RA-18/README.md},
  note         = {Read at commit b8c7852, 2026-10-07},
}

Resolution claims

A recursive counterexample to a complex extension of the Goreinov–Tyrtyshnikov–Zamarashkin conjecture v1 GitHub ↗

Sidney Holden

Weighted orthogonal-complement duality proves the real square-root bound of the Goreinov–Tyrtyshnikov–Zamarashkin conjecture for Parseval frames (matrices with orthonormal columns) having at most $r+2$ nonzero row directions, using the established real two-column theorem. The unrestricted real conjecture is not resolved here. Separately, an explicit sequence of complex matrices with orthonormal columns disproves a dimension-independent complex extension of the conjecture. The matrices …

Partial resolution · not verified · fidelity not established · posted on GitHub 13 Sep 2026

Status history

When	Change	By	Reason
2026-10-09	Open → Partially resolved	The registry's curators	A recursive counterexample to a complex extension of the Goreinov–Tyrtyshnikov–Zamarashkin conjecture v1 recorded from OpenProblemsInNLA @ eb7c9d6, manuscript/ra18.pdf.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00175, "The Goreinov–Tyrtyshnikov–Zamarashkin conjecture on square-submatrix inverse norms", clopen.solutions.