login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

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
1, 1, 1, 2, 3, 5, 9, 32, 56, 144, 320, 1458, 3645, 9477, 25515, 131072, 327680, 1114112, 3411968, 19531250, 56640625 (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. - Jon E. Schoenfield, Sep 07 2015

REFERENCES

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

Hudelson, Matthew; Klee, Victor and Larman, David, 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.

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

Table of n, a(n) for n=0..20.

Jan Brandts, A Cihangir, Enumeration and investigation of acute 0/1-simplices modulo the action of the hyperoctahedral group, arXiv preprint arXiv:1512.03044, 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.

Richard P. Brent and Judy-anne H. Osborn, On minors of maximal determinant matrices, arXiv preprint arXiv:1208.3819, 2012.

H. Ehlich, Determinantenabschaetzungen fuer binaere Matrizen, Math. Z. 83 (1964), 123-132.

H. Ehlich and K. Zeller, Binaere Matrizen, Zeit. Angew. Math. Mech., 42 (1962), 20-21.

J. Freixas and S. Kurz, On alpha-roughly weighted games, arXiv preprint arXiv:1112.2861, 2011

J. Huttenhain, C. Ikenmeyer, Binary Determinantal Complexity, arXiv:1410.8202 [cs.CC], 2014-2015.

W. P. Orrick, The maximal {-1, 1}-determinant of order 15.

W. P. Orrick and B. Solomon, Large determinant sign matrices of order 4k+1

W. P. Orrick and B. Solomon, The Hadamard Maximal Determinant Problem (website)

W. P. Orrick, B. Solomon, R. Dowdeswell and W. D. Smith, New lower bounds for the maximal determinant problem

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.

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

EXAMPLE

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

100110

001111

111001

010101

010011

011110

CROSSREFS

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

Sequence in context: A094206 A118998 A276410 * A179332 A081938 A129500

Adjacent sequences:  A003429 A003430 A003431 * A003433 A003434 A003435

KEYWORD

nonn,hard,more,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Added a(18)-a(20). Jon E. Schoenfield, Jan 31 2015

Edited by William P. Orrick, Dec 20 2011

STATUS

approved

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 December 9 14:26 EST 2016. Contains 278971 sequences.