13
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ By tweaking J, the matrix of all ones, you can establish some weak upper bounds, such as getting (n-1)! times (n+2k) for the permanent. You might be able to tweak more than one row to lower the factorial term and get (n+k2^s) for small s and odd k . Gerhard "Ask Me About System Design" Paseman, 2013.01.16 $\endgroup$ Jan 16, 2013 at 19:11
  • $\begingroup$ Perfect proved a similar result for $\pm 1$ matrices in his "Positive Diagonals of $\pm 1$ Matrices" (he mentions the connection to the permanent in the concluding remarks to his paper). I don't know if his proof carries over or not, but it may be worth looking at. $\endgroup$ Jan 16, 2013 at 20:27
  • $\begingroup$ I proved the conjecture in general, see below. $\endgroup$
    – GH from MO
    Jan 16, 2013 at 20:37

1 Answer 1

10
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.