Re Permanents of (+1,-1) matrices

N. J. A. Sloane njas at research.att.com
Tue Oct 28 15:54:42 CET 2003


Thanks to everyone who replied.  To summarize, let A
be a nonsingular +1,-1  n X n matrix.  The conjecture appears
to be that for n >= 5 the max permanent of A is given by
the following (new) sequence:

%I A087981
%S A087981 0,2,4,24,128,880,6816,60032,589312
%N A087981 Permanent of the n X n (+1,-1)-matrix with exactly n-1 -1s on the diagonal.
%C A087981 It is conjectured by Kraeuter and Seifter that for n >= 5 this is the maximum possible value for the permanent of a nonsingular n X n (+1,-1)-matrix with exactly n-1 -1's on the diagonal. 
%C A087981 I don't know for what values of n this has been confirmed. As Edwin Clark points out, it is certainly false for n = 4. - njas
%C A087981 The maximum possible value for the permanent of a singular n X n (+1,-1)-matrix is obviously n!.
%D A087891 A. R. Kraeuter and N. Seifter, Some properties of the permanent of (1,-1)-matrices,  Linear and Multilinear Algebra 15 (1984), 207-223.
%D A087981 N. Seifter, Upper bounds for permanents of (1,-1)-matrices, Israel J. Math. 48 (1984), 69-78.
%D A087891 Edward Tzu-Hsia  Wang, On permanents of (1,-1)-matrices, Israel J. Math. 18 (1974), 353-361.
%O A087981 2,2
%K A087981 nonn,easy,more
%A A087981 Gordon Royle (gordon(AT)csse.uwa.edu.au), Oct 28 2003

But what is the max permanent for n <= 4 ?  For 
n =  1  2  3  4    we have
     1  0  6  x     where thanks to Ed Clark we know x >= 8

It remains to see if 8 is the max permanent of a 4x4 nonsingular
+1,-1 matrix - could someone please do that computation?


NJAS





More information about the SeqFan mailing list