|
|
A003432
|
|
Hadamard maximal determinant problem: largest determinant of a (real) {0,1}-matrix of order n.
(Formerly M0720)
|
|
24
|
|
|
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
|
H. Ehlich and K. Zeller, Binäre Matrizen, Zeit. Angew. Math. Mech., 42 (1962), 20-21.
|
|
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
|
|
|
KEYWORD
|
nonn,hard,more,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|