login
This site is supported by donations 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)
19

%I M0720

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

%T 1114112,3411968,19531250,56640625

%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]

%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, 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 H. Ehlich, <a href="http://dx.doi.org/10.1007/BF01111249">Determinantenabschaetzungen fuer binaere Matrizen</a>, Math. Z. 83 (1964), 123-132.

%H H. Ehlich and K. Zeller, <a href="http://dx.doi.org/10.1002/zamm.19620421310">Binaere 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, 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, C. Ikenmeyer, <a href="http://arxiv.org/abs/1410.8202">Binary Determinantal Complexity</a>, arXiv:1410.8202 [cs.CC], 2014-2015.

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

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

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

%H W. P. Orrick, B. Solomon, R. Dowdeswell and W. D. Smith, <a href="http://arXiv.org/abs/math.CO/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="http://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html">Hadamard's maximum determinant problem.</a>

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

%H Eric Weisstein's World of Mathematics, <a href="http://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 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

%O 0,4

%A _N. J. A. Sloane_

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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified February 24 15:37 EST 2018. Contains 299623 sequences. (Running on oeis4.)