login
Maximum determinant of an n X n matrix with n copies of the numbers 1 .. n.
18

%I #39 Nov 04 2020 17:10:02

%S 1,1,3,18,160,2325,41895,961772,27296640,933251220

%N Maximum determinant of an n X n matrix with n copies of the numbers 1 .. n.

%C 929587995 <= a(9) <= 934173632 (upper bound from Gasper's determinant theorem). The lower bound corresponds to a Latin square provided in A309985, but it is unknown whether a larger determinant value can be achieved by an unconstrained arrangement of the matrix entries. - _Hugo Pfoertner_, Aug 27 2019

%C Oleg Vlasii found a 9 X 9 matrix significantly exceeding the determinant value achievable by a Latin square. See example and links. - _Hugo Pfoertner_, Nov 04 2020

%H Ortwin Gasper, Hugo Pfoertner and Markus Sigg, <a href="http://www.emis.de/journals/JIPAM/article1119.html">An Upper Bound for the Determinant of a Matrix with given Entry Sum and Square Sum</a>, JIPAM, Journal of Inequalities in Pure and Applied Mathematics, Volume 10, Issue 3, Article 63, 2008.

%H IBM Research, <a href="https://www.research.ibm.com/haifa/ponderthis/challenges/November2019.html">Large 9x9 determinant</a>, Ponder This Challenge November 2019.

%H Markus Sigg, <a href="https://arxiv.org/abs/1804.02897">Gasper's determinant theorem, revisited</a>, arXiv:1804.02897 [math.CO], 2018.

%H Oleg Vlasii, <a href="https://github.com/OlegV567/Determinant-OEIS-A301371-9">Determinant-OEIS-A301371-9</a>, program and description, 4 Dec 2019.

%H <a href="/index/De#determinants">Index entries for sequences related to maximal determinants</a>

%F A328030(n) <= a(n) <= A328031(n). - _Hugo Pfoertner_, Nov 04 2019

%e Matrices with maximum determinants:

%e a(2) = 3:

%e (2 1)

%e (1 2)

%e a(3) = 18:

%e (3 1 2)

%e (2 3 1)

%e (1 2 3)

%e a(4) = 160:

%e (4 3 2 1)

%e (1 4 3 2)

%e (3 1 4 3)

%e (2 2 1 4)

%e a(5) = 2325:

%e (5 3 1 2 4)

%e (2 5 4 1 3)

%e (4 1 5 3 2)

%e (3 4 2 5 1)

%e (1 2 3 4 5)

%e a(6) = 41895:

%e (6 1 4 2 3 5)

%e (3 6 2 1 5 4)

%e (4 5 6 3 2 1)

%e (5 3 1 6 4 2)

%e (1 2 5 4 6 3)

%e (2 4 3 5 1 6)

%e a(7) = 961772:

%e (7 2 3 5 1 4 6)

%e (3 7 6 4 2 1 5)

%e (2 1 7 6 4 5 3)

%e (4 5 1 7 6 3 2)

%e (6 3 5 1 7 2 4)

%e (5 6 4 2 3 7 1)

%e (1 4 2 3 5 6 7)

%e a(8) = 27296640:

%e (8 8 3 5 4 3 4 1)

%e (1 8 6 3 1 6 6 5)

%e (5 3 8 1 7 6 4 2)

%e (5 1 6 8 2 4 7 3)

%e (1 5 2 7 8 6 4 3)

%e (7 3 2 4 3 8 2 7)

%e (5 4 2 2 6 2 8 7)

%e (4 5 7 6 5 1 1 7)

%e a(n) is an upper bound for the determinant of an n X n Latin square. a(n) = A309985(n) for n <= 7. a(8) > A309985(8). - _Hugo Pfoertner_, Aug 26 2019

%e From _Hugo Pfoertner_, 2020 Nov 04: (Start)

%e a(9) = 933251220, achieved by a Non-Latin square:

%e (9 5 5 3 3 2 2 8 8)

%e (4 9 2 6 7 5 3 1 8)

%e (4 7 9 2 1 8 6 3 5)

%e (6 3 7 9 4 1 8 2 5)

%e (6 2 8 5 9 7 1 4 3)

%e (7 4 1 8 2 9 5 6 3)

%e (7 6 3 1 8 4 9 5 2)

%e (1 8 6 7 5 3 4 9 2)

%e (1 1 4 4 6 6 7 7 9)

%e found by Oleg Vlasii as an answer to the IBM Ponder This Challenge November 2019. See links. (End)

%Y Cf. A085000, A309985, A328030, A328031.

%K nonn,hard,more

%O 0,3

%A _Hugo Pfoertner_, Mar 21 2018

%E a(8) from _Hugo Pfoertner_, Aug 26 2019

%E a(9) from _Hugo Pfoertner_, Nov 04 2020