Construct a separating diagonal perturbation in nearly linear time
For a Hermitian matrix $H$ with eigenvalues $\lambda_1(H), \dots, \lambda_n(H)$ listed with multiplicity, let $$\operatorname{gap}(H) = \min_{i \ne j} |\lambda_i(H) - \lambda_j(H)|.$$ Amsel et al. recall Minami's estimate: if $E$ is a random diagonal matrix with independent absolutely continuous entries, then with high probability $\operatorname{gap}(T + \delta E) \ge C(\delta/n)^{c}$ for a Hermitian tridiagonal $T$, with $C, c$ depending on the distribution of the entries. They ask for an efficient deterministic construction of such a perturbation, and suggest starting with tridiagonal Toeplitz matrices, whose eigenvalues are known explicitly.
Problem. Are there universal constants $a, c_0, C, q > 0$ and a deterministic algorithm that, for every $n \ge 2$, every Hermitian tridiagonal $T \in \mathbb{C}^{n \times n}$ with $\|T\|_2 \le 1$ and every $0 < \delta < 1/2$, receives the three diagonals of $T$ and returns a real diagonal matrix $D$ with $$\|D\|_2 \le \delta, \qquad \operatorname{gap}(T + D) \ge c_0 \left(\frac{\delta}{n}\right)^{a},$$ using at most $Cn\,[1 + \log(n/\delta)]^q$ exact arithmetic operations and comparisons? Square roots of nonnegative real numbers cost one operation each; extracting bits from exact real inputs is not allowed.
Source: Amsel et al. (2026), Problem 3.2, in the nearly linear-time form it calls ambitious; made precise by OpenProblemsInNLA (‖T‖₂ ≤ 1, 0 < δ < 1/2, a real diagonal D with ‖D‖₂ ≤ δ, and the exact arithmetic model of Sobczyk (2025)).
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- SP
- Keywords
- deterministic algorithms, eigenvalue gaps, OpenProblemsInNLA, tridiagonal matrices
- Literature checked
- Oct. 7, 2026 by clemens-admin
References
@misc{amsel2026,
author = {Amsel, Noah and Baumann, Yves and Beckman, Paul and B{\"u}rgisser, Peter and Cama{\~n}o, Chris and Chen, Tyler and Chow, Edmond and Damle, Anil and Derezinski, Michal and Embree, Mark and Epperly, Ethan N. and Falgout, Robert and Fornace, Mark and Greenbaum, Anne and Greif, Chen and Halikias, Diana and Huang, Zhen and Jarlebring, Elias and Koutis, Yiannis and Kressner, Daniel and Kyng, Rasmus and Liesen, J{\"o}rg and Lok, Jackie and Meyer, Raphael A. and Nakatsukasa, Yuji and Pearce, Kate and Peng, Richard and Persson, David and Rebrova, Eliza and Schneider, Ryan and Shah, Rikhav and Solomonik, Edgar and Srivastava, Nikhil and Townsend, Alex and Webber, Robert J. and Williams, Jess},
title = {Linear Systems and Eigenvalue Problems: Open Questions from a {S}imons Workshop},
year = {2026},
eprint = {2602.05394},
archivePrefix = {arXiv},
}
@inproceedings{sobczyk2025,
author = {Sobczyk, Aleksandros},
title = {Deterministic Complexity Analysis of {H}ermitian Eigenproblems},
booktitle = {52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
series = {LIPIcs},
volume = {334},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
year = {2025},
pages = {131:1--131:21},
doi = {10.4230/LIPIcs.ICALP.2025.131},
eprint = {2410.21550},
archivePrefix = {arXiv},
}
@article{minami1996,
author = {Minami, Nariyuki},
title = {Local fluctuation of the spectrum of a multidimensional {A}nderson tight binding model},
journal = {Comm. Math. Phys.},
volume = {177},
number = {3},
year = {1996},
pages = {709--725},
doi = {10.1007/BF02099544},
}
@misc{openproblemsinnla-ke02,
author = {Townsend, Alex},
title = {{KE-02}: Construct a separating diagonal perturbation in nearly linear time},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/eigenvalues-and-inverse-problems/KE-02/README.md},
note = {Read at commit 7336302, 2026-10-06},
}
Resolution claims
For a Hermitian tridiagonal $T$ and $0<\delta<1/2$, the note gives deterministic constructions, on two explicit classes, of a real diagonal $D$ with $\|D\|_2\le\delta$ that separates the eigenvalues of $T+D$. Write $T=\operatorname{diag}(t_i)+R$. If the absolute off-diagonal row sums of $R$ are at most $\delta/[2(n-1)]$, sorting the diagonal and adding an arithmetic ramp of displacements gives $\operatorname{gap}(T+D)\ge\delta/(n-1)$ in $O(n\log n)$ operations, by …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Open → Partially resolved | The registry's curators | Deterministic separation on two explicit tridiagonal classes v1 recorded from OpenProblemsInNLA @ eb7c9d6, KE-02/proof.md. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00151, "Construct a separating diagonal perturbation in nearly linear time", clopen.solutions.