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

1, 1, 1, 2, 3, 5, 9, 32, 56, 144, 320, 1458, 3645, 9477, 25515, 131072, 327680, 1114112, 3411968, 19531250, 56640625, 195312500

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• hard
• more
• nice

Comments

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

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

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

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

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

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

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

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.

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

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]

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

Examples

			G.f. = 1 + x + x^2 + 2*x^3 + 3*x^4 + 5*x^5 + 9*x^6 + 32*x^7 + 56*x^8 + ...
One of 2 ways to get determinant 9 with a 6 X 6 matrix, found by Williamson:
  1 0 0 1 1 0
  0 0 1 1 1 1
  1 1 1 0 0 1
  0 1 0 1 0 1
  0 1 0 0 1 1
  0 1 1 1 1 0
		

References

• J. Hadamard, Résolution d'une question relative aux déterminants, Bull. des Sciences Math. 2 (1893), 240-246.
• F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 54.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Jan Brandts and A Cihangir, Enumeration and investigation of acute 0/1-simplices modulo the action of the hyperoctahedral group, arXiv preprint arXiv:1512.03044 [math.CO], 2015.
• J. Brenner, The Hadamard maximum determinant problem, Amer. Math. Monthly, 79 (1972), 626-630.
• R. P. Brent, W. P. Orrick, J. Osborn, and P. Zimmermann, Maximal determinants and saturated D-optimal designs of orders 19 and 37, arXiv:1112.4160 [math.CO], 2011. [From William P. Orrick, Dec 20 2011]
• Richard P. Brent and Judy-anne H. Osborn, On minors of maximal determinant matrices, arXiv preprint arXiv:1208.3819 [math.CO], 2012.
• Swee Hong Chan and Igor Pak, Computational complexity of counting coincidences, arXiv:2308.10214 [math.CO], 2023. See p. 18.
• V. Chasiotis, S. Kounias, and N. Farmakis, The D-optimal saturated designs of order 22, Discrete Mathematics 341 (2018), 380-387. Corrigendum ibid 342 (2019), 2161.
• H. Ehlich, Determinantenabschätzungen für binäre Matrizen, Math. Z. 83 (1964), 123-132.
• H. Ehlich and K. Zeller, Binäre Matrizen, Zeit. Angew. Math. Mech., 42 (1962), 20-21.
• J. Freixas and S. Kurz, On alpha-roughly weighted games, arXiv preprint arXiv:1112.2861 [math.CO], 2011.
• Matthew Hudelson, Victor Klee and David Larman, Largest j-simplices in d-cubes: some relatives of the Hadamard maximum determinant problem, Proceedings of the Fourth Conference of the International Linear Algebra Society (Rotterdam, 1994). Linear Algebra Appl. 241/243 (1996), 519-598.
• J. Huttenhain and C. Ikenmeyer, Binary Determinantal Complexity, arXiv:1410.8202 [cs.CC], 2014-2015.
• Yongbin Li, Junwei Zi, Yan Liu and Xiaojun Zhang, A note of values of minors for Hadamard matrices, arXiv:1905.04662 [math.CO], 2019.
• William P. Orrick, The maximal {-1, 1}-determinant of order 15, arXiv:math/0401179 [math.CO], 2004.
• William P. Orrick and B. Solomon, Large determinant sign matrices of order 4k+1, arXiv:math/0311292 [math.CO], 2003.
• William P. Orrick and B. Solomon, The Hadamard Maximal Determinant Problem (website)
• William P. Orrick, B. Solomon, R. Dowdeswell and W. D. Smith, New lower bounds for the maximal determinant problem, arXiv:math/0304410 [math.CO], 2003.
• N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
• Eric Weisstein's World of Mathematics, Hadamard's maximum determinant problem.
• Eric Weisstein's World of Mathematics, (0, 1)-Matrix
• Eric Weisstein's World of Mathematics, (-1, 0, 1)-Matrix
• J. Williamson, Determinants whose elements are 0 and 1, Amer. Math. Monthly 53 (1946), 427-434. Math. Rev. 8,128g.
• Luke Zeng, Shawn Xin, Avadesian Xu, Thomas Pang, Tim Yang and Maolin Zheng, Seele's New Anti-ASIC Consensus Algorithm with Emphasis on Matrix Computation, arXiv:1905.04565 [cs.CR], 2019.
• Chuanming Zong, What is known about unit cubes, Bull. Amer. Math. Soc., 42 (2005), 181-211.
• Index entries for sequences related to binary matrices
• Index entries for sequences related to Hadamard matrices
• Index entries for sequences related to maximal determinants

Crossrefs

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

Extensions

a(18)-a(20) added by William P. Orrick, Dec 20 2011

a(21) added by Richard P. Brent, Aug 16 2021