A003432 -id:A003432

A051752

Number of n X n (real) {0,1}-matrices having determinant A003432(n).

+20
6

1, 1, 3, 3, 60, 3600, 529200, 75600, 195955200, 13716864000

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

LINKS

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

Eric Weisstein's World of Mathematics, Hadamard's Maximum Determinant Problem.

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

Luke Zeng, Shawn Xin, Avadesian Xu, Thomas Pang, Tim Yang, Maolin Zheng, Seele's New Anti-ASIC Consensus Algorithm with Emphasis on Matrix Computation, arXiv:1905.04565 [cs.CR], 2019.

Miodrag Zivkovic, Classification of small (0,1) matrices, arXiv:math/0511636 [math.CO], 2005.

Miodrag Zivkovic, Classification of small (0,1) matrices, Linear Algebra and its Applications, 414 (2006), 310-346.

CROSSREFS

Cf. A003432, A046747, A086264, A089478, A188895.

KEYWORD

nonn,hard,more

AUTHOR

Eric W. Weisstein

EXTENSIONS

a(5) = 3600 from Daniel P. Corson (danl(AT)MIT.EDU), Jan 09 2000

a(6) = 529200, a(7) = 75600 from Ulrich Hermisson (uhermiss(AT)rz.uni-leipzig.de), Feb 25, 2003

More terms from Miodrag Zivkovic (ezivkovm(AT)matf.bg.ac.yu), Feb 28 2006

a(0)=1 prepended by Alois P. Heinz, Dec 20 2023

STATUS

approved

A089478

Triangle T(n,k) read by rows, where T(n,k) = number of times the determinant of a real n X n (0,1)-matrix takes the value k, for n >= 0, 0 <= k <= A003432(n).

+20
4

0, 1, 1, 1, 10, 3, 338, 84, 3, 42976, 10020, 1200, 60, 21040112, 4851360, 1213920, 144720, 43560, 3600, 39882864736, 9240051240, 3868663680, 768723480, 418703040, 63612360, 46569600, 6438600, 5014800, 529200, 292604283435872

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

COMMENTS

The first 4 rows were provided by Wouter Meeussen.

LINKS

Minfeng Wang, Table of n, a(n) for n = 0..118

EXAMPLE

a(4) = T(2,1) = 3 because there are 3 different (0,1)-matrices with determinant=1:

((1,0),(0,1)), ((1,1),(0,1)), ((1,0),(1,1)).

Triangle T(n,k) begins:

0, 1;

1, 1;

10, 3;

338, 84, 3;

42976, 10020, 1200, 60;

21040112, 4851360, 1213920, 144720, 43560, 3600;

...

PROG

(Fortran)

c See link in A086264.

CROSSREFS

Cf. T(n,0) = A046747(n), T(n,1) = A086264(n), T(n,A003432(n)) = A051752(n).

The n-th row of the table contains A089472(n) nonzero entries.

Cf. A089479.

KEYWORD

nonn,hard,tabf

AUTHOR

Hugo Pfoertner, Nov 04 2003

EXTENSIONS

Edited by Alois P. Heinz, Dec 20 2023

STATUS

approved

A094813

a(n) = number of (0,1) matrices of size n X n whose determinants are k, where -L <= k <= +L and L = A003432(n).

+20
0

1, 13, 10, 33, 84, 338, 84, 360, 1200, 10020, 42976, 10020, 12003600, 42795, 145485, 1206772, 4848581, 21059938, 4848585, 1206796, 145473, 42807, 3600

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

Table of n, a(n) for n=1..23.

J. Brenner, The Hadamard maximum determinant problem, Amer. Math. Monthly, 79 (1972), 626-630.

J. Williamson, Determinants whose elements are 0 and 1, Amer. Math. Monthly 53 (1946), 427-434. Math. Rev. 8,128g.

EXAMPLE

n = 2 : det([a b];[c d]) is (ad - bc) [16 possible matrices]

0 if ((a OR d) = zero) AND ((b OR c) = zero)

OR ((a AND d) = one) AND ((b AND D) = one) [10 possible matrices]

+1 if ((a AND d) = one) AND ((b OR c) = zero) [ 3 possible matrices]

-1 if ((a OR d) = zero) AND ((b AND c) = one) [ 3 possible matrices]

CROSSREFS

Cf. A003432, A003433.

KEYWORD

hard,nonn

AUTHOR

Patricia J. Egan (capdevcom(AT)lycos.com), Jun 11 2004

STATUS

approved

A007299

Number of Hadamard matrices of order 4n.
(Formerly M3736)

+10
24

1, 1, 1, 1, 5, 3, 60, 487, 13710027

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

COMMENTS

More precisely, number of inequivalent Hadamard matrices of order n if two matrices are considered equivalent if one can be obtained from the other by permuting rows, permuting columns and multiplying rows or columns by -1.

The Hadamard conjecture is that a(n) > 0 for all n >= 0. - Charles R Greathouse IV, Oct 08 2012

From Bernard Schott, Apr 24 2022: (Start)

A brief historical overview based on the article "La conjecture de Hadamard" (see link):

1893 - J. Hadamard proposes his conjecture: a Hadamard matrix of order 4k exists for every positive integer k (see link).

As of 2000, there were five multiples of 4 less than or equal to 1000 for which no Hadamard matrix of that order was known: 428, 668, 716, 764 and 892.

2005 - Hadi Kharaghani and Behruz Tayfeh-Rezaie publish their construction of a Hadamard matrix of order 428 (see link).

2007 - D. Z. Djoković publishes "Hadamard matrices of order 764 exist" and constructs 2 such matrices (see link).

As of today, there remain 12 multiples of 4 less than or equal to 2000 for which no Hadamard matrix of that order is known: 668, 716, 892, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, and 1964. (End)

By private email, Felix A. Pahl informs that a Hadamard matrix of order 1004 was constructed in 2013 (see link Djoković, Golubitsky, Kotsireas); so 1004 is deleted from the last comment. - Bernard Schott, Jan 29 2023

REFERENCES

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

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

S. Wolfram, A New Kind of Science. Champaign, IL: Wolfram Media, p. 1073, 2002.

LINKS

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

V. Alvarez, J. A. Armario, M. D. Frau and F. Gudlel, The maximal determinant of cocyclic (-1, 1)-matrices over D_{2t}, Linear Algebra and its Applications, 2011.

F. J. Aragon Artacho, J. M. Borwein, and M. K. Tam, Douglas-Rachford Feasibility Methods for Matrix Completion Problems, March 2014.

Dragomir Z. Djoković, Hadamard matrices of order 764 exist, arXiv:math/0703312 [math.CO], 2007.

Dragomir Z. Djoković, Oleg Golubitsky, and Ilias S. Kotsireas, Some new orders of Hadamard and skew-Hadamard matrices, arXiv:1301.3671 [math.CO], 2013.

Shalom Eliahou, La conjecture de Hadamard (I), Images des Mathématiques, CNRS, 2020.

Shalom Eliahou, La conjecture de Hadamard (II), Images des Mathématiques, CNRS, 2020.

Jacques Salomon Hadamard, Sur le module maximum que puisse atteindre un déterminant, C. R. Acad. Sci. Paris 116 (1893) 1500-1501 (link from Gallica).

Hadi Kharaghani, Home Page

Hadi Kharaghani and B. Tayfeh-Rezaie, Hadamard matrices of order 32, J. Combin. Designs 21 (2013) no. 5, 212-221. [DOI]

Hadi Kharaghani and B. Tayfeh-Rezaie, A Hadamard matrix of order 428, Journal of Combinatorial Designs, Volume 13, Issue 6, November 2005, pp. 435-440 (First published: 13 December 2004).

H. Kharaghani and B. Tayfeh-Rezaie, On the classification of Hadamard matrices of order 32, J. Combin. Des., 18 (2010), 328-336.

H. Kharaghani and B. Tayfeh-Rezaie, Hadamard matrices of order 32, 2012.

H. Kimura, Hadamard matrices of order 28 with automorphism groups of order two, J. Combin. Theory (1986), A 43, 98-102.

H. Kimura, New Hadamard matrix of order 24, Graphs Combin. (1989), 5, 235-242.

H. Kimura, Classification of Hadamard matrices of order 28 with Hall sets, Discrete Math. (1994), 128, 257-268.

H. Kimura, Classification of Hadamard matrices of order 28, Discrete Math. (1994), 133, 171-180.

W. P. Orrick, Switching operations for Hadamard matrices, arXiv:math/0507515 [math.CO], 2005-2007. (Gives lower bounds for a(8) and a(9))

N. J. A. Sloane, Tables of Hadamard matrices

N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).

Warren D. Smith, C program for generating Hadamard matrices of various orders

Edward Spence, Classification of Hadamard matrices of order 24 and 28, Discrete Math. 140 (1995), no. 1-3, 185-243.

Eric Weisstein's World of Mathematics, Hadamard Matrix

Index entries for sequences related to Hadamard matrices

CROSSREFS

Cf. A019442, A096201, A036297, A048615, A048616, A003432, A048885.

KEYWORD

hard,nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

a(8) from the H. Kharaghani and B. Tayfeh-Rezaie paper. - N. J. A. Sloane, Feb 11 2012

STATUS

approved

A003433

Hadamard maximal determinant problem: largest determinant of (+1,-1)-matrix of order n.
(Formerly M1291)

+10
12

1, 2, 4, 16, 48, 160, 576, 4096, 14336, 73728, 327680, 2985984, 14929920, 77635584, 418037760, 4294967296, 21474836480, 146028888064, 894426939392, 10240000000000, 59392000000000, 409600000000000

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

I added the entry for n=22 since this has been proved optimal by Chasiotis et al (reference in A003432). [Richard P. Brent, Aug 17 2021]

REFERENCES

Ed Hughes and Rob Pratt, New Features in SAS/OR 13.1, SAS Paper SAS256-2014.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

See A003432 for further references, links and formulas.

LINKS

Table of n, a(n) for n=1..22.

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

Thomas Decru, Tako Boris Fouotsa, Paul Frixons, Valerie Gilchrist, and Christophe Petit, Attacking trapdoors from matrix products, Cryptology ePrint Archive (2024) Paper 2024/1332.

Massimiliano Fasi and Gian Maria Negri Porzio, Determinants of Normalized Bohemian Upper Hessemberg Matrices, University of Manchester (England, 2019).

John Holbrook, Nathaniel Johnston, and Jean-Pierre Schoch, Real Schur norms and Hadamard matrices, arXiv:2206.02863 [math.CO], 2022.

Ion Nechita, Some analytical aspects of Hadamard matrices.

William P. Orrick and B. Solomon, Large-determinant sign matrices of order 4k+1, Discr. Math. 307 (2007), 226-236.

Eric Weisstein's World of Mathematics, -11-Matrix

Index entries for sequences related to binary matrices

Index entries for sequences related to Hadamard matrices

Index entries for sequences related to maximal determinants

FORMULA

a(n) = 2^(n-1)*A003432(n-1). E.g., a(6) = 32*A003432(5) = 32*5 = 160.

a(n) <= n^(n/2).

MATHEMATICA

A003432 = Cases[Import["https://oeis.org/A003432/b003432.txt", "Table"], {_, _}][[All, 2]];

a[n_] := 2^(n-1) A003432[[n]];

a /@ Range[21] (* Jean-François Alcover, Jan 17 2020 *)

CROSSREFS

A003432 is the main entry for this sequence.

Cf. A051753.

Cf. A188895 (number of distinct matrices having this maximal determinant).

KEYWORD

nonn,hard,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

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

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

STATUS

approved

A089472

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

+10
12

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

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

LINKS

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

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.

EXAMPLE

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}

CROSSREFS

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

KEYWORD

nonn,hard,more

AUTHOR

Hugo Pfoertner, Nov 04 2003

EXTENSIONS

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

STATUS

approved

A036297

Number of Hadamard matrices of order n.

+10
9

1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 5, 0, 0, 0, 3, 0, 0, 0, 60, 0, 0, 0, 487, 0, 0, 0, 13710027, 0, 0, 0

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,17

REFERENCES

See A007299 for references.

LINKS

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

See A007299 for links.

Index entries for sequences related to Hadamard matrices

Index entries for sequences related to maximal determinants

CROSSREFS

A007299 is the main entry for this sequence. Cf. A003432.

KEYWORD

nonn,nice,hard,more

AUTHOR

N. J. A. Sloane

EXTENSIONS

a(32) from the H. Kharaghani and B. Tayfeh-Rezaie paper. - N. J. A. Sloane, Feb 11 2012

STATUS

approved

A013588

Smallest positive integer not the determinant of an n X n {0,1}-matrix.

+10
8

2, 2, 3, 4, 6, 10, 19, 41, 103, 269

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

This majorizes the sequence of maximal determinants only up to the 6th term. It is conjectured that the sequence of maximal determinants majorizes this for all later terms.

The first term needing verification is a(11) >= 739. a(12) = 2173 has been verified by Brent, Orrick, Osborn, and Zimmermann in 2010. Lower bounds for the next terms: a(13) >= 6739, a(14) >= 21278, a(15) >= 69259, a(16) >= 230309. - Hugo Pfoertner, Jan 03 2020

LINKS

Table of n, a(n) for n=1..10.

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

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.

William P. Orrick, The maximal {-1, 1}-determinant of order 15, arXiv:math/0401179 [math.CO], 2004.

William P. Orrick, Spectrum of the determinant function.

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

G. R. Paseman, Related Material

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.

Index entries for sequences related to binary matrices

Index entries for sequences related to maximal determinants

EXAMPLE

There is no 3 X 3 {0,1}-matrix with determinant 3, as such a matrix must have a row with at least one 0 in it.

PROG

(Python)

from itertools import product

from sympy import Matrix

def A013588(n):

s, k = set(Matrix(n, n, p).det() for p in product([0, 1], repeat=n**2)), 1

while k in s:

k += 1

return k # Chai Wah Wu, Oct 01 2021

CROSSREFS

Cf. A003432, A089472.

KEYWORD

nice,more,hard,nonn

AUTHOR

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

EXTENSIONS

Extended by William Orrick, Jan 12 2006. a(7), a(8) and a(9) computed by Miodrag Zivkovic. a(7) and a(8) independently confirmed by Antonis Charalambides. a(10) computed by William Orrick.

STATUS

approved

A084109

n is congruent to 1 (mod 4) and is not the sum of two squares.

+10
8

21, 33, 57, 69, 77, 93, 105, 129, 133, 141, 161, 165, 177, 189, 201, 209, 213, 217, 237, 249, 253, 273, 285, 297, 301, 309, 321, 329, 341, 345, 357, 381, 385, 393, 413, 417, 429, 437, 453, 465, 469, 473, 489, 497

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

Alternatively, n is congruent to 1 (mod 4) with at least 2 distinct prime factors congruent to 3 (mod 4) in the squarefree part of n. - Comment corrected by Jean-Christophe Hervé, Oct 25 2015

Applications to the theory of optimal weighing designs and maximal determinants: An (n+1) X (n+1) conference matrix is impossible.

The upper bound of Ehlich/Wojtas on the determinant of a (0,1) matrix of order congruent to 1 (mod 4) cannot be achieved for n X n matrices.

The bound of Ehlich/Wojtas on the determinant of a (-1,1) matrix of order congruent to 2 (mod 4) cannot be achieved for (n+1) X (n+1) matrices.

Numbers with only odd prime factors, of which a strictly positive even number are raised to an odd power and congruent to 3 (mod 4). - Jean-Christophe Hervé, Oct 24 2015

REFERENCES

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, p. 56.

LINKS

Jean-Christophe Hervé, Table of n, a(n) for n = 1..1000

H. Ehlich, Determinantenabschätzungen für binäre Matrizen, Math. Z. 83 (1964) 123-132.

D. Raghavarao, Some aspects of weighing designs, Ann. Math. Stat. 31 (1960) 878-884.

EXAMPLE

a(1) = 3*7 = 21, a(2) = 3*11 = 33, a(3) = 3*19 = 57, a(14) = 3^3*7 = 189.

MAPLE

N:= 1000: # to get all entries <= N

S:= {seq(i, i=1..N, 4)} minus

{seq(seq(i^2+j^2, j=1..floor(sqrt(N-i^2)), 2), i=0..floor(sqrt(N)), 2)}:

sort(convert(S, list)); # Robert Israel, Oct 25 2015

MATHEMATICA

a[m_] := Complement[Range[1, m, 4], Union[Flatten[Table[j^2+k^2, {j, 1, Sqrt[m], 2}, {k, 0, Sqrt[m], 2}]]]]

PROG

(PARI) is(n)=if(n%4!=1, return(0)); my(f=factor(n)); for(i=1, #f~, if(f[i, 1]%4==3 && f[i, 2]%2, return(1))); 0 \\ Charles R Greathouse IV, Jul 01 2016

CROSSREFS

Cf. A000952, A003432, A003433, A022544, A001481.

KEYWORD

easy,nonn

AUTHOR

William P. Orrick, Jun 18 2003

STATUS

approved

A119002

Maximal determinant of real n X n symmetric (0,1) matrices.

+10
5

1, 1, 1, 2, 3, 5, 9, 18, 56, 144

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

The determinant of this 8 X 8 matrix is a(8) = 56:

{0, 1, 1, 1, 0, 1, 0, 0},

{1, 0, 1, 1, 0, 1, 0, 0},

{1, 1, 0, 1, 0, 0, 1, 1},

{1, 1, 1, 0, 1, 0, 0, 1},

{0, 0, 0, 1, 1, 1, 0, 1},

{1, 1, 0, 0, 1, 1, 1, 0},

{0, 0, 1, 0, 0, 1, 1, 1},

{0, 0, 1, 1, 1, 0, 1, 0}

and the determinant of this 9 X 9 matrix is a(9) = 144:

{1, 1, 0, 1, 1, 0, 0, 1, 1},

{1, 1, 1, 1, 0, 1, 0, 0, 0},

{0, 1, 1, 1, 0, 0, 1, 1, 1},

{1, 1, 1, 0, 1, 0, 1, 0, 1},

{1, 0, 0, 1, 0, 1, 1, 0, 1},

{0, 1, 0, 0, 1, 1, 1, 1, 0},

{0, 0, 1, 1, 1, 1, 0, 0, 1},

{1, 0, 1, 0, 0, 1, 0, 1, 1},

{1, 0, 1, 1, 1, 0, 1, 1, 0}. - Jean-François Alcover, Nov 18 2017

LINKS

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

Index entries for sequences related to maximal determinants

FORMULA

a(n) <= A003432(n).

CROSSREFS

Cf. A003432, A119003, A119004, A118998.

KEYWORD

nonn,more

AUTHOR

Giovanni Resta, May 08 2006

EXTENSIONS

a(8) and a(9) from Jean-François Alcover, Nov 18 2017

a(0)=1 prepended by Alois P. Heinz, Nov 18 2017

STATUS

approved