A note on Erdős matrices and Marcus\unicode{x2013}Ree inequality

Abstract

In 1959, Marcus and Ree proved that any bistochastic matrix $A$ satisfies ${\Delta }_n(A):={\max }_{\sigma \in S_n}{\sum }_{i=1}^{n}A(i,\sigma (i))-{\sum }_{i,j=1}^{n}A(i,j{)}^2\ge 0$. Erdős asked to characterize the bistochastic matrices satisfying ${\Delta }_n(A)=0$. This problem remains largely open, and very recently, a complete list of such matrices was obtained in dimension $n=3$ by Bouthat, Mashreghi, and Morneau-Guérin. Soon after, Tripathi proved that there were only finitely many such matrices in any dimension $n$. In this paper, we continue the investigation initiated in these two works. We characterize all $4\times 4$ bistochastic matrices satisfying ${\Delta }_4(A)=0$. Furthermore, we show that for $n\ge 3$, ${\Delta }_n(A)=\alpha$ has uncountably many solutions when $\alpha \in (0,(n-1)/4)$. This answers a question raised in [Tripathi, R., $\text{Some observations on Erdo˝s matrices}$, Linear Algebra and Its Applications 708 (2025)]. We also extend the Marcus\unicode{x2013}Ree inequality to infinite bistochastic arrays and bistochastic kernels. Our investigation into $4\times 4$ Erdős matrices also leads to several intriguing questions of independent interest. We propose several questions and conjectures and present numerical evidence for them.

20 pages + appendix (2 pages); 3 tables; Minor changes to improve readability and correction of typos; This is the accepted version in Linear Algebra and its Applications