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

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∈Λnk define Ā∈Λnn−k by Ā=Jn−A. We are interested in the matrices in Λnk which maximise the permanent function. Consider the sets Mnk={A∈Λnk: per(A)⩾per(B), for all B∈Λnk},M̄nk={A∈Λnk: per(Ā)⩾per(B̄), for all B∈Λ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∪M̄nk is a direct sum of matrices of bounded size of which fewer than k differ from Jk. 2. A∈Mnk if and only if A⊕Jk∈Mn+kk. 3. A∈M̄nk if and only if A⊕Jk∈M̄n+kk. 4. Mn3=M̄n3 if n≡0 or 1 (mod 3) but Mn3∩M̄n3=∅ if n≡2 (mod 3).