Linear Systems and Eigenvalue Problems — Problem 4 (Polynomially decaying eigenvalues)

Definitions and mathematical statement

Fix constants $\varepsilon>0$ and $p>0$. For each integer $n\geq 1$, let $U_n\in{\mathbb{C}}^{n\times n}$ have Haar probability distribution on the unitary group, and define \[ \Lambda_n=\operatorname{diag}(1^{-p},2^{-p},\ldots,n^{-p}), \qquad A_n=U_n\Lambda_n U_n^*. \] Here $U_n^*$ denotes the conjugate transpose, so $A_n$ is Hermitian positive definite with eigenvalues $j^{-p}$, $1\leq j\leq n$. Let $z_n\in{\mathbb{C}}^n$ be distributed uniformly "on the sphere," as stated in the source, and set $b_n=A_nz_n$. The supplied record does not specify the sphere's normalization or whether $z_n$ is independent of $U_n$.

The requested comparison is the asymptotic behavior, as $n\to\infty$ with $p$ and $\varepsilon$ fixed, of \[ T_{\mathrm{CG}}(A_n,b_n,\varepsilon) \qquad\text{and}\qquad T_{\mathrm{RCD}}(A_n,b_n,\varepsilon). \] The source uses $\epsilon$ in these expressions after fixing $\varepsilon$; they are treated here as the same tolerance parameter. The quantities $T_{\mathrm{CG}}$ and $T_{\mathrm{RCD}}$ are not defined in the supplied record. In particular, the algorithmic conventions, initialization, stopping criterion, cost measure, and intended probabilistic meaning of the asymptotic comparison are unspecified. Thus this is the supplied comparison question with unresolved qualifications, rather than a fully specified asymptotic assertion.

Short English statement

For matrices with eigenvalues $j^{-p}$ and Haar-distributed eigenvectors, compare the source's quantities $T_{\mathrm{CG}}$ and $T_{\mathrm{RCD}}$ as the dimension grows, using right-hand sides $b_n=A_nz_n$. Definitions of these quantities and several distributional conventions are needed to make the comparison precise.

Sources

• Local UnsolvedMath registry: permanent ID $800495$, source problem code catalogue entry, titled "Linear Systems and Eigenvalue Problems --- Problem 4 (Polynomially decaying eigenvalues)." The supplied record attributes the problem to Amsel, Baumann et al., with proposed year 2026, and labels it open; this is a supplied status label, not an independently verified mathematical assessment.
• Supplied source: Amsel, Baumann et al., Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop (2026), Problem 4, https://arxiv.org/abs/2602.05394. The record reports access on 2026-10-16 and extraction by arxiv_latex. These provenance details are supplied curation and were not independently verified here.
• Supplied registry provenance: upstream ID $800495$, upstream revision d371ee917ac9647fbb06cd6fc529deec6f3dda82; record updated 2026-10-16T14:00:00Z. Background context: "Polynomially decaying eigenvalues."