maximum permanent of (0,1)-matrices with various conditions

[Edwin Clark]

---------- Forwarded message ----------
Date: Fri, 14 Nov 2003 18:25:30 -0600
From: Pante Stanica <pstanica at mail.aum.edu>

Hello,

    My email address has changed from the seqfan-registered stanica at strudel.aum.edu to pstanica at mail.aum.edu, so I cannot post directly to seqfan (but I am being forwarded the messages). So, please post this on seqfan, if you will.

   Regarding the maximum/minimum values of the permanents of (0,1)-matrices: I just returned from MCCCC03 (Midwest Conference on Combinatorics, Computing and Cryptography at Univ. of Nevada at Las Vegas) where Seok-Zun Song (Cheju National Univ., Korea) gave a talk on Max/Min permanents of (0,1)-matrices. He followed one of his papers from Linear Algebra and Applic. Volume 373, 1 November 2003, Pages 197-210, where he determines "exactly" those values for matrices having a fixed no. of zeros. He gave me a copy of the paper. I skimmed through it in the airport, but I haven't looked carefully at all the results. It seems though that the problem may have been solved now.

Best,
Pante Stanica
Auburn Univ. Montgomery
Mathematics Department


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Dr. Pantelimon Stanica
Mathematics Department 
Auburn University Montgomery
Montgomery, AL 36124-4023
http://sciences.aum.edu/~stanica

----- Original Message -----
From: Edwin Clark <eclark at math.usf.edu>
Date: Friday, November 14, 2003 4:28 pm
Subject: maximum permanent of (0,1)-matrices with various conditions

> 
> For anyone interested in the sequences discussed previously 
> concerning the
> maximum permanet of an nxn non-singular (0,1)-matrix here is an 
> update:
> My solutions were correct but lacked rigorous proof. I just submitted
> the following proofs (to Neil) obtained with the help of Richard 
> Brualdi:
> Both are based on the following paper
> 
> [1] Brualdi, Richard A.; Goldwasser, John L.; Michael, T. S. 
> Maximum permanents of matrices of zeros and ones. 
> J. Combin. Theory Ser. A 47 (1988), no. 2, 207--245.
> 
> Corollary 4.4 in this paper says:
> 
> --------------------------------------------------------------
> Let n and t be integers with n >=4 and 0 <=t <= n. Let m(n,t) be
> the maximum permanent of an nxn (0,1)-matrix with exactly t 0's.
> Then m(n,t) = per D where D is  the nxn (0,1)-matrix with exactly 
> t  0's
> all of which lie on the main diagonal. Moreover, if A is an nxn
> (0,1)-matrix with exactly t 0's and  per A = m(n,t) then A is
> combinatorially equivalent to D, i.e., permuting rows and columns 
> of A
> gives D. 
> ----------------------------------------------------------------
> This can be applied to show that for n >=4 then m(n,n-1) is
> the maximum permanent of an nxn NONSINGULAR (0,1) matrix:
> 
> Proof Let n >=4. Take an nxn (0,1)-matrix A which is nonsingular. 
> It has
> t, at least n-1, 0's. Otherwise there will be two rows of all 1's. 
> Let B
> be the matrix obtained from A by replacing t-(n-1) of A's 0's with
> 1's. Let D be the matrix with all 1's except for 0's in the first 
> n-1
> positions on the diagonal. This matrix is easily seen to be
> non-singular. Now we have 
>                 per(A) < =  per(B) < =  per (D),
> where the first inequality follows since replacing 0's by 1's cannot
> decrease the permanent, and the second from Corollary 4.4 in [1] which
> shows that per(D) is the maximum permanent of ANY nxn matrix with 
> n -1
> 0's.  Corollary 4.4 requires n >=4.  a(n) for n < 4 can be computed
> directly. 
> 
> 
> And for n>=4 from Corollary 4.4 above it is now easy to see that the
> number of nonsingular nxn (0,1) matrices A with per A = m(n,n-1) 
> is n*n!.
> 
> --Edwin
> 
> 
> PS There are more sequences to be obtained from the above 
> corollary if
> anyone has the energy to find them. In fact, in the above paper by
> Brualdi, et al, results analogous to this corollary are given for
> the maximum permanent of nxn (0,1)-matrices with exactly t 0's for
> t satisfying 0 <= t <= 2n. See Theorem 2.3 in the paper.
> 
>