OFFSET
1,2
COMMENTS
An n X n bistochastic matrix A is Erdős if Sum_{i=1..n} Sum_{j=1..n} A(i, j)^2 = max_{p in S_n} Sum_{i=1..n} A(i, p(i)), where S_n is the set of all permutations of [n]. It is known that any bistochastic matrix satisfies the inequality Sum_{i=1..n} Sum_{j=1..n} A(i, j)^2 <= max_{p in S_n} Sum_{i=1..n} A(i, p(i)).
Two Erdős matrices A and B are equivalent if A=PBQ for some permutation matrices P and Q.
The n-th term in the sequence a(n) >= p(n), where p(n) is the number of partitions of n [Tripathi, 2024].
LINKS
Ludovick Bouthat, Javad Mashreghi, and Frédéric Morneau-Guérin, On a question of Erdős on doubly stochastic matrices, Linear and Multilinear Algebra, Vol 72, (17) 2024, 2823-2844; arXiv preprint arXiv:2306.05518 [math.MG], 2023.
Aman Kushwaha and Raghavendra Tripathi, A note on Erdős matrices and Marcus--Ree inequality, arXiv:2503.09542 [math.MG], 2025.
Raghavendra Tripathi, Some observations on Erdős matrices, Linear Algebra and its Applications, Vol 708, 2025, 236-251; arXiv preprint arXiv:2410.06612 [math.MG], 2024.
EXAMPLE
When n=1, there is only one bistochastic matrix, namely [1], which is clearly Erdős. This gives a(1)=1.
When n=2, there are only 3 Erdős matrices, namely [1, 0; 0, 1], [1/2, 1/2; 1/2, 1/2], and [0, 1; 1, 0]. Since [1, 0; 0, 1] and [0, 1; 1, 0] are equivalent, it follows that a(2)=2.
When n=3, there are only 6 Erdős matrices up to equivalence. This was shown by Bouthat, Mashreghi, and Morneau-Guérin in 2024. Here is a list of 6 non-equivalent Erdős matrices in dimension 3:
[1, 0, 0; 0, 1, 0; 0, 0, 1],
[1/3, 1/3, 1/3; 1/3, 1/3, 1/3; 1/3, 1/3, 1/3],
[1, 0, 0 ; 0, 1/2, 1/2; 0, 1/2, 1/2],
[0 , 1/2, 1/2; 1/2, 1/4, 1/4; 1/2, 1/4, 1/4],
[0, 1/2, 1/2; 1/2, 0, 1/2; 1/2, 1/2, 0],
[3/5, 0, 2/5; 0, 3/5, 2/5; 2/5, 2/5, 1/5]
A complete list 41 of non-equivalent Erdős matrices in dimension 4 was obtained by Kushwaha and Tripathi.
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Raghavendra Tripathi, Mar 09 2025
STATUS
approved