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

Author

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

Keywords

• nice
• more
• hard
• nonn

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

Asymptotically, the sequence is at least exponential as there is an exponential lower bound of a(n) >= 2^n / (201*n) due to Shah 2022. - Rikhav Shah, Jul 09 2025

Examples

			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.
		

Links

• 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
• Rikhav Shah, Determinants of binary matrices achieve every integral value up to Ω(2^n/n), Linear Algebra and its Applications, Volume 645, 2022, pp. 229-236.
• Miodrag Živković, 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.
• Miodrag Živković, 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

Crossrefs

Cf. A003432, A089472.

Programs

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

Extensions

Extended by William P. 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.