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...
More information about the SeqFan
mailing list