A003432 - OEIS (original) (raw)

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

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

Vasilis Chasiotis, Stratis Kounias, and Nikos Farmakis, The D-optimal saturated designs of order 22, Discrete Mathematics 341 (2018), 380-387. Corrigendum ibid 342 (2019), 2161.

H. Ehlich and K. Zeller, Binäre Matrizen, Zeit. Angew. Math. Mech., 42 (1962), 20-21. [broken link]

Eric Weisstein's World of Mathematics, (0, 1)-Matrix.

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