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

Research output: Contribution to journalArticleResearchpeer-review

12 Citations (Scopus)

Abstract

Let Λk n denote the set of (0, 1)-matrices of order n with exactly k ones in each row and column. Let Ji be such that Λi i = {Ji} and for A ∈ Λk n define Ā ∈ Λn-k n by Ā = Jn - A. We are interested in the matrices in Λk n which maximise the permanent function. Consider the sets Mn = {A ∈ Λk n: per(A) ≥ per(B), for all B ∈ Λk n}, M̄kn = {A ∈ Λk n: per(Ā) ≥ per(B̄), for all B ∈ Λk n}. For k fixed and n sufficiently large we prove the following results. 1. Modulo permutations of the rows and columns, every member of Mk n ∪ M̄k n is a direct sum of matrices of bounded size of which fewer than k differ from Jk. 2. A ∈ Mk n if and only if A ⊕ Jk ∈ Mk n+k. 3. A ∈ M̄k n if and only if A ⊕ Jk ∈ M̄k n+k. 4. M3n = M̄3n if n ≡ 0 or 1 (mod3) but M3n ∩ M̄3 n = ∅ if n ≡ 2(mod3). We also conjecture the exact composition of M̄k n for large n, which is equivalent to identifying regular bipartite graphs with the maximum number of 4-cycles.

Original languageEnglish
Pages (from-to)191-205
Number of pages15
JournalDiscrete Mathematics
Volume205
Issue number1-3
DOIs
Publication statusPublished - 28 Jul 1999
Externally publishedYes

Keywords

  • (0, 1)-matrices
  • Permanent
  • Regular bipartite graphs
  • Rook polynomials

Cite this