Skip to main content

Merris’s average-minor inequality

← Minc’s list

Minc’s list · Conjecture 18

Merris’s average-minor inequality

Proved by others Proof posted in September 2026

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\).

Resolution

The conjecture is now proved in every order.

Dongyang Liu posted a proof on Zenodo on 13 September 2026, in a working preprint that comes with a formalization in the Lean 4 proof assistant; the preprint says that OpenAI Codex assisted with the proof. It establishes more. Write \(S_i=\sum_{j=1}^{n}\operatorname{per}A(j\mid i)\). Then every row-stochastic matrix \(A\) with positive entries satisfies

\[ \operatorname{per}A\,\sum_{i=1}^{n}\frac{1}{S_i}\ \ge\ 1, \]

and hence \(n\operatorname{per}A\ge\min_i S_i\) for every nonnegative row-stochastic matrix, with no condition on the column sums. We audited the written argument independently and found no gap.

We had proved the inequality in every order for several families of doubly stochastic matrices: three-term circulants, two-type block matrices and some sparse patterns. Our work has not been posted.

Read the proof ↗

Earlier 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 gave only sufficient conditions.
  • Jinhui Li (August 2026) posted on GitHub a proof of the case \(n=4\), formalized in the Lean proof assistant. It goes through the averaged inequality \(\sum_{i,j}\operatorname{per}A(j\mid i)\le 16\operatorname{per}A\) for \(A\in\Omega_4\).

References

  1. D. Liu, A harmonic cofactor inequality for row-stochastic matrices, working preprint (13 September 2026). doi:10.5281/zenodo.22735117
  2. J. Li, Merris’ conjecture in dimension four, Lean 4 formalization (2026). github.com/123ljh0bot/Merris-Conjecture-in-Dimension-Four
  3. R. Merris, The permanent of a doubly stochastic matrix, Amer. Math. Monthly 80 (1973), 791–793. doi:10.1080/00029890.1973.11993372
  4. 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
  5. 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
  6. 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