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
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. [Edited by William P. Orrick, Dec 20 2011]

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

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 [math.CO], 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, arXiv:math/0401179 [math.CO], 2004.

W. P. Orrick and B. Solomon, Large determinant sign matrices of order 4k+1, arXiv:math/0311292 [math.CO], 2003.

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

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

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:

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

a(18)-a(20) added 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 January 24 08:39 EST 2017. Contains 281234 sequences.