A381896 Number of n X n Erdős matrices up to equivalence.

1, 2, 6, 41

Offset: 1

Author

Raghavendra Tripathi, Mar 09 2025

Keywords

• nonn
• hard
• more

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].

Examples

			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.
		

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.

Crossrefs

Cf. A000041.