Kräuter’s minimum sign-matrix permanent

← Minc’s list

Minc’s list · Conjecture 36

Kräuter’s minimum sign-matrix permanent

Open

Posed by
Kräuter
First posed
1985

Statement

Posed by A. R. Kräuter in a 1985 report on permanents of \((\pm1)\)-matrices, after he had conjectured the case of orders \(2^k-1\) in an earlier survey; it is Conjecture 36 in Minc’s 1987 survey.

Conjecture 36. The minimum value of the permanent on the set of \(n\times n\) \((1,-1)\)-matrices with positive permanent is

\[ 2^{\,n-\lfloor\log_2(n+1)\rfloor}. \]

Negating a row changes only the sign of the permanent, so this is also the least nonzero value of \(\lvert\operatorname{per}A\rvert\). Kräuter and Seifter showed that \(2^{\,n-\lfloor\log_2(n+1)\rfloor}\) divides the permanent of every such matrix, so the conjecture is equivalent to finding, in every order, a matrix whose permanent has exactly this absolute value.

Prior progress

  • Kräuter and Seifter (1983) proved the divisibility bound, so no smaller positive value can occur.
  • Kräuter (1985) verified the conjecture for \(n\le7\), and Wanless (2005) gave explicit attaining matrices for every \(n\le20\).
  • Budrevich, Guterman and Taranin (2015, 2017) gave a short proof of the divisibility theorem and showed that its exponent is best possible \(2\)-adically, which does not settle attainment.
  • Ingram and Razborov (2025) studied the range of permanents of \((\pm1)\)-matrices and list the conjecture as open.

Our progress so far

  • All orders up to \(32\). For every \(21\le n\le32\) we constructed an explicit \(n\times n\) \((\pm1)\)-matrix whose permanent is \(\pm2^{\,n-\lfloor\log_2(n+1)\rfloor}\); for example, our matrix of order \(32\) has permanent \(-2^{27}\). With the divisibility bound and Wanless’s matrices, the conjecture holds for all \(n\le32\).
  • Cofactors of extremal matrices. If \(\lvert\operatorname{per}A\rvert=2^{\,n-\lfloor\log_2(n+1)\rfloor}\), then all permanental cofactors of \(A\) are divisible by the corresponding value for order \(n-1\), and after dividing, their greatest common divisor is \(1\) or \(2\). A \(6\times6\) example shows that the value \(2\) occurs.

The first open order is \(n=33\).

References

  1. A. R. Kräuter, Recent results on permanents of (1, −1) matrices, Berichte 249, Forschungszentrum Graz, 1985.
  2. A. R. Kräuter and N. Seifter, On some questions concerning permanents of (1, −1)-matrices, Israel J. Math. 45 (1983), 53–62. doi:10.1007/BF02760670
  3. H. Minc, Theory of permanents 1982–1985, Linear and Multilinear Algebra 21 (1987), 109–148. doi:10.1080/03081088708817786
  4. I. M. Wanless, Permanents of matrices of signed ones, Linear and Multilinear Algebra 53 (2005), 427–433. doi:10.1080/03081080500093990
  5. M. V. Budrevich, A. E. Guterman and K. A. Taranin, On the divisibility of permanents for (±1)-matrices, J. Math. Sci. 216 (2016), 738–745. doi:10.1007/s10958-016-2937-4
  6. D. Ingram and A. Razborov, On the range of the permanent of (±1)-matrices, Linear Algebra Appl. 743 (2026), 271–285. arXiv:2507.09433