Maximising the permanent and complementary permanent of (0,1) matrices with constant line sum

Let Λnk denote the set of (0,1)-matrices of order n with exactly k ones in each row and column. Let Ji be such that Λii={Ji} and for A in Λnk define comp{A} in Λnn-k by comp{A}=Jn-A. We are interested in the matrices in Λnk which maximise the permanent function. Consider the sets

Mnk={A in Λnk: per(A)≥per(B), for all B in Λnk},

Cnk={A in Λnk: per(comp{A})≥per(comp{B}), for all B in Λnk}.

For k fixed and n sufficiently large we prove the following results.

  1. Modulo permutations of the rows and columns, every member of Mnk union Cnk is a direct sum of matrices of bounded size of which fewer than k differ from Jk.
  2. A in Mnk if and only if A direct sum Jk is in Mn+kk.
  3. A in Cnk if and only if A direct sum Jk is in Cn+kk.
  4. Mn3=Cn3 if n=0 or 1 (mod 3) but Mn3 intersect Cn3 is the emptyset if n=2 (mod 3).
We also conjecture the exact composition of Cnk for large n, which is equivalent to identifying regular bipartite graphs with the maximum number of 4-cycles.

Click here to download the whole paper.