On the divisibility of permanents for \((\pm1)\)-matrices (Q308667): Difference between revisions

If \(A = (a_{ij})\) is an \(n\times n\)-square matrix, the permanent of \(A\) is defined as \(\text{per}(A) = \sum_{\sigma \in \mathcal{S}_n} a_{1\sigma(1)}\cdots a_{n\sigma(n)}\) where \(\mathcal{S}_n\) denotes the set of permutations on \(\{1,\dots, n\}\). If the entries of \(A\) are elements of \(\{-1,1\}\), \textit{A. R. Kräuter} and \textit{N. Seifter} [Isr. J. Math. 45, 53--62 (1983; Zbl 0517.15009)] have shown that the \(2^{n-\lfloor \log_2(n)\rfloor-1}\) divides \(\mathrm {per}(A)\) and \(2^{n-\lfloor \log_2(n)\rfloor}\) divides \(\mathrm {per}(A)\) if and only if \(n\neq 2^t-1\) for all \(t\in\mathbb{N}\). The present paper gives an alternative proof for these results. For \(0\leq j\leq n\), let \(k_j\) denote the number of sets of cardinality \(j\) of the form \(\{(i_1,\sigma(i_1)), \dots ,(i_j,\sigma(i_j))\}\) such that \(a_{i_k, \sigma(i_k)}=-1\) for \(1\leq k\leq j\) and \(\sigma\in\mathcal{S}_n\). First, the authors show that \[ \mathrm {per}(A) = \sum_{j=0}^n (-2)^jk_j(n-j)! \] holds. Then they prove for \(0\leq j\leq n\) that \(2^{n-j +\lfloor \log_2(n)\rfloor -1}\) divides \((n-j)!\) and \(2^{n-j-\lfloor \log_2(n)\rfloor}\) divides \((n-j)!\) if and only if \(n\neq 2^t-1\) for all \(t\in\mathbb{N}\). Since \(k_0 = 1\), the results of Kräuter and Seifter [loc. cit.] follows.