Characterization of Erdös matrices by their zero entries

Abstract

An Erdös matrix $E$ is a bistochastic matrix whose sum of squares of entries (Frobenius norm squared) equals its maxtrace (maximum of all the $\ddot{I}ƒ$-traces for permutations $\ddot{I}ƒ$'s). We characterize all Erdös $E$ by the patterns of their zero entries; showing that each such skeleton has at most one $E$. We present an algorithm to find all $n\times n$ Erdös matrices, which finds them up to $n⩽5$ quickly and also size $n=6$. We further show some presently known RCDS matrices to be Erdös.