|
|
A085000
|
|
Maximal determinant of an n X n matrix using the integers 1 to n^2.
|
|
30
|
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Bounds for the next terms and the corresponding matrices are given by O. Gasper, H. Pfoertner and M. Sigg: 440960274696935 <= a(8) < 441077015225642, 346254605664223620 <= a(9) < 346335386150480625, 356944784622927045792 <= a(10) < 357017114947987625629. a(n) < sqrt(3*((n^5+n^4+n^3+n^2)/12)^n*(n^2+1)/(n+1)). - Hugo Pfoertner, Aug 15 2010
Improved lower bounds (private communication from Benjamin R. Buhrow, Dec 09 2019): a(8) >= 440970981670289, a(9) >= 346260899916111296. - Hugo Pfoertner, Jan 25 2021
Improved lower bound (private communication from Richard Gosiorovsky, Aug 18 2021): a(10) >= 356948996371054862392. - Hugo Pfoertner, Aug 24 2021
|
|
LINKS
|
|
|
EXAMPLE
|
The following 3 X 3 matrix is one of 36 whose determinant is 412 (there are also 36 whose determinant is -412):
9 3 5
4 8 1
2 6 7
Results from a specially adapted hill-climbing algorithm strongly suggest that a(5) = 6839492. a(6) is at least 1862125166. Heuristically, a(n) is approximately 0.44*n^(2.06*n), suggesting that a(7) is close to 6.8*10^11. - Tim Paulden (timmy(AT)cantab.net), Sep 21 2003
a(6) found with FORTRAN program given at Pfoertner link. A corresponding matrix is ((36 24 21 17 5 8) ( 3 35 25 15 23 11) (13 7 34 16 10 31) (14 22 2 33 12 28) (20 4 19 29 32 6) (26 18 9 1 30 27) ). - Hugo Pfoertner, Sep 23 2003
a(7) is the determinant of the matrix ((46 42 15 2 27 24 18) (9 48 36 30 7 14 31) (39 11 44 34 13 29 5) (26 22 17 41 47 1 21) (20 8 40 6 33 23 45) (4 28 19 25 38 49 12) (32 16 3 37 10 35 43)). Although no proof for the optimality of a(7) is available, the results of an extensive computational search make the existence of a better solution extremely unlikely. A total of approximately 15 CPU years on SGI Origin 3000 and of 3.8 CPU years on SGI Altix 3000 computers was used for this result.
|
|
MATHEMATICA
|
Needs["DiscreteMath`Combinatorica`"]; n=3; n2=n^2; dMax=0; mMax={}; p=Range[n2]; Do[m=Partition[p, n]; d=Det[m]; If[d>dMax, dMax=d; mMax=m]; p=NextPermutation[p], {k, n2!}]; {dMax, mMax} (* T. D. Noe *)
|
|
PROG
|
(PARI) vectomat(v)=my(n=sqrtint(#v)); matrix(n, n, i, j, v[n*(i-1)+j])
a(n)=my(m, t, M); n*=n; for(k=0, (n-1)!-1, t=matdet(M=vectomat(numtoperm(n, k))); if(abs(t)>m, m=abs(t); print(t" "M))); m \\ Charles R Greathouse IV, Sep 13 2013
|
|
CROSSREFS
|
Cf. A088214, A088215, A088216, A088217, A088237, A180087 [upper bounds for a(n)], A180128, A221976, A301371, A301532, A301533, A309985, A325900, A350566.
|
|
KEYWORD
|
nonn,nice,hard,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(4) from Marsac Laurent (jko(AT)rox0r.net), Sep 15 2003
Entry edited by N. J. A. Sloane, Nov 22 2006, to remove some erroneous entries. Further edits Nov 25 2006.
|
|
STATUS
|
approved
|
|
|
|