Vanishing Hadamard permanents

← Minc’s list

Minc’s list · Problem 5

Vanishing Hadamard permanents

Open

Posed by
Wang
First posed
1974

Statement

Posed by E. T. H. Wang in 1974, in a paper on permanents of \((\pm1)\)-matrices; it is Problem 5 in Minc’s 1978 book.

Problem 5. Can the permanent of an \(n\times n\) Hadamard matrix vanish for \(n>2\)?

A Hadamard matrix is a \((\pm1)\)-matrix \(H\) with \(HH^{\mathsf T}=nI\); apart from \(n=1,2\) these exist only when \(4\) divides \(n\). The restriction \(n>2\) is needed because \(\operatorname{per}\bigl(\begin{smallmatrix}1&1\\1&-1\end{smallmatrix}\bigr)=0\).

Prior progress

  • Wanless (2005) computed the permanents of all Hadamard matrices of orders \(4,8,\dots,28\), up to equivalence. None vanishes, and in each case the exact power of \(2\) dividing \(\operatorname{per}H\) equals that dividing \(n!\), which led him to conjecture this in every order \(n\ge4\).
  • Chabaud (2018) proved Wanless’s conjecture, and hence nonvanishing, for the Sylvester matrices of every order \(2^k\ge4\).
  • The Hadamard structure is essential: a \((\pm1)\)-matrix of order \(n\) with zero permanent exists whenever \(n+1\) is not a power of \(2\).

Our progress so far

  • Every Hadamard order below \(128\). For every order \(32\le n\le124\), every real Hadamard matrix \(H\) of order \(n\) satisfies Wanless’s conjecture: the exact power of \(2\) dividing \(\operatorname{per}H\) is the one dividing \(n!\). In particular \(\operatorname{per}H\ne0\). These are proofs for all matrices of each order, not enumerations; order \(32\) alone has more than \(13\) million equivalence classes.

References

  1. E. T. H. Wang, On permanents of (1, −1)-matrices, Israel J. Math. 18 (1974), 353–361. doi:10.1007/BF02760844
  2. H. Minc, Permanents, Encyclopedia of Mathematics and its Applications 6, Addison-Wesley, 1978.
  3. I. M. Wanless, Permanents of matrices of signed ones, Linear and Multilinear Algebra 53 (2005), 427–433. doi:10.1080/03081080500093990
  4. U. Chabaud, On the permanent of Sylvester-Hadamard matrices, preprint (2018). arXiv:1802.08001