A013588 -id:A013588 - cp's OEIS frontend

A003432 Hadamard maximal determinant problem: largest determinant of a (real) {0,1}-matrix of order n.

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

Offset: 0

N. J. A. Sloane

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]

			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

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

Jan Brandts and 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.
Swee Hong Chan and Igor Pak, Computational complexity of counting coincidences, arXiv:2308.10214 [math.CO], 2023. See p. 18.
V. Chasiotis, S. Kounias, and N. Farmakis, The D-optimal saturated designs of order 22, Discrete Mathematics 341 (2018), 380-387. Corrigendum ibid 342 (2019), 2161.
H. Ehlich, Determinantenabschätzungen für binäre Matrizen, Math. Z. 83 (1964), 123-132.
H. Ehlich and K. Zeller, Binäre 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.
Matthew Hudelson, Victor Klee and David Larman, 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.
J. Huttenhain and C. Ikenmeyer, Binary Determinantal Complexity, arXiv:1410.8202 [cs.CC], 2014-2015.
Yongbin Li, Junwei Zi, Yan Liu and Xiaojun Zhang, A note of values of minors for Hadamard matrices, arXiv:1905.04662 [math.CO], 2019.
William P. Orrick, The maximal {-1, 1}-determinant of order 15, arXiv:math/0401179 [math.CO], 2004.
William P. Orrick and B. Solomon, Large determinant sign matrices of order 4k+1, arXiv:math/0311292 [math.CO], 2003.
William P. Orrick and B. Solomon, The Hadamard Maximal Determinant Problem (website)
William 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.
Luke Zeng, Shawn Xin, Avadesian Xu, Thomas Pang, Tim Yang and Maolin Zheng, Seele's New Anti-ASIC Consensus Algorithm with Emphasis on Matrix Computation, arXiv:1905.04565 [cs.CR], 2019.
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

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

a(18)-a(20) added by William P. Orrick, Dec 20 2011

a(21) added by Richard P. Brent, Aug 16 2021

A089472 Number of different values taken by the determinant of a real (0,1)-matrix of order n.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 19, 43, 91, 227, 587

Offset: 0

Hugo Pfoertner, Nov 04 2003

Lower bounds: a(11) >= 1623, a(12) >= 4605, a(13) >= 14365, a(14) >= 44535, a(15) >= 145273, a(16) >= 476947

			a(7)=43 because a 7X7 (0,1)-matrix A_7 can produce the values abs(det(A_7))= {0,1,...,17,18,20,24,32}

R. Craigen, The Range of the Determinant Function on the Set of n X n (0,1)-Matrices, J. Combin. Math. Combin. Computing, 8 (1990) pp. 161-171.
W. P. Orrick, The maximal {-1, 1}-determinant of order 15.
Gerhard R. Paseman, Partial Proof of the Determinant Spectrum for 7x7 0-1 Matrices.
Miodrag Zivkovic, Massive computation as a problem solving tool, In Proceedings of the 10th Congress of Yugoslav Mathematicians (Belgrade, 2001), pages 113-128. Univ. Belgrade Fac. Math., Belgrade, 2001.
M. Zivkovic, Classification of small (0,1) matrices, arXiv:math/0511636 [math.CO], 2005.

Cf. A003432 (largest determinant of (0, 1)-matrix), A013588 (smallest integer not representable as determinant of (0, 1)-matrix), A089478 (occurrence counts), A087983 (number of different values taken by permanent of (0, 1)-matrix).

a(1)..a(4) from Wouter Meeussen.
a(7) verified by Gordon F. Royle.
Extended by William Orrick, Jan 12 2006. a(8) and a(9) computed by Miodrag Zivkovic. a(8) independently confirmed by Antonis Charalambides. a(10) computed by William Orrick.
Edited by Max Alekseyev, May 02 2011
a(0)=1 prepended by Alois P. Heinz, Mar 16 2019

A089477 Smallest positive integer not the permanent of a real {0,1}-matrix of order n.

Original entry on oeis.org

2, 3, 5, 13, 27, 119, 737, 5153

Offset: 1

Hugo Pfoertner, Nov 05 2003

a(6) from Gordon F. Royle.

			a(2)=3 because {0,1,2} are expressible as permanents of (0, 1)-matrices.

Swee Hong Chan and Igor Pak, Computational complexity of counting coincidences, arXiv:2308.10214 [math.CO], 2023. See p. 4.

Cf. A089479 occurrence counts for permanents of (0, 1)-matrices, A087983 number of different values taken by permanent of (0, 1)-matrix, A013588 smallest number not expressible as determinant of (0, 1)-matrix.

a(7) from Giovanni Resta, Mar 29 2006

a(8) from Minfeng Wang, Oct 04 2024

A108150 Number of different nonnegative values taken by the determinant of a real (0,1)-matrix of order n.

Original entry on oeis.org

1, 2, 2, 3, 4, 6, 10, 22, 46, 114, 294

Offset: 0

William P. Orrick, Jan 12 2006

For references and links see A089472.

A089472 is the main entry for this sequence. Cf. A003432, A013588, A051236.

a(1)=2, a(n) = (A089472(n) + 1) / 2 for n>1

a(0)=1 prepended by Alois P. Heinz, Mar 17 2019

A373916 Numbers that are the determinant of real {0,1}-matrices of order 10, but not of symmetric such matrices.

Original entry on oeis.org

253, 268, 274, 294, 304

Offset: 1

Hugo Pfoertner, Jun 25 2024

This property also applies to the corresponding negative values.

William P. Orrick, Spectrum of the determinant function, (2010). The applicable part is "Spectrum for n=11" because of the representation for {-1,1}-matrices.
Hugo Pfoertner, Positions of the terms in a histogram of the accumulated occurrence counts.

Cf. A003432, A006125, A013588, A089472, A108150, A118985, A373915.

A051236 Largest integer a(n) for which the integer interval [ 0,a(n) ] is a subset of the set of determinants of all n X n 0-1 matrices.

Original entry on oeis.org

1, 1, 2, 3, 5, 9, 18, 40, 102, 268

Offset: 1

Gerhard R. Paseman (paseman(AT)prado.com)

A definition for a(n) is given in Craigen's paper. The table given there suggests a(9)=102. Term for term, this sequence is one less than the sequence A013588.

			There is a 7x7 0-1 matrix with determinant 20, but no 7x7 0-1 matrix with determinant 19.

R. Craigen, The Range of the Determinant Function on the Set of n X n (0,1)-Matrices, J. Combin. Math. Combin. Computing, 8 (1990) pp. 161-171.

G. R. Paseman, A Different Approach to Hadamard's Maximum Determinant Problem

Cf. A013588.

a(n) = A013588(n) - 1

Extended by William Orrick, Jan 12 2006

A215644 Full spectrum threshold for maximal determinant {+1, -1} matrices: largest order of submatrix for which the full spectrum of absolute determinant values occurs.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 6, 4, 6, 6, 7, 6, 7, 7, 7, 8, 8, 8, 9, 8, 10

Offset: 1

Richard P. Brent and Judy-anne Osborn, Aug 18 2012

a(n) is the maximum of m(A) taken over all maximal determinant matrices A of order n, where m(A) is the maximum m such that the full spectrum of possible values (ignoring sign) occurs for the minors of order m of A.

			For n = 8 we have a(8) = 4 as a Hadamard matrix of order 8 has minors of order 4 with the full spectrum of values {0,8,16} (signs are ignored) but minors of order m > 4 do not have this property.

R. P. Brent, The Hadamard Maximal Determinant Problem
Richard P. Brent and Judy-anne H. Osborn, On minors of maximal determinant matrices, arXiv:1208.3819, 2012.
Index entries for sequences related to maximal determinants

Cf. A003432, A003433, A013588.

We calculated the first 21 terms of the sequence by an exhaustive computation of minors of known maximal determinant matrices as at August 2012.

cp's OEIS Frontend

A003432 Hadamard maximal determinant problem: largest determinant of a (real) {0,1}-matrix of order n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A089472 Number of different values taken by the determinant of a real (0,1)-matrix of order n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A089477 Smallest positive integer not the permanent of a real {0,1}-matrix of order n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A108150 Number of different nonnegative values taken by the determinant of a real (0,1)-matrix of order n.

Views

Author

Keywords

References

Crossrefs

Formula

Extensions

A373916 Numbers that are the determinant of real {0,1}-matrices of order 10, but not of symmetric such matrices.

Views

Author

Keywords

Comments

Links

Crossrefs

A051236 Largest integer a(n) for which the integer interval [ 0,a(n) ] is a subset of the set of determinants of all n X n 0-1 matrices.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A215644 Full spectrum threshold for maximal determinant {+1, -1} matrices: largest order of submatrix for which the full spectrum of absolute determinant values occurs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions