Some results towards the Dittert conjecture on permanents
type: Item
instance of: scholarly article
title: Some results towards the Dittert conjecture on permanents
zbMATH Open document ID: 1239.15004
author: Gi-Sang Cheon
author: Ian M. Wanless
published in: Linear Algebra and its Applications
publication date: 2012-03-08T00:00:00Z
review text: The Dittert conjecture says the following. Let \(A=(a_{ij})\) be an \(n\times n\) martix. Consider the function \[ \phi(A)=\prod_{i=1}^n\sum_{j=1}^n a_{ij}+\prod_{j=1}^n\sum_{i=1}^n a_{ij}-per(A), \] and define \(J_n\) to be a matrix all whose entries equal \(\frac{1}{n}\). Dittert conjectured that for a real nonnegative \(n\times n\) matrix \(A\) with entries sum \(n\) one has \[ \phi(A)\leq 2-\frac{n!}{n^n}, \] with equality if and only if \(A=J_n\). The Dittert conjecture is still open for \(n\geq 4\). This conjecture generalizes the van der Waerden conjecture. The problem was to find the minimun of \(per(A)\) on the set of matrices with all row and column sums equal to \(1\) (these matrices are called stochastic matrices). This problem was solved by Egorycev and Falikman [\textit{G. P. Egorychev}, Adv. Math. 42, 299--305 (1981; Zbl 0478.15003); \textit{D. I. Falikman}, Math. Notes 29, 475--479 (1981); translation from Mat. Zametki 29, 931--938 (1981; Zbl 0475.15007)]. In particular they proved that the matrix with the minimal permanent is \(J_n\). In the Dittert conjecture a larger set of matrices than in the van der Waerden conjecture is considered; if one restricts to the set of stochastic matrices then the Dittert conjecture follows from the van der Waerden conjecture. Several partial results on the Dittert conjecture were obtained by \textit{R. Sinkhorn} [Linear Multilinear Algebra 16, 167--173 (1984; Zbl 0568.15004)], \textit{S. G. Hwang} [Linear Algebra Appl. 76, 31--44 (1986; Zbl 0589.15016); ibid. 95, 161--169 (1987; Zbl 0628.15018)], \textit{G.-S. Cheon} and \textit{H.-W. Yoon} [Int. Math. Forum 1, No. 37--40, 1943--1949 (2006; Zbl 1306.15008)]. The main results of the paper under review are the following. If \(A\) is partially decomposable, then \(\phi(A)\leq \phi(J_n)\). If the zeroes in \(A\) form a block then \(A\) is not a \(\phi\)-maximizing matrix. One has \(\phi(A)<\phi(J_n)\) unless \(\delta:=per(J_n)-per(A)\leq O(n^4e^{-2n})\) and \[ |k-\sum_{…
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 15B51
zbMATH DE Number: 6013285
zbMATH Keywords: Dittert conjecture
zbMATH Keywords: doubly superstochastic matrices
zbMATH Keywords: van der Waerden conjecture
zbMATH Keywords: minimal permanent
Wikidata QID: Q123023749
reviewed by: Dmitry Artamonov
MaRDI profile type: Publication
full work available at URL: j.laa.2010.08.041
OpenAlex ID: W2020052858
cites work: Maximization of a matrix function related to the Dittert conjecture
cites work: A note on the Dittert conjecture for permanents
cites work: An update on Minc's survey of open problems involving permanents
cites work: An interpretation of the Dittert conjecture in terms of semi-matchings
cites work: Q4745951
cites work: Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
cites work: A note on a conjecture on permanents
cites work: On a conjecture of E. Dittert
cites work: Random access communication and graph entropy
cites work: On certain convex matrix sets
cites work: Theory of permanents 1982–1985
cites work: A problem related to the van der waerden permanent theorem*
DOI: 10.1016/J.LAA.2010.08.041
Recommended article: A note on the Dittert conjecture for permanents
Recommended article: A note on a conjecture on permanents
Recommended article: A conjecture on permanents
Recommended article: Research problems
Recommended article: On some permanental conjectures
Recommended article: Q3312366
Recommended article: On two permanental conjectures
Recommended article: On a conjecture about the μ-permanent
Recommended article: On the Dinitz conjecture and related conjectures
Recommended article: A result on Dillon's conjecture in difference sets
description: scientific article; zbMATH DE number 6013285