A lower bound on the maximum permanent in \(\Lambda_{n}^{k}\).
type: Item
instance of: scholarly article
title: A lower bound on the maximum permanent in \(\Lambda_{n}^{k}\).
zbMATH Open document ID: 1048.15010
DOI: 10.1016/S0024-3795(02)00715-2
published in: Linear Algebra and its Applications
publication date: 2003-11-19T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 15B36
Mathematics Subject Classification ID: 05B20
zbMATH DE Number: 2005978
zbMATH Keywords: permanent
zbMATH Keywords: \((0,1)\) matrix
zbMATH Keywords: Bregman bound
zbMATH Keywords: Merriell's conjectures
zbMATH Keywords: regular bipartite graph
zbMATH Keywords: Latin rectangle
author: Ian M. Wanless
reviewed by: Alexander Guterman
MaRDI profile type: Publication
cites work: Q3661894
cites work: Q4044717
cites work: Combinatorial matrix theory
cites work: Hermite polynomials and a duality relation for matchings polynomials
cites work: Asymptotic enumeration of Latin rectangles
cites work: Q5812325
cites work: Theory of monomer-dimer systems
cites work: A vector space analog of permutations with restricted position
cites work: Maximising the permanent of \((0,1)\)-matrices and the number of extensions of Latin rectangles
cites work: The maximum permanent in
cites work: Q5553636
cites work: Q4059363
cites work: Q3243274
cites work: Counting 1-factors in regular bipartite graphs
cites work: Maximising the permanent and complementary permanent of (0,1)-matrices with constant line sum
Recommended article: Q4789733
Recommended article: Q3487560
Recommended article: Q4484071
Recommended article: Q3734589
Recommended article: A lower bound for permanents of (0,1)-matrices
Recommended article: Permanents of Hessenberg (0,1)-matrices
Recommended article: An analytic approach to a permanent conjecture
Recommended article: On a combinatorial problem related to permanents
Recommended article: Extremal functions of excluded tensor products of permutation matrices
Recommended article: Matrices all of whose principal submatrices of some order have a nonzero permanent
description: scientific article; zbMATH DE number 2005978