Re Permanent conjecture
N. J. A. Sloane
njas at research.att.com
Wed Oct 29 22:41:53 CET 2003
I am posting this on behalf of John Goldwasser. - njas
>From jgoldwas at math.wvu.edu Wed Oct 29 15:30:54 2003
>Delivered-To: njas at research.att.com
>Date: Wed, 29 Oct 2003 15:30:01 -0500 (EST)
>From: John Goldwasser <jgoldwas at math.wvu.edu>
>To: eclark at math.usf.edu, <njas at research.att.com>
>Cc: John Goldwasser <jgoldwas at math.wvu.edu>
>Subject: Permanent conjecture
>X-Spam-Status: No, hits=-102.6 required=4.0
> tests=BAYES_20,USER_AGENT_PINE,USER_IN_ALL_SPAM_TO
> version=2.55
>X-Spam-Level:
>X-Spam-Checker-Version: SpamAssassin 2.55 (1.174.2.19-2003-05-19-exp)
>
>Neil and Edwin-
> Henry Gould, a colleague of mine, passed on to me the permanent
>conjecture from seqfan. Since I am not a member, my understanding is that
>I cannot send a message to be posted there, so I am sending it to you.
> First of all, it is easy to see that that 4x4 matrix with permanent
>equal to 8 is the essentially unique such matrix (any nonsing. (1,-1)
>matrix can be brought to that one by row and col. permutations and by
>multiplying rows and/or columns by -1. Perhaps a better canonical
>representative for this class is the matrix with all 1's except -1's on
>the main diagonal. To see that you could not have permanent more than 8
>you just note that:
>Any 3x3 (1,-1) matrix has abs. value of permanent equal to 2 or 6, and
>if it is 6 then the matrix is singular.
>2. If a 3x3 submatrix of a 4x4 (1,-1) matrix has permanent plus or minus 6
>then each two columns of the 3x3 are multiples of each other, so at least
>2 of these 3 columns in the 4x4 are multiples of each other, i.e. the 4x4
>is singular. So all 3x3 submatrices have permanent equal to plus or minus
>2. Given any 3x4 (1,-1) matrix with all 3x3 submatrices with permanent
>equal to plus or minus 2, clearly there is a unique way to choose the plus
>or minus 1's in one more row to make the permanent of the 4x4 matrix equal
>to 8 (and it can't be more than that).
>
>Let a(n) be the per. of an nxn (1,-1) matrix with all 1's except (n-1)
>-1's on main diagonal and let b(n) be the matrix with all 1.s except all
>-1's on the main diagonal. Clearly,
> a(n) = b(n) + 2b(n-1)
>It's not hard to get a recurrence relation for a(n) and b(n). More
>interesting is this:
>
>b(n) is equal to n! times Maclaurin's series for e^x with x=-2 truncated
>after the x^n term. When n=3 this gives 6 times -1/3, and this is the
>only place the partial sum is negative, so b(n) is negative only for n=3.
>
>So the fraction of random permutations of a large finite set which have an
>even number of fixed points minus the fraction which have an odd number of
>fixed points is 1/e^2 (exact in the limit).
>
>The well-known derangement numbers are the permanents of (0,1) matrices
>with all 1's except 0's on the main diagonal. The nth of these is
>precisely equal to the closest integer to n!/e. Who would have guessed
>that changing the 0's to -1's just divides again by e?
>
>As to the conjecture itself, it is easy to check it for n=5 (using 4x4
>cofactor matrices as in going from 3 to 4 above), and it is correct. I
>believe it is correct for larger n as well, though it may not be so easy
>to show it!
> John Goldwasser
>
More information about the SeqFan
mailing list