Deterministic regularization of the nonsymmetric eigenproblem
For $M \in \mathbb{C}^{n \times n}$ with simple spectrum let $$\operatorname{gap}(M) = \min_{i \ne j} |\lambda_i(M) - \lambda_j(M)|, \qquad \kappa_V(M) = \inf_{M = VDV^{-1},\ D \text{ diagonal}} \|V\|_2 \|V^{-1}\|_2.$$ Banks, Garza-Vargas, Kulkarni and Srivastava showed that if $\|A\|_2 \le 1$, $0 < \gamma < 1/2$ and $G$ has independent complex Gaussian entries of mean $0$ and variance $1/n$, then with probability at least $1 - 12/n$ $$\|G\|_2 \le 4, \qquad \kappa_V(A + \gamma G) \le \frac{n^2}{\gamma}, \qquad \operatorname{gap}(A + \gamma G) \ge \frac{\gamma^4}{n^5}.$$
Problem. Find a deterministic algorithm and universal constants $C, c, d$ such that, for every $n \ge 2$, every $A \in \mathbb{C}^{n \times n}$ with $\|A\|_2 \le 1$ and every $0 < \delta < 1/2$, the algorithm constructs a matrix $E \in \mathbb{C}^{n \times n}$ with $$\|E\|_2 \le \delta, \qquad A + E \text{ has simple spectrum}, \qquad \frac{\kappa_V(A + E)}{\operatorname{gap}(A + E)} \le C \left(\frac{n}{\delta}\right)^{c},$$ using $O(n^3 \log^d(n/\delta))$ exact arithmetic operations.
Source: Banks, Garza-Vargas, Kulkarni and Srivastava (2023; arXiv 2019), Section 6, first direction for future research; asked for the perturbation alone by Sobczyk (2025; arXiv 2024), Conclusion, question 4, and made precise by Amsel et al. (2026), Problem 3.1. In this form, OpenProblemsInNLA: ‖A‖₂ ≤ 1, 0 < δ < 1/2, exact arithmetic, and the bound C(n/δ)^c where Problem 3.1 prints C(δ/n)^c.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- SP
- Keywords
- deterministic algorithms, eigenvector condition numbers, OpenProblemsInNLA, pseudospectra
- Literature checked
- Oct. 7, 2026 by clemens-admin
References
@article{banks2023,
author = {Banks, Jess and Garza-Vargas, Jorge and Kulkarni, Archit and Srivastava, Nikhil},
title = {Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time},
journal = {Found. Comput. Math.},
volume = {23},
number = {6},
year = {2023},
pages = {1959--2047},
doi = {10.1007/s10208-022-09577-5},
eprint = {1912.08805},
archivePrefix = {arXiv},
}
@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},
}
@misc{openproblemsinnla-ie07,
author = {Townsend, Alex},
title = {{IE-07}: Deterministic regularization of the nonsymmetric eigenproblem},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/eigenvalues-and-inverse-problems/IE-07/README.md},
note = {Read at commit 7336302, 2026-10-06},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00147, "Deterministic regularization of the nonsymmetric eigenproblem", clopen.solutions.