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

[Edwin Clark]

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.