A003432 - OEIS

%I M0720 #106 Feb 16 2025 08:32:27

%S 1,1,1,2,3,5,9,32,56,144,320,1458,3645,9477,25515,131072,327680,

%T 1114112,3411968,19531250,56640625,195312500

%N Hadamard maximal determinant problem: largest determinant of a (real) {0,1}-matrix of order n.

%C The entries are restricted to 0 and 1; the determinant is computed in the field of real numbers.

%C Suppose M = (m(i,j)) is an n X n matrix of real numbers. Let

%C a(n) = max det M subject to m(i,j) = 0 or 1 [this sequence],

%C g(n) = max det M subject to m(i,j) = -1 or 1 [A003433],

%C h(n) = max det M subject to m(i,j) = -1, 0 or 1 [A003433],

%C F(n) = max det M subject to 0 <= m(i,j) <= 1 [this sequence],

%C G(n) = max det M subject to -1 <= m(i,j) <= 1 [A003433].

%C Then a(n) = F(n), g(n) = h(n) = G(n), g(n) = 2^(n-1)*a(n-1). Thus all five problems are equivalent.

%C Hadamard proved that a(n) <= 2^(-n)*(n+1)^((n+1)/2), with equality if and only if a Hadamard matrix of order n+1 exists. Equivalently, g(n) <= n^(n/2), with equality if and only if a Hadamard matrix of order n exists. It is believed that a Hadamard matrix of order n exists if and only if n = 1, 2 or a multiple of 4 (see A036297).

%C We have a(21) = 195312500?, a(22) = 662671875?, and a(36) = 1200757082375992968. Furthermore, starting with a(23), many constructions are known that attain the upper bounds of Hadamard, Barba, and Ehlich-Wojtas, and are therefore maximal. See the Orrick-Solomon web site for further information. [Edited by _William P. Orrick_, Dec 20 2011]

%C The entry a(21) = 195312500 is now known to be correct. [Edited by _Richard P. Brent_, Aug 17 2021]

%D J. Hadamard, Résolution d'une question relative aux déterminants, Bull. des Sciences Math. 2 (1893), 240-246.

%D F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 54.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Jan Brandts and A Cihangir, <a href="http://arxiv.org/abs/1512.03044">Enumeration and investigation of acute 0/1-simplices modulo the action of the hyperoctahedral group</a>, arXiv preprint arXiv:1512.03044 [math.CO], 2015.

%H J. Brenner, <a href="http://www.jstor.org/stable/2317092">The Hadamard maximum determinant problem</a>, Amer. Math. Monthly, 79 (1972), 626-630.

%H R. P. Brent, W. P. Orrick, J. Osborn, and P. Zimmermann, <a href="http://arxiv.org/abs/1112.4160">Maximal determinants and saturated D-optimal designs of orders 19 and 37</a>, arXiv:1112.4160 [math.CO], 2011. [From William P. Orrick, Dec 20 2011]

%H Richard P. Brent and Judy-anne H. Osborn, <a href="http://arxiv.org/abs/1208.3819">On minors of maximal determinant matrices</a>, arXiv preprint arXiv:1208.3819 [math.CO], 2012.

%H Swee Hong Chan and Igor Pak, <a href="https://arxiv.org/abs/2308.10214">Computational complexity of counting coincidences</a>, arXiv:2308.10214 [math.CO], 2023. See p. 18.

%H V. Chasiotis, S. Kounias, and N. Farmakis, <a href="https://dx.doi.org/10.1016/j.disc.2017.09.005">The D-optimal saturated designs of order 22</a>, Discrete Mathematics 341 (2018), 380-387. Corrigendum ibid 342 (2019), 2161.

%H H. Ehlich, <a href="http://dx.doi.org/10.1007/BF01111249">Determinantenabschätzungen für binäre Matrizen</a>, Math. Z. 83 (1964), 123-132.

%H H. Ehlich and K. Zeller, <a href="http://dx.doi.org/10.1002/zamm.19620421310">Binäre Matrizen</a>, Zeit. Angew. Math. Mech., 42 (1962), 20-21.

%H J. Freixas and S. Kurz, <a href="http://arxiv.org/abs/1112.2861">On alpha-roughly weighted games</a>, arXiv preprint arXiv:1112.2861 [math.CO], 2011.

%H Matthew Hudelson, Victor Klee and David Larman, <a href="https://doi.org/10.1016/0024-3795(95)00541-2">Largest j-simplices in d-cubes: some relatives of the Hadamard maximum determinant problem</a>, Proceedings of the Fourth Conference of the International Linear Algebra Society (Rotterdam, 1994). Linear Algebra Appl. 241/243 (1996), 519-598.

%H J. Huttenhain and C. Ikenmeyer, <a href="http://arxiv.org/abs/1410.8202">Binary Determinantal Complexity</a>, arXiv:1410.8202 [cs.CC], 2014-2015.

%H Yongbin Li, Junwei Zi, Yan Liu and Xiaojun Zhang, <a href="https://arxiv.org/abs/1905.04662">A note of values of minors for Hadamard matrices</a>, arXiv:1905.04662 [math.CO], 2019.

%H William P. Orrick, <a href="https://arxiv.org/abs/math/0401179">The maximal {-1, 1}-determinant of order 15</a>, arXiv:math/0401179 [math.CO], 2004.

%H William P. Orrick and B. Solomon, <a href="https://arxiv.org/abs/math/0311292">Large determinant sign matrices of order 4k+1</a>, arXiv:math/0311292 [math.CO], 2003.

%H William P. Orrick and B. Solomon, <a href="https://web.archive.org/web/20200219170713/http://www.indiana.edu/~maxdet/">The Hadamard Maximal Determinant Problem (website)</a>

%H William P. Orrick, B. Solomon, R. Dowdeswell and W. D. Smith, <a href="https://arxiv.org/abs/math/0304410">New lower bounds for the maximal determinant problem</a>, arXiv:math/0304410 [math.CO], 2003.

%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/sg.txt">My favorite integer sequences</a>, in Sequences and their Applications (Proceedings of SETA '98).

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html">Hadamard's maximum determinant problem.</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/01-Matrix.html">(0, 1)-Matrix</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/-101-Matrix.html">(-1, 0, 1)-Matrix</a>

%H J. Williamson, <a href="http://www.jstor.org/stable/2306240">Determinants whose elements are 0 and 1</a>, Amer. Math. Monthly 53 (1946), 427-434. Math. Rev. 8,128g.

%H Luke Zeng, Shawn Xin, Avadesian Xu, Thomas Pang, Tim Yang and Maolin Zheng, <a href="https://arxiv.org/abs/1905.04565">Seele's New Anti-ASIC Consensus Algorithm with Emphasis on Matrix Computation</a>, arXiv:1905.04565 [cs.CR], 2019.

%H Chuanming Zong, <a href="http://dx.doi.org/10.1090/S0273-0979-05-01050-5">What is known about unit cubes</a>, Bull. Amer. Math. Soc., 42 (2005), 181-211.

%H <a href="/index/Mat#binmat">Index entries for sequences related to binary matrices</a>

%H <a href="/index/Ha#Hadamard">Index entries for sequences related to Hadamard matrices</a>

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

%e G.f. = 1 + x + x^2 + 2*x^3 + 3*x^4 + 5*x^5 + 9*x^6 + 32*x^7 + 56*x^8 + ...

%e One of 2 ways to get determinant 9 with a 6 X 6 matrix, found by Williamson:

%e   1 0 0 1 1 0

%e   0 0 1 1 1 1

%e   1 1 1 0 0 1

%e   0 1 0 1 0 1

%e   0 1 0 0 1 1

%e   0 1 1 1 1 0

%Y A003433(n) = 2^(n-1)*a(n-1). Cf. A013588, A036297, A051752.

%K nonn,hard,more,nice,changed

%O 0,4

%A _N. J. A. Sloane_

%E a(18)-a(20) added by _William P. Orrick_, Dec 20 2011

%E a(21) added by _Richard P. Brent_, Aug 16 2021