OP-00186 Partially resolved

Realizing every sign-matrix permanent with negative entries confined on or above the diagonal

Let $\Omega_n = \{-1, 1\}^{n \times n}$, let $\operatorname{per}$ be the permanent, and let $\mathcal{U}_n \subseteq \Omega_n$ consist of the matrices whose entries below the diagonal all equal $1$, so that every entry $-1$ lies on or above the diagonal (diagonal entries may be $-1$). Ingram and Razborov showed that the number of values of $\operatorname{per}$ on $\Omega_n$ grows superpolynomially in $n$, and Hunter, Kwan and Sauermann that it grows at least exponentially.

Problem. Does every $A \in \Omega_n$ have some $B \in \mathcal{U}_n$ with $\operatorname{per} B = \operatorname{per} A$, for every $n \ge 1$? That is, is $$\{\operatorname{per} B : B \in \mathcal{U}_n\} = \{\operatorname{per} A : A \in \Omega_n\}$$ for every $n \ge 1$?

Source: Ingram and Razborov (2026), Problem 4 of arXiv:2507.09433v1.

Imported from github.com/ajt60gaibb/OpenProblemsInNLA.

Classification

Primary: CO — Combinatorics
Secondary: NA
Keywords: OpenProblemsInNLA, permanents, sign matrices
Literature checked: Oct. 8, 2026 by clemens-admin

References

@article{ingram2026,
  author        = {Ingram, DeVon and Razborov, Alexander},
  title         = {On the range of the permanent of $(\pm1)$-matrices},
  journal       = {Linear Algebra Appl.},
  volume        = {743},
  year          = {2026},
  pages         = {271--285},
  doi           = {10.1016/j.laa.2026.04.027},
  eprint        = {2507.09433},
  archivePrefix = {arXiv},
}
@misc{hunter2025,
  author        = {Hunter, Zach and Kwan, Matthew and Sauermann, Lisa},
  title         = {Exponential anticoncentration of the permanent},
  year          = {2025},
  eprint        = {2509.22577},
  archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ac12,
  author       = {Townsend, Alex},
  title        = {{AC-12}: Realizing every sign-matrix permanent with negative entries confined on or above the diagonal},
  howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
  year         = {2026},
  url          = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/arithmetic-and-complexity/AC-12/README.md},
  note         = {Read at commit b8c7852, 2026-10-07},
}

Resolution claims

Exact finite cases of two sign-matrix permanent problems v1 GitHub ↗

Matthew J. Colbrook

Explicit integer certificates are supplied for two finite-parameter statements about permanents of sign matrices. For every order $1\le n\le35$, a matrix with permanent $2^{n-\lfloor\log_2(n+1)\rfloor}$ is given; the universal divisibility bound therefore identifies the least positive permanent for each of these orders. For every $1\le n\le10$, an explicit catalogue and an exhaustive inclusion check show that every sign-matrix permanent is attained …

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

Status history

When	Change	By	Reason
2026-10-08	Open → Partially resolved	The registry's curators	Exact finite cases of two sign-matrix permanent problems v1 recorded from OpenProblemsInNLA @ eb7c9d6, manuscripts/AC-11-12.pdf.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00186, "Realizing every sign-matrix permanent with negative entries confined on or above the diagonal", clopen.solutions.