Hardness of the spectral-norm condition number
Absolute values are taken componentwise, and $\|\cdot\|_2$ is the spectral norm, the operator norm induced by the Euclidean norm. Inputs are rational numbers written in binary, and algorithms are deterministic Turing machines. For $A \in \mathbb{Q}^{n \times n}$, $n \ge 1$, the interval matrix $[A - I_n, A + I_n]$ consists of the matrices $A - \operatorname{diag}(d)$ with $d \in [-1, 1]^n$, and is regular if all of them are nonsingular. For such $A$ let $$c_2(A) = \max_{d \in [-1, 1]^n} \bigl\|(A - \operatorname{diag}(d))^{-1}\bigr\|_2 = \Bigl(\min_{d \in [-1, 1]^n} \sigma_{\min}(A - \operatorname{diag}(d))\Bigr)^{-1}.$$ When $[A - I_n, A + I_n]$ is regular, $Ax - |x| = b$ has a unique solution $x^\star$ for every $b \in \mathbb{R}^n$ (Wu and Li), and Zamani and Hladík showed that $\|x - x^\star\|_2 \le c_2(A)\, \|Ax - |x| - b\|_2$ for all $x \in \mathbb{R}^n$. They showed that the maximum defining $c_2(A)$ is attained at some $d \in \{-1, 1\}^n$, that $c_2(A) = 1/(\sigma_{\min}(A) - 1)$ when $A$ is symmetric, and that the analogous condition numbers for the $1$-norm and the $\infty$-norm are NP-hard to compute.
Problem. Is it $\mathsf{NP}$-hard, under polynomial-time Turing reductions that query only matrices $A$ with $[A - I_n, A + I_n]$ regular, to decide whether $c_2(A) \ge t$, given a rational $t > 0$ and $A \in \mathbb{Q}^{n \times n}$ promised to have $[A - I_n, A + I_n]$ regular? Equality $c_2(A) = t$ is a yes-instance, and checking the promise is not part of the task.
Source: Zamani and Hladík (2023), §2, Remark 1, the conjecture that computing c₂(A) is NP-hard (first posted as arXiv:1912.12904, 2019), repeated as open in their §7; in this decision form, under the regularity promise and with Turing reductions, OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- OC
- Keywords
- absolute value equations, condition numbers, interval matrices, OpenProblemsInNLA
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{zamani2023,
author = {Zamani, Moslem and Hlad{\'\i}k, Milan},
title = {Error bounds and a condition number for the absolute value equations},
journal = {Math. Program.},
volume = {198},
number = {1},
year = {2023},
pages = {85--113},
doi = {10.1007/s10107-021-01756-6},
eprint = {1912.12904},
archivePrefix = {arXiv},
}
@article{wu2018,
author = {Wu, Shi-Liang and Li, Cui-Xia},
title = {The unique solution of the absolute value equations},
journal = {Appl. Math. Lett.},
volume = {76},
year = {2018},
pages = {195--200},
doi = {10.1016/j.aml.2017.08.012},
}
@misc{openproblemsinnla-av02,
author = {Townsend, Alex},
title = {{AV-02}: Hardness of the spectral-norm condition number},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/intervals-and-absolute-value-equations/AV-02/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
The paper proves NP-hardness, under a polynomial-time many-one reduction, of deciding whether the maximum spectral norm of $(A - \operatorname{diag} d)^{-1}$ over $d \in [-1, 1]^n$, a condition number for absolute value equations, is at least a rational threshold. Hardness holds for integer upper-triangular $A$ with every diagonal entry equal to $2$, for which the entire diagonal perturbation family is …
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-00257, "Hardness of the spectral-norm condition number", clopen.solutions.