OP-00259 Solution claimed

Exact solution hulls for inverse M-matrix intervals

For $n \ge 1$ and $L, U \in \mathbb{Q}^{n \times n}$, $l, u \in \mathbb{Q}^n$ with $L \le U$ and $l \le u$ entrywise, let $\mathcal A = \{A \in \mathbb{R}^{n \times n} : L \le A \le U\}$ and $\mathbf{b} = \{b \in \mathbb{R}^n : l \le b \le u\}$, their entries varying independently, and let $C = (L + U)/2$ and $R = (U - L)/2$. An inverse M-matrix is the inverse of a nonsingular M-matrix. When every member of $\mathcal A$ is an inverse M-matrix, the solution set $\{A^{-1}b : A \in \mathcal A,\ b \in \mathbf{b}\}$ is nonempty and compact. Johnson and Smith showed that every member of $\mathcal A$ is an inverse M-matrix if and only if every vertex matrix (every member with each entry equal to $L_{ij}$ or $U_{ij}$) is. For such $\mathcal A$, Hladík showed that the entrywise minimum of $A^{-1}$ over $\mathcal A$ is the entrywise minimum of $(C + D_iRD_j)^{-1}$ over $i, j \in \{1, \dots, n\}$, and the maximum that of $(C - D_iRD_j)^{-1}$, where $D_i$ is the diagonal matrix with $-1$ in position $i$ and $1$ in the other diagonal positions; and that $\min (A^{-1}b)_i$ over $\mathcal A \times \mathbf{b}$ is attained with $b_i = l_i$ and $b_j = u_j$ for $j \ne i$, and $\max (A^{-1}b)_i$ with $b_i = u_i$ and $b_j = l_j$ for $j \ne i$.

Problem. Is there a deterministic algorithm that, given $n \ge 1$, $L$, $U$, $l$ and $u$ with the promise that every member of $\mathcal A$ is an inverse M-matrix, returns the exact rational endpoints of $$\prod_{i=1}^n \Big[\min_{A \in \mathcal A,\ b \in \mathbf{b}} (A^{-1}b)_i,\ \max_{A \in \mathcal A,\ b \in \mathbf{b}} (A^{-1}b)_i\Big]$$ in time polynomial in the binary input length? Its behaviour outside the promise is unrestricted, and checking the promise is not part of the task.

Source: Hladík (2020), §9 of the arXiv version, the question before Theorem 25; first posted as arXiv:1711.08732 (2017). Stated as a promise problem in the bit model, with exact rational output, by OpenProblemsInNLA.

Imported from github.com/ajt60gaibb/OpenProblemsInNLA.

Classification

Primary: NA — Numerical Analysis
Secondary: RA
Keywords: interval matrices, inverse M-matrices, linear systems, OpenProblemsInNLA
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{johnson2002,
  author  = {Johnson, Charles R. and Smith, Ronald L.},
  title   = {Intervals of inverse {M}-matrices},
  journal = {Reliab. Comput.},
  volume  = {8},
  number  = {3},
  year    = {2002},
  pages   = {239--243},
  doi     = {10.1023/A:1015517430475},
}
@misc{openproblemsinnla-iv05,
  author       = {Townsend, Alex},
  title        = {{IV-05}: Exact solution hulls for inverse M-matrix intervals},
  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-05/README.md},
  note         = {Read at commit eb7c9d6, 2026-10-07},
}

Resolution claims

Exact inverse-M interval solution hulls by 2n linear programs v1 GitHub ↗

Matthew J. Colbrook

For a rational interval matrix every member of which is an inverse M-matrix, and an arbitrary rational interval right-hand side, the paper computes the exact interval hull of the solution set using $2n$ linear programs, each with $n$ variables and $2n$ inequalities. Writing the interval matrix by its midpoint $C$ and radius $R$, it shows that for each sign vector …

Full resolution · not verified · fidelity not established · posted on GitHub 11 Sep 2026

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-00259, "Exact solution hulls for inverse M-matrix intervals", clopen.solutions.