Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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 –  Gerhard Paseman Jan 16 '13 at 19:11
    
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. –  Kevin P. Costello Jan 16 '13 at 20:27
    
I proved the conjecture in general, see below. –  GH from MO Jan 16 '13 at 20:37
add comment

1 Answer

up vote 9 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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