A lower bound on the maximum permanent in \(\Lambda_{n}^{k}\). (Q1414135)

Let \(\Lambda_n^k\) denote the set of square \((0,1)\)-matrices of order \(n\) with exactly \(k\) non-zero entries in each row and each column, \(P_n^k\) be the maximum value achieved by the permanent over \(\Lambda_n^k\). A theorem by \textit{L. M. Brégman} [Sov. Math., Dokl. 14, 945--949 (1973; Zbl 0293.15010)], shows that \(P_n^k\leq (k!)^{n/k}\). The author shows that \(P_n^k\geq (k!)^tr!\) where \(n=tk+r\), \(0\leq r<k\) and \((P_n^k)^{1/n}\sim (k!)^{1/k}\) whenever \(k=o(n)\). He provides a number of structural results concerning matrices which achieve \(P_n^k\). Some of these results support \textit{D. Merriell}'s conjectures [Linear Multilinear Algebra 9, 81--91 (1980; Zbl 0438.15009)], while some other show the limitations of Merriell's conjectures. In particular it is proved that for fixed \(t\) and large enough \(k\) the maximizing matrices in \(\Lambda_{2k+t}^k\) are either fully indecomposable or have two components whose orders differ by at most 1. Also it is shown that for each fixed \(r\geq 2\) there exists \(k_r\) such that the following holds for any given \(k>k_r\): (1) There are finitely many \(n\) for which maximizing matrices in \(\Lambda_n^k\) can contain a component from \(\Lambda_{k+c}^k\) for any \(c\) satisfying \(2\leq c\leq r\); (2) Maximizing matrices in \(\Lambda_{tk+r}^k \), where \(t\geq r\), are either isomorphic to block diagonal matrix with \((t-r)\) blocks \(J_k\) and \(r\) blocks \(D_{k+1}\) or contain fewer than \(t\) components; here \(J_k\) is the \(k\times k\) matrix of all ones and \(D_k\) is the \(k\times k\) matrix with zero entries on the main diagonal and 1 elsewhere. The author provides some examples where the best arrangement does not use the maximum possible number of \(J_k\)'s.