OP-00185 Partially resolved

The least positive permanent of a sign matrix

Let $\Omega_n = \{-1, 1\}^{n \times n}$, let $\operatorname{per}$ be the permanent, and let $p_n$ be the least positive value of $\operatorname{per} A$ for $A \in \Omega_n$ (the all-ones matrix has permanent $n!$). Kräuter and Seifter showed that $2^{n - \lfloor \log_2(n+1) \rfloor}$ divides $\operatorname{per} A$ for every $A \in \Omega_n$, so $p_n$ is at least this number, and Wanless gave matrices attaining it for every $n \le 20$. A different conjecture of Kräuter, a rank-dependent upper bound on $|\operatorname{per} A|$, was proved by Budrevich and Guterman.

Problem. Is $p_n = 2^{n - \lfloor \log_2(n+1) \rfloor}$ for every $n \ge 1$?

Source: Kräuter (1985); listed by Minc (1987) as Conjecture 36. The case n = 2ᵏ − 1 is in Kräuter (1983), (4.24).

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{minc1987,
  author  = {Minc, Henryk},
  title   = {Theory of permanents 1982--1985},
  journal = {Linear Multilinear Algebra},
  volume  = {21},
  number  = {2},
  year    = {1987},
  pages   = {109--148},
  doi     = {10.1080/03081088708817786},
}
@article{krauter1983,
  author  = {Kr{\"a}uter, Arnold Richard},
  title   = {Permanenten -- ein kurzer {\"U}berblick},
  journal = {S{\'e}m. Lothar. Combin.},
  volume  = {9},
  year    = {1983},
  pages   = {Art. B09b},
  url     = {https://www.mat.univie.ac.at/~slc/opapers/s09kraeu.html},
}
@article{wanless2005,
  author  = {Wanless, Ian M.},
  title   = {Permanents of matrices of signed ones},
  journal = {Linear Multilinear Algebra},
  volume  = {53},
  number  = {6},
  year    = {2005},
  pages   = {427--433},
  doi     = {10.1080/03081080500093990},
}
@article{krauterseifter1983,
  author  = {Kr{\"a}uter, Arnold R. and Seifter, Norbert},
  title   = {On some questions concerning permanents of $(1,-1)$-matrices},
  journal = {Israel J. Math.},
  volume  = {45},
  number  = {1},
  year    = {1983},
  pages   = {53--62},
  doi     = {10.1007/BF02760670},
}
@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},
}
@article{budrevich2019,
  author        = {Budrevich, Mikhail V. and Guterman, Alexander E.},
  title         = {Kr{\"a}uter conjecture on permanents is true},
  journal       = {J. Combin. Theory Ser. A},
  volume        = {162},
  year          = {2019},
  pages         = {306--343},
  doi           = {10.1016/j.jcta.2018.11.009},
  eprint        = {1810.04439},
  archivePrefix = {arXiv},
}
@article{cheon2005,
  author  = {Cheon, Gi-Sang and Wanless, Ian M.},
  title   = {An update on {M}inc's survey of open problems involving permanents},
  journal = {Linear Algebra Appl.},
  volume  = {403},
  year    = {2005},
  pages   = {314--342},
  doi     = {10.1016/j.laa.2005.02.030},
}
@techreport{krauter1985,
  author      = {Kr{\"a}uter, Arnold Richard},
  title       = {Recent results on permanents of $(+1,-1)$-matrices},
  institution = {Forschungszentrum Graz},
  type        = {Bericht},
  number      = {249},
  year        = {1985},
  pages       = {243--254},
  note        = {Not seen; details per Cheon and Wanless},
}
@misc{openproblemsinnla-ac11,
  author       = {Townsend, Alex},
  title        = {{AC-11}: The least positive permanent of a sign matrix},
  howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
  year         = {2026},
  url          = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/arithmetic-and-complexity/AC-11/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-00185, "The least positive permanent of a sign matrix", clopen.solutions.