Conditioning of a random Krylov compression of a cyclic shift
Let $C_n \in \mathbb{C}^{n \times n}$ be the cyclic shift, $C_n e_j = e_{j+1}$ for $j < n$ and $C_n e_n = e_1$. Draw $b$ uniformly from the unit sphere of $\mathbb{C}^n$. For $2 \le k < n$ let $Q$ have orthonormal columns spanning the Krylov space $$\mathcal{K}_k(C_n, b) = \operatorname{span}\{b, C_n b, \dots, C_n^{k-1} b\},$$ which has dimension $k$ almost surely, and put $H = Q^* C_n Q$. Let $$\kappa_V(H) = \inf_{H = VDV^{-1},\ D \text{ diagonal}} \|V\|_2 \|V^{-1}\|_2,$$ with $\kappa_V(H) = +\infty$ if $H$ is not diagonalizable; it does not depend on the choice of $Q$. With the starting vector $e_1$ in place of $b$, $H$ is a Jordan block for every $k < n$, so $\kappa_V(H) = +\infty$.
Problem. Are there universal constants $C, c > 0$ such that $$\Pr\{\kappa_V(H) \le Cn^c\} \ge 0.99$$ for every $n \ge 3$ and every $2 \le k < n$?
Source: Amsel et al. (2026), Problem 3.5 (scribes Shah and Embree), asked for arbitrary A with the circulant shift singled out. In this form (the cyclic shift, a uniform starting vector on the complex unit sphere, probability 0.99), OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- PR, SP
- Keywords
- circulant matrices, eigenvector condition numbers, Krylov subspaces, OpenProblemsInNLA
- 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{openproblemsinnla-ie10,
author = {Townsend, Alex},
title = {{IE-10}: Conditioning of a random Krylov compression of a cyclic shift},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/eigenvalues-and-inverse-problems/IE-10/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
For the cyclic shift $C_n$ with $n \ge 3$, a starting vector $b$ uniform on the complex unit sphere and $2 \le k < n$, the paper proves that the compression $H_k = Q^*C_nQ$ of $C_n$ to the Krylov space $\operatorname{span}\{b, C_nb, \dots, C_n^{k-1}b\}$ satisfies $\mathbb{E}\,\kappa_V(H_k) \le 17n^2k$, where $\kappa_V$ is the eigenvector condition number. By Markov's inequality, $\kappa_V(H_k) \le …
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-00220, "Conditioning of a random Krylov compression of a cyclic shift", clopen.solutions.