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?



Permanent of a matrix of odd integers
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](http://www.cut-the-knot.org/wiki-math/index.php?n=Arithmetic.LegendresFormula) 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.


