Maximising the permanent and complementary permanent of (0,1) matrices with constant line sum
Let Λ_{n}^{k} denote the set of (0,1)matrices
of order n with exactly k ones in each row and column. Let
J_{i} be such that
Λ_{i}^{i}={J_{i}} and for
A in Λ_{n}^{k} define
comp{A} in Λ_{n}^{nk} by comp{A}=J_{n}A. We
are interested in the matrices in Λ_{n}^{k}
which maximise the permanent function. Consider the sets
M_{n}^{k}={A in Λ_{n}^{k}:
per(A)≥per(B), for all B in Λ_{n}^{k}},
C_{n}^{k}={A in Λ_{n}^{k}:
per(comp{A})≥per(comp{B}), for all
B in Λ_{n}^{k}}.
For k fixed and n sufficiently large we prove the following results.
 Modulo permutations of the rows and columns, every member of
M_{n}^{k} union C_{n}^{k} is a direct
sum of matrices of bounded size of which fewer than k differ from
J_{k}.
 A in M_{n}^{k} if and only if A direct sum
J_{k} is in M_{n+k}^{k}.
 A in C_{n}^{k} if and only if A direct sum
J_{k} is in C_{n+k}^{k}.

M_{n}^{3}=C_{n}^{3} if n=0 or 1
(mod 3) but M_{n}^{3} intersect
C_{n}^{3} is the emptyset if n=2 (mod 3).
We also conjecture the exact composition of C_{n}^{k}
for large n, which is equivalent to identifying regular bipartite
graphs with the maximum number of 4cycles.
Click here to download the whole paper.