Monotonicity toward the boundary

← Minc’s list

Minc’s list · Problem 8

Monotonicity toward the boundary

Open

Posed by
Friedland and Minc
First posed
1978

Statement

Posed by S. Friedland and H. Minc in 1978, in a paper on the monotonicity of permanents of doubly stochastic matrices; it is Problem 8 in Minc’s 1978 book.

Problem 8. Let \(\Omega_n\) be the set of \(n\times n\) doubly stochastic matrices and \(J_n\) the matrix with every entry \(1/n\). Find matrices \(A\) on the boundary of \(\Omega_n\) such that the permanent is monotone increasing on the segment

\[ (1-\theta)J_n+\theta A,\qquad 0\le\theta\le1. \]

The boundary consists of the matrices in \(\Omega_n\) with a zero entry. Since the monotonicity fails for some matrices, the problem asks, in effect, for a description of the boundary matrices with this property. Monotonicity implies Conjecture 4 for \(A\), and it forces \(\sigma_{n-1}(A)\le n^2\operatorname{per}A\), where \(\sigma_{n-1}\) is the sum of all permanental minors of order \(n-1\).

Prior progress

  • Monotonicity was proved for permutation matrices and related families (Friedland and Minc 1978), for \(\tfrac12(I_n+P_n)\) with \(P_n\) a full cycle (Sinkhorn 1980; London 1981), for all of \(\Omega_3\) and for \(J_s\oplus J_t\) (Lih and Wang 1981), and for further circulant families (London 1981).
  • Marcus and Minc (1968) proved it for normal matrices whose eigenvalues lie in the sector \(\lvert\arg z\rvert\le\pi/(2n)\). Hwang (1986, 1989) proved it for several structured families, for every symmetric positive semidefinite \(A\in\Omega_n\), and for all direct sums \(J_{n_1}\oplus\cdots\oplus J_{n_t}\).
  • Wanless (1999) disproved the Holens–Đoković conjecture. Those of his counterexamples that fail at the top order, such as one of order \(22\), are boundary directions along which the permanent is not monotone.

Our progress so far

  • Non-monotone examples in every order \(n\ge9\). For every \(n\ge9\) we constructed an explicit matrix \(B_n\) with entries in \(\{0,1,2\}\) and all line sums \(3\) such that \(3\,\sigma_{n-1}(B_n)>n^2\operatorname{per}B_n\). The permanent is therefore eventually decreasing along the segment towards \(A=B_n/3\). At \(n=9\), \(\operatorname{per}B_9=96\) and \(\sigma_8(B_9)=2640\). The smallest previously published example we know of has order \(22\).
  • Order five, sparse mixtures. Every convex combination of at most four \(5\times5\) permutation matrices has the monotonicity property.
  • Sparse supports. If every row and column of \(A\in\Omega_n\) has at most two nonzero entries, then \(\sigma_{n-1}(A)\le n^2\operatorname{per}A\), with equality exactly for \(\tfrac12(P+Q)\) where \(P^{-1}Q\) is a full cycle; in order five this gives monotonicity for all such matrices.

References

  1. S. Friedland and H. Minc, Monotonicity of permanents of doubly stochastic matrices, Linear and Multilinear Algebra 6 (1978/79), 227–231. doi:10.1080/03081087808817241
  2. M. Marcus and H. Minc, Extensions of classical matrix inequalities, Linear Algebra Appl. 1 (1968), 421–444. doi:10.1016/0024-3795(68)90018-9
  3. R. Sinkhorn, Concerning the question of monotonicity of the permanent on the doubly stochastic matrices, Linear and Multilinear Algebra 8 (1980), 323–328. doi:10.1080/03081088008817336
  4. K.-W. Lih and E. T. H. Wang, Monotonicity conjecture on permanents of doubly stochastic matrices, Proc. Amer. Math. Soc. 82 (1981), 173–178. doi:10.1090/S0002-9939-1981-0609645-5
  5. D. London, Monotonicity of permanents of certain doubly stochastic matrices, Pacific J. Math. 95 (1981), 125–131. doi:10.2140/pjm.1981.95.125
  6. S.-G. Hwang, On the monotonicity of the permanent, Proc. Amer. Math. Soc. 106 (1989), 59–63. doi:10.1090/S0002-9939-1989-0960645-2
  7. I. M. Wanless, The Holens–Đoković conjecture on permanents fails!, Linear Algebra Appl. 286 (1999), 273–285. doi:10.1016/S0024-3795(98)10177-5