# permanent of (-1,1) matrices

Gordon Royle gordon at csse.uwa.edu.au
Tue Oct 28 12:44:54 CET 2003

Do you want the sequence of permanents of this particular matrix [actually,
of this particular class of matrices because obviously independent
row/column permutations do not change its non-singularity or its permanent]
or the maximum permanent of a \pm 1 matrix?

The former is easy enough to compute a few terms for as follows, and
assuming the conjecture is true, the two sequences will be the same for all
n \geq 5.

Permanent of the nxn (+1,-1)-matrix  with exactly n-1 -1s on the diagonal
--------------------------------------------------------------------------

n=2    0
n=3    2
n=4    4
n=5    24
n=6    128
n=7    880
n=8    6816
n=9    60032
n=10    589312

Regarding the conjecture itself, it seems like one of those annoying ones
that are intuitively "obvious" but for which a proof is (obviously somewhat)
elusive....

The maximum permanent for any (-1,1) matrix is when the matrix is all 1s,
and then it is just n!. Clearly if we add "a few" -1s this will just reduce
the permanent and at least for a little while, the more -1s we add, the more
the permanent will be reduced. So given that n-1 is the smallest number
of -1s that we can add to get a non-singular matrix, it is not surprising
that this matrix would have the largest permanent...