Two-vertex certification of nonsingular sign regularity
Note: OpenProblemsInNLA (IV-01) lists the full problem as solved in Lean, with a proof at https://github.com/erenup/two-vertex-sign-regularity/tree/22fedcfb6940fd943d67f1582068ed5b9b91a83e/lean. It uses Lean 4.34.0-rc2 and a repository the registry has not approved, so it has not been checked here.
For $\epsilon \in \{-1, 1\}^n$, a matrix $M \in \mathbb{R}^{n \times n}$ is nonsingular sign regular with signature $\epsilon$ if $\det M \ne 0$ and $\epsilon_k d \ge 0$ for every minor $d$ of $M$ of order $k$, for $k = 1, \dots, n$. For $L, U \in \mathbb{R}^{n \times n}$ with $L \le U$ entrywise, let $A^-$ and $A^+$ be the checkerboard vertex matrices $$A^-_{ij} = \begin{cases} L_{ij}, & i + j \text{ even}, \\ U_{ij}, & i + j \text{ odd}, \end{cases} \qquad A^+_{ij} = \begin{cases} U_{ij}, & i + j \text{ even}, \\ L_{ij}, & i + j \text{ odd}. \end{cases}$$ Garloff proved the analogue of the implication below for strictly sign regular matrices, and the implication itself whenever the entries with $L_{ij} = U_{ij}$ all have $i + j$ of the same parity. Adm and Garloff proved it for $\epsilon = (1, \dots, 1)$, that is, for nonsingular totally nonnegative matrices, as Garloff had conjectured, and when $A^-$ and $A^+$ are tridiagonal. More generally, Adm and Garloff and Hassuneh, Adm and Garloff proved it for sixteen signatures in each order $n$, eight of period four and the eight obtained from them by changing the sign of $\epsilon_n$, in some cases under a sign condition on one entry of $A^-$ or $A^+$; for $n = 4$ these are all signatures. Without nonsingularity the analogue fails, already for totally nonnegative matrices (Garloff).
Problem. For every $n \ge 5$, all $L, U \in \mathbb{R}^{n \times n}$ with $L \le U$ entrywise and every $\epsilon \in \{-1, 1\}^n$: if $A^-$ and $A^+$ are nonsingular sign regular with signature $\epsilon$, is every $M \in \mathbb{R}^{n \times n}$ with $L \le M \le U$ entrywise nonsingular sign regular with signature $\epsilon$?
Source: Garloff, Adm and Titi (2016), Conjecture 3.1, after Adm and Garloff (2016), who raise it as a question; stated for n ≥ 5 by OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- RA
- Keywords
- interval matrices, OpenProblemsInNLA, sign regular matrices, totally nonnegative matrices
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{garloff2016,
author = {Garloff, J{\"u}rgen and Adm, Mohammad and Titi, Jihad},
title = {A Survey of Classes of Matrices Possessing the Interval Property and Related Properties},
journal = {Reliab. Comput.},
volume = {22},
year = {2016},
pages = {1--14},
url = {https://www.reliable-computing.org/reliable-computing-22-pp-001-014.pdf},
}
@article{adm2016,
author = {Adm, Mohammad and Garloff, J{\"u}rgen},
title = {Intervals of special sign regular matrices},
journal = {Linear Multilinear Algebra},
volume = {64},
number = {7},
year = {2016},
pages = {1424--1444},
doi = {10.1080/03081087.2015.1090388},
}
@article{garloff1982,
author = {Garloff, J{\"u}rgen},
title = {Criteria for sign regularity of sets of matrices},
journal = {Linear Algebra Appl.},
volume = {44},
year = {1982},
pages = {153--160},
doi = {10.1016/0024-3795(82)90010-6},
}
@article{adm2013,
author = {Adm, Mohammad and Garloff, J{\"u}rgen},
title = {Intervals of totally nonnegative matrices},
journal = {Linear Algebra Appl.},
volume = {439},
number = {12},
year = {2013},
pages = {3796--3806},
doi = {10.1016/j.laa.2013.10.021},
}
@article{adm2021,
author = {Adm, Mohammad and Garloff, J{\"u}rgen},
title = {Characterization, perturbation, and interval property of certain sign regular matrices},
journal = {Linear Algebra Appl.},
volume = {612},
year = {2021},
pages = {146--161},
doi = {10.1016/j.laa.2020.12.007},
}
@article{hassuneh2025,
author = {Hassuneh, Imad and Adm, Mohammad and Garloff, J{\"u}rgen},
title = {Matrices having a positive determinant and all other minors nonpositive},
journal = {Spec. Matrices},
volume = {13},
number = {1},
year = {2025},
pages = {20240031},
doi = {10.1515/spma-2024-0031},
}
@article{adm2026,
author = {Adm, Mohammad and Garloff, J{\"u}rgen},
title = {Certification of the Sign Regularity of Matrix Intervals},
journal = {Acta Sci. Math. (Szeged)},
year = {2026},
doi = {10.1007/s44146-026-00223-y},
note = {Online first, 17 January 2026},
}
@misc{openproblemsinnla-iv01,
author = {Townsend, Alex},
title = {{IV-01}: Two-vertex certification of nonsingular sign regularity},
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-01/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
Let the checkerboard vertex matrices $A^-$ and $A^+$ of a real interval matrix $[L,U]$ be nonsingular sign regular with a common signature. The note proves that every matrix in $[L,U]$ is nonsingular sign regular with that signature whenever the fixed nonzero entries ($L_{ij}=U_{ij}\ne0$), oriented by sign and checkerboard parity, form an acyclic directed bipartite graph and the fixed zero entries …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Open → Partially resolved | The registry's curators | A directed fixed-entry criterion v1 recorded from OpenProblemsInNLA @ eb7c9d6, IV-01/result.md. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00201, "Two-vertex certification of nonsingular sign regularity", clopen.solutions.