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

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

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.

Sequence in context: A329695 A103599 A032245 * A108150 A066015 A065482

Adjacent sequences: A013585 A013586 A013587 * A013589 A013590 A013591

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