permanent of (-1,1) matrices

N. J. A. Sloane njas at research.att.com
Tue Oct 28 01:52:19 CET 2003


I came across this entry in MathSciNet:



MR0768267 (86b:15009) 
Seifter, Norbert(A-MNT) 
Upper bounds for permanents of (1,-1)-matrices. 
Israel J. Math. 48 (1984), no. 1, 69--78.

"It has been proposed by E. T.-H. Wang [same journal 18 (1974), 353--361; MR 50 #13077] to find a good upper bound for the permanent of an n\times n nonsingular (1,-1)-matrix. The
reason for the nonsingularity assumption is that without it the maximum value is clearly n!. A. R. Krauter and the author [Linear and Multilinear Algebra 15 (1984), no. 3, 207--223; MR
85j:15007] conjectured an upper bound, namely the permanent of the n\times n (1,-1)-matrix having exactly (n-1) -1's, these -1's being on the main diagonal, and proved that this
upper bound holds for a large class of nonsingular matrices. In this paper the upper bound is affirmed for another large class of nonsingular (1,-1)-matrices. Another upper bound, weaker than the
above, is deduced for the permanents of a large class of (1,-1)-matrices, some of which are singular."


In other words, there is a conjecture that the max permanent of an n X n
(-1,1)-matrix is given by the permanent of the
matrix having exactly (n-1) -1's, these -1's being on the main diagonal.

Neither the Wang not the Seifter references are in the OEIS.

Could someone please compute these numbers, and tell me the
sequence number (if present), or add it as a new sequence if not?

Thanks!

Neil

(and tell the list if you are going to do it,
to avoid duplication)





More information about the SeqFan mailing list