Re Permanent conjecture

[N. J. A. Sloane]

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
>