Real van der Waerden radius

← Minc’s list

Minc’s list · Problem 13

Real van der Waerden radius

Open

Posed by
Sinkhorn
First posed
1981

Statement

Posed by R. Sinkhorn in 1981, in a paper on neighbourhoods of \(J_n\) in which the van der Waerden bound holds; it is Problem 13 in Minc’s 1983 survey.

Problem 13. Determine the largest number \(b=b(n)\) such that \(\operatorname{per}A\ge n!/n^n\) for all real \(n\times n\) matrices \(A\) all of whose row and column sums are equal to \(1\) and which satisfy \(\lVert J_n-A\rVert\le b\).

Here \(J_n\) is the matrix with every entry \(1/n\), and the entries of \(A\) may be negative, which is what separates this from van der Waerden’s theorem. The catalogue does not name the norm; we use the Frobenius norm \(\lVert X\rVert_F=\bigl(\sum_{i,j}x_{ij}^2\bigr)^{1/2}\) throughout.

Prior progress

  • Sinkhorn (1981) found an explicit neighbourhood of \(J_n\) in which \(\operatorname{per}A>n!/n^n\) for doubly stochastic \(A\ne J_n\), before van der Waerden’s conjecture was proved.
  • Gyires (1980) showed that the bound holds on a short initial segment of every line from \(J_n\), with a length depending on the direction, which gives no uniform radius.
  • Every real line-sum-one matrix within Frobenius distance \(1/(n-1)\) of \(J_n\) is nonnegative, so the van der Waerden theorem (Egorychev; Falikman 1981) covers that ball. Cheon and Wanless (2005) reported no progress on the sharp radius.

Our progress so far

  • Order three, exactly. \(b(3)=3\sqrt2/4\approx1.0607\). In fact every real \(3\times3\) matrix \(X\) with zero line sums satisfies the sharp inequality \[ \operatorname{per}(J_3+X)-\tfrac29\ \ge\ \frac{\lVert X\rVert_F^2}{6}-\frac{2\lVert X\rVert_F^3}{9\sqrt2}, \] and the only matrices on the boundary with permanent \(\tfrac29\) are the six matrices \(\tfrac74J_3-\tfrac34P\), where \(P\) is a permutation matrix.
  • Order four, exactly. \(b(4)=\sqrt{\rho_4}=1.16144933\ldots\), where \(\rho_4\) is an explicitly isolated root of a polynomial of degree \(8\).
  • Order five. \(0.255\le b(5)\le1.19156\), with the upper bound attained by an explicit algebraic matrix of degree \(13\).
  • All orders. \(b(n)>1/(n-1)\) for every \(n\ge3\), and \(b(n)\ge\dfrac{51}{50(n-1)}\) for every \(n\ge5\).

References

  1. R. Sinkhorn, A neighborhood in which the van der Waerden permanent conjecture is valid, Linear and Multilinear Algebra 10 (1981), 217–221. doi:10.1080/03081088108817413
  2. H. Minc, Theory of permanents 1978–1981, Linear and Multilinear Algebra 12 (1983), 227–263. doi:10.1080/03081088308817488
  3. B. Gyires, The common source of several inequalities concerning doubly stochastic matrices, Publ. Math. Debrecen 27 (1980), 291–304. doi:10.5486/PMD.1980.27.3-4.15
  4. G. P. Egorychev, The solution of van der Waerden’s problem for permanents, Adv. Math. 42 (1981), 299–305. doi:10.1016/0001-8708(81)90044-X
  5. D. I. Falikman, Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix, Math. Notes 29 (1981), 475–479. doi:10.1007/BF01163285