Exact determinant ranges of general tridiagonal interval matrices
For $n \ge 2$ let $[\underline{a}_i, \overline{a}_i]$ for $1 \le i \le n$, and $[\underline{b}_i, \overline{b}_i]$ and $[\underline{c}_i, \overline{c}_i]$ for $1 \le i < n$, be $3n - 2$ closed intervals with rational endpoints, each lower endpoint at most the upper one, and let $$\mathcal T = \{T \in \mathbb{R}^{n \times n} : T_{ii} \in [\underline{a}_i, \overline{a}_i],\ T_{i,i+1} \in [\underline{b}_i, \overline{b}_i],\ T_{i+1,i} \in [\underline{c}_i, \overline{c}_i],\ T_{ij} = 0 \text{ for } |i - j| > 1\},$$ its entries varying independently. Let $d_- = \min_{T \in \mathcal T} \det T$ and $d_+ = \max_{T \in \mathcal T} \det T$. Since the determinant is affine in each entry, both are attained at matrices whose entries are interval endpoints, so they are rational. For general interval matrices, computing the exact range of the determinant is NP-hard (see Horáček, Hladík and Matějka). Bar-On, Codenotti and Leoncini showed that regularity of a tridiagonal interval matrix, here $0 \notin [d_-, d_+]$, can be checked in linear time, and Horáček, Hladík and Matějka showed that $d_-$ and $d_+$ can be computed in polynomial time when every member of $\mathcal T$ is an H-matrix.
Problem. Is there a deterministic algorithm that, given the $3n - 2$ intervals, returns the exact rational numbers $d_-$ and $d_+$ in time polynomial in the total binary input length, uniformly in $n$? Instances in which $\mathcal T$ contains singular matrices, and intervals containing $0$, are included.
Source: Hladík (2020), §2 of the arXiv version, first posted as arXiv:1711.08732 (2017); again Horáček, Hladík and Matějka (2018), §5.4. Stated with explicit input and output conventions by OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- RA
- Keywords
- determinants, interval matrices, OpenProblemsInNLA, tridiagonal matrices
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@incollection{hladik2020,
author = {Hlad{\'\i}k, Milan},
title = {An Overview of Polynomially Computable Characteristics of Special Interval Matrices},
booktitle = {Beyond Traditional Probabilistic Data Processing Techniques: Interval, Fuzzy etc. Methods and Their Applications},
editor = {Kosheleva, Olga and Shary, Sergey P. and Xiang, Gang and Zapatrin, Roman},
series = {Stud. Comput. Intell.},
volume = {835},
publisher = {Springer},
address = {Cham},
year = {2020},
pages = {295--310},
doi = {10.1007/978-3-030-31041-7_16},
eprint = {1711.08732},
archivePrefix = {arXiv},
}
@article{horacek2018,
author = {Hor{\'a}{\v{c}}ek, Jaroslav and Hlad{\'\i}k, Milan and Mat{\v{e}}jka, Josef},
title = {Determinants of Interval Matrices},
journal = {Electron. J. Linear Algebra},
volume = {33},
year = {2018},
pages = {99--112},
doi = {10.13001/1081-3810.3719},
eprint = {1809.03736},
archivePrefix = {arXiv},
}
@article{baron1996,
author = {Bar-On, Ilan and Codenotti, Bruno and Leoncini, Mauro},
title = {Checking robust nonsingularity of tridiagonal matrices in linear time},
journal = {BIT},
volume = {36},
number = {2},
year = {1996},
pages = {206--220},
doi = {10.1007/BF01731979},
}
@misc{openproblemsinnla-iv02,
author = {Townsend, Alex},
title = {{IV-02}: Exact determinant ranges of general tridiagonal interval matrices},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/intervals-and-absolute-value-equations/IV-02/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
A reduction from PARTITION encodes signed sums of small rational rotation angles in the continuant of a tridiagonal interval matrix. It proves that deciding whether the maximum determinant of a rational tridiagonal interval matrix is at least a rational threshold is NP-complete, and that computing the exact determinant range, and the exact interval hull of the solution set of a …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Open → Partially resolved | The registry's curators | Exact tridiagonal interval determinants and solution hulls are NP-hard v1 recorded from OpenProblemsInNLA @ eb7c9d6, manuscripts/IV-02_IV-04.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00264, "Exact determinant ranges of general tridiagonal interval matrices", clopen.solutions.