permanent of (-1,1) matrices
Edwin Clark
eclark at math.usf.edu
Tue Oct 28 05:38:48 CET 2003
On Mon, 27 Oct 2003, N. J. A. Sloane wrote:
>
> 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)
There seems to a problem here:
Consider the following two matrices: Each is followed by its determinant
and then its permanent. (Calculated with Maple 9)
[-1 -1 1 1]
[ ]
[ 1 1 1 1]
[ ], 16, 8
[ 1 -1 1 -1]
[ ]
[-1 1 1 -1]
[1 1 1 1]
[ ]
[1 -1 1 1]
[ ], -8, 4
[1 1 -1 1]
[ ]
[1 1 1 -1]
According to the abstract above the permanent of the second matrix should
be an upper bound. But the first one has a larger permanent. Am I missing
something. If not this is a counter-example to the conjecture. ??
Or is there a bug here in Maple?
Would someone else please check this.
--Edwin
More information about the SeqFan
mailing list