Find a near-largest nonnormal eigenvalue using few matrix-vector products
A diagonalizable $A \in \mathbb{C}^{n \times n}$ is accessible only through exact queries $v \mapsto Av$. A number $K \ge 1$ is supplied, with the promise that $A = V\Lambda V^{-1}$ for some diagonal $\Lambda$ and $\|V\|_2\|V^{-1}\|_2 \le K$; neither the eigenvalues nor $V$ are supplied. The spectral radius $\rho(A) = \max_{\mu \in \sigma(A)} |\mu|$ is assumed to be positive. Between queries an algorithm may perform finite exact arithmetic; only queries are counted, and products with $A^*$ and solutions of shifted linear systems are not additional oracle operations.
Amsel et al. remark that the power method approximates the spectral radius to relative accuracy $\varepsilon$, in a mixed forward–backward error sense, with $O(\log(n\kappa_V)/\varepsilon)$ iterations, where $\kappa_V = \|V\|_2\|V^{-1}\|_2$ (Shah, Srivastava and Zeng).
Problem. Are there universal constants $C, a, b > 0$ and a randomized algorithm that, for every such input and every $\varepsilon \in (0, 1/2)$, returns with probability at least $0.99$ a complex number $z$ such that some $\mu \in \sigma(A)$ satisfies $$|\mu| \ge (1 - \varepsilon)\rho(A), \qquad |z - \mu| \le \varepsilon\rho(A),$$ using at most $C[1 + \log(nK)]^a \varepsilon^{-b}$ matrix-vector queries?
Source: Amsel et al. (2026), Problem 3.9 (Section 3.5, scribe Shah), from the Simons Institute workshop Linear Systems and Eigenvalue Problems (2025); made precise by OpenProblemsInNLA (A diagonalizable with a supplied bound K ≥ 1 on ‖V‖₂‖V⁻¹‖₂, exact queries v ↦ Av only, success probability 0.99, 0 < ε < 1/2, and the query bound C[1 + log(nK)]^a ε^(−b) for poly(log(nκ_V), 1/ε)).
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- SP
- Keywords
- eigenvalue algorithms, nonnormal matrices, OpenProblemsInNLA, query complexity
- Literature checked
- Oct. 8, 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},
}
@misc{shah2024,
author = {Shah, Rikhav and Srivastava, Nikhil and Zeng, Edward},
title = {Sparse Pseudospectral Shattering},
year = {2024},
eprint = {2411.19926},
archivePrefix = {arXiv},
note = {Section 1.3, Theorem 1.5 of v1},
}
@misc{openproblemsinnla-ke03,
author = {Townsend, Alex},
title = {{KE-03}: Find a near-largest nonnormal eigenvalue using few matrix-vector products},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/eigenvalues-and-inverse-problems/KE-03/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
For a diagonalizable complex $n \times n$ matrix $A$ accessed only through exact products $v \mapsto Av$, with a supplied bound $K \ge 1$ on the condition number of an eigenvector matrix and positive spectral radius $\rho$, a randomized algorithm is given that uses $O(\varepsilon^{-2}[1 + \log(nK)])$ queries and, with probability at least $0.997$, returns $z$ such that some eigenvalue …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00228, "Find a near-largest nonnormal eigenvalue using few matrix-vector products", clopen.solutions.