login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003432 Hadamard maximal determinant problem: largest determinant of a (real) {0,1}-matrix of order n.
(Formerly M0720)
22
1, 1, 1, 2, 3, 5, 9, 32, 56, 144, 320, 1458, 3645, 9477, 25515, 131072, 327680, 1114112, 3411968, 19531250, 56640625, 195312500 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
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]
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.
EXAMPLE
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
CROSSREFS
A003433(n) = 2^(n-1)*a(n-1). Cf. A013588, A036297, A051752.
Sequence in context: A278119 A118998 A276410 * A179332 A081938 A129500
KEYWORD
nonn,hard,more,nice
AUTHOR
EXTENSIONS
a(18)-a(20) added by William P. Orrick, Dec 20 2011
a(21) added by Richard P. Brent, Aug 16 2021
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 01:57 EDT 2024. Contains 370952 sequences. (Running on oeis4.)