Some observations on Erdős matrices

Abstract

In a seminal paper in 1959, Marcus and Ree proved that every $n\times n$ bistochastic matrix $A$ satisfies $\Vert A{\Vert }_F^2\le {\max }_{\sigma \in S_n}{A}_{i,\sigma (i)}$ where $S_n$ is the symmetric group on $\{1,\dots ,n\}$. Erdős asked to characterize the bistochastic matrices for which the equality holds in the Marcus--Ree inequality. We refer to such matrices as Erdős matrices. While this problem is trivial in dimension $n=2$, the case of dimension $n=3$ was only resolved recently in~\cite{bouthat2024question} in 2023. We prove that for every $n$, there are only finitely many $n\times n$ Erdős matrices. We also give a characterization of Erdős matrices that yields an algorithm to generate all Erdős matrices in any given dimension. We also prove that Erdős matrices can have only rational entries. This answers a question of~\cite{bouthat2024question}.

15 pages; Fixed a small mistake in the main result; This is the accepted version in Linear algebra and its applications