Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. The site's commentary credits B. Gyires [Gy80], The common source of several inequalities concerning doubly stochastic matrices, with a proof of van der Waerden's conjecture: every doubly stochastic n×nn\times n matrix XX satisfies per⁡(X)≥n!/nn\operatorname{per}(X)\ge n!/n^n. By averaging the n!n! diagonal products, that conjecture would give the statement of Problem 499. The paper does not prove the conjecture. Its Theorems 1.1–1.4 are inequalities for weighted sums of permanental quantities of (AA∗)1/2(AA^*)^{1/2}, (A∗A)1/2(A^*A)^{1/2} and AA, not bounds on per⁡(A)\operatorname{per}(A). On p. 293, van der Waerden's conjecture appears as a special case of the paper's own Conjectures 1.3 and 1.5. Corollaries 3.3 and 3.4 (pp. 299–300) give those conjectures for symmetric positive semidefinite matrices. Section 4 (p. 301) says the author could not prove them for arbitrary doubly stochastic matrices, beyond the cases k=1,2k=1,2 of Conjecture 1.1 (Theorems 4.5 and 4.6). Theorem 4.9 and Corollary 4.1 (p. 304) give the bound only for the matrices (1−x)A0+xA(1-x)A_0+xA with 0<x≤δ0<x\le\delta, where A0A_0 has every entry 1/n1/n. The paper ends by showing the conjecture equivalent to its Conjecture 4.1, which it leaves open. It proves no lower bound on the permanent of an arbitrary doubly stochastic matrix.

Why the attribution is rejected. The publication the site cites, Publ. Math. Debrecen 27 (1980), no. 3-4, 291–304, does not contain the theorem credited to it. Van der Waerden's conjecture was proved by Egorychev and Falikman, and the problem's statement by Marcus and Minc. The rejection concerns the attribution; the paper's own theorems are not in question.