Merris’s average-minor inequality

← Minc’s list

Minc’s list · Conjecture 18

Merris’s average-minor inequality

Open

Posed by
Merris
First posed
1973

Statement

Posed by R. Merris in 1973, in a short note on the permanent of a doubly stochastic matrix; it is Conjecture 18 in Minc’s 1978 book.

Conjecture 18. Let \(\Omega_n\) be the set of \(n\times n\) doubly stochastic matrices and let \(A(j\mid i)\) be \(A\) with row \(j\) and column \(i\) deleted. If \(A\in\Omega_n\), then

\[ n\operatorname{per}A\ \ge\ \min_{1\le i\le n}\ \sum_{j=1}^{n}\operatorname{per}A(j\mid i). \]

Expanding along column \(i\) gives \(\sum_j a_{ji}\operatorname{per}A(j\mid i)=\operatorname{per}A\), so the conjecture says that in some column the unweighted average of the permanental minors is at most their weighted average. Equality holds at \(J_n\).

Prior progress

  • For positive semidefinite symmetric \(A\in\Omega_n\) the inequality follows from an inequality of Marcus and Minc (1968), restated by Marcus and Merris (1973), which bounds the average of all the minors \(\operatorname{per}A(i\mid j)\) by \(\operatorname{per}A\).
  • Wanless (1999) found a matrix of order \(22\) that violates the stronger averaged inequality \(\sum_{i,j}\operatorname{per}A(j\mid i)\le n^2\operatorname{per}A\); it does not violate Merris’s inequality, whose minimum column remains safe.
  • Minc (1983, 1987) and Cheon and Wanless (2005) reported no progress; later papers give only sufficient conditions.

Our progress so far

  • Three-term circulants. For every \(n\ge3\) and \(x,y,z\ge0\), the matrix \((xI+yP+zP^{-1})/(x+y+z)\), where \(P\) is a cyclic permutation matrix, satisfies the inequality in every column.
  • Two-type block matrices. Every \(A\in\Omega_n\) that is constant on the blocks of a partition of the rows and of the columns into at most two classes satisfies the inequality, strictly unless \(A=J_n\) when all blocks are positive.
  • Near \(J_n\). The inequality holds on a neighbourhood of \(J_n\), with equality there only at \(J_n\).
  • Sparse patterns. The inequality holds in every column when each row and column of \(A\) has at most two nonzero entries. It also holds for \(\tfrac13(D+A_T)\) whenever \(T\) is a tree of maximum degree at most \(3\), where \(A_T\) is its adjacency matrix and \(D\) is diagonal with entries \(3-\deg v\).
  • No counterexample near Wanless’s matrix. All \(4{,}194{,}304\) two-fold lifts of Wanless’s order-\(22\) matrix to order \(44\) satisfy Merris’s inequality.

References

  1. R. Merris, The permanent of a doubly stochastic matrix, Amer. Math. Monthly 80 (1973), 791–793. doi:10.1080/00029890.1973.11993372
  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. M. Marcus and R. Merris, A relation between the permanental and determinantal adjoints, J. Austral. Math. Soc. 15 (1973), 270–271. doi:10.1017/S1446788700013173
  4. 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