Linear Systems and Eigenvalue Problems — Problem 6

Definitions and mathematical statement

Let $n$ be a positive integer and consider a linear system $Ax=b$, where $A$ is an $n\times n$ matrix and $b$ has $n$ entries. The supplied source does not specify the scalar field, the admissible matrix class, or assumptions ensuring existence and uniqueness of a solution. Define \[ \mathrm{nnz}(A)=\left|\{(i,j):1\leq i,j\leq n,\ A_{ij}\neq 0\}\right|. \] For each real $p>0$, the source denotes by $\bar\kappa_p$ the $p$-averaged condition number of the singular values of $A$. No formula for this quantity is included in the supplied record, so its normalization and treatment of zero singular values remain unresolved.

The question attributed to Amsel, Baumann et al., Problem 6, is to determine the smallest real $p>0$ for which an $n\times n$ linear system $Ax=b$ can be solved to high accuracy using \[ \widetilde O\!\left(\mathcal T_A\,\bar\kappa_p\right) \] arithmetic operations, where $\mathcal T_A$ is either $n^2$ or $\mathrm{nnz}(A)$.

This is an unresolved formulation template: the definition of $\bar\kappa_p$, the input domain, the meaning of high accuracy, the factors suppressed by $\widetilde O$, and the algorithmic guarantees must be specified before the requested complexity bound becomes a precise mathematical assertion. The supplied record also does not clarify whether the two choices of $\mathcal T_A$ are separate targets or simultaneous requirements. Its request for a smallest positive exponent does not establish that such a minimum exists.

Short English statement

Determine the smallest positive exponent $p$ permitting highly accurate linear-system solution in $\widetilde O(\mathcal T_A\bar\kappa_p)$ arithmetic operations, with $\mathcal T_A=n^2$ or $\mathrm{nnz}(A)$. The supplied record leaves the averaged condition number and essential accuracy and input assumptions undefined, so a complete precise formulation requires mathematical review.

Sources

• Local UnsolvedMath registry, permanent ID $800497$, exact source problem code catalogue entry, title "Linear Systems and Eigenvalue Problems --- Problem 6." The record attributes the problem to Amsel, Baumann et al., with proposed year 2026, and labels it open. This is supplied registry status, not an independently verified mathematical assessment.
• Amsel, Baumann et al., Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop (2026), Problem 6. Supplied source URL: https://arxiv.org/abs/2602.05394. The record reports access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance details, not a claim of independent source access or verification.