Question

It is clear that the permanent of an $n\times n$ matrix which entries are odd integers, is an even number, as it is the sum of $n!$ odd numbers. I am interested in finding the highest power of $2$ that divides the permanent of such a matrix.

Note that if $A$ is an odd $n\times n$ matrix, then $\det (A)\equiv 0 (\mod 2^{n-1})$. This can be seen by performing $n-1$ row operations to obtain an $n\times n$ matrix $B$ which $n-1$ of its rows consist of even integers (I found this nice observation in Amos Nevo Peter Sarnak's paper, "Prime and Almost Prime Points on Principal Homogeneous Spaces": http://web.math.princeton.edu/sarnak/NS-final-Oct-08.pdf).

I aim to find a similar result for the permanent. Of course, here I cannot use row operations. Running several thousands of examples on a computer, I suspect the following:

If $n=2^s -1$ for some integer $s\geq 2$ then $\text {perm}(A)\equiv 2^{n-s} (\mod 2^{n-s+1})$. If $2^s \leq n < 2^{s+1} -1$ then $\text {perm}(A)\equiv 0 (\mod 2^{n-s})$.

I have been able to show this (by tedious case analysis) for $n=3,4,5$. Namely, I already have that: $\text {perm}(A_{3\times 3})\equiv 2(\mod 4)$, $\text {perm}(A_{4\times 4})\equiv 0(\mod 4)$, $\text {perm}(A_{5\times 5})\equiv 0(\mod 8)$.

Any idea how to generalize this for any $n$, or if something like this has been done before?

Answer 1

Let us consider $s$ with $2^s\leq n<2^{s+1}$. First we prove the conjecture when all the entries of $A$ are $1$'s. Then $\mathrm{perm}(A)=n!$, hence by Legendre's formula the exponent of $2$ in it equals $n-t$, where $t$ is the number of $1$'s in the binary expansion of $n$. For $n=2^{s+1}-1$ we have $t=s+1$, hence the exponent equals $n-s-1$. For $2^s\leq n< 2^{s+1}-1$ we have $t\leq s$, hence the exponent is at least $n-s$.

For the general case we can assume that the statement holds for $n-1$. By the special case above, it suffices to show that if we increase by $2$ a single entry $a_{ij}$ of $A$, then the resulting matrix $B$ satisfies $$ \mathrm{perm}(B) \equiv \mathrm{perm}(A) \pmod{2^{n-s}}. $$ Clearly, $$ \mathrm{perm}(B) = \mathrm{perm}(A) + 2\mathrm{perm}(C),$$ where $C$ is the $(n-1)\times(n-1)$ matrix that results from $A$ by deleting the $i$-th row and the $j$-th column. Note that $2^s-1\leq n-1<2^{s+1}-1$, hence by the induction hypothesis we have $$ \mathrm{perm}(C) \equiv 0 \pmod{2^{n-1-s}}. $$ The claim follows, and we are done.