cp's OEIS Frontend

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

%I A013588 #52 Jul 10 2025 10:58:13
%S A013588 2,2,3,4,6,10,19,41,103,269
%N A013588 Smallest positive integer not the determinant of an n X n {0,1}-matrix.
%C A013588 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.
%C A013588 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
%C A013588 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
%H A013588 Swee Hong Chan and Igor Pak, <a href="https://arxiv.org/abs/2308.10214">Computational complexity of counting coincidences</a>, arXiv:2308.10214 [math.CO], 2023. See p. 18.
%H A013588 R. Craigen, <a href="https://www.researchgate.net/publication/265824172_The_range_of_the_determinant_function_on_the_set_of_nn_01-_matrices">The Range of the Determinant Function on the Set of n X n (0,1)-Matrices</a>, J. Combin. Math. Combin. Computing, 8 (1990) pp. 161-171.
%H A013588 William P. Orrick, <a href="https://arxiv.org/abs/math/0401179">The maximal {-1, 1}-determinant of order 15</a>, arXiv:math/0401179 [math.CO], 2004.
%H A013588 William P. Orrick, <a href="https://web.archive.org/web/20200215015425/http://www.indiana.edu/~maxdet/spectrum.html">Spectrum of the determinant function</a>.
%H A013588 G. R. Paseman, <a href="http://web.archive.org/web/20070211014636/http://grpmath.prado.com/icm98sl.html">A Different Approach to Hadamard's Maximum Determinant Problem</a>
%H A013588 G. R. Paseman, <a href="http://web.archive.org/web/20050215232056/http://grpmath.prado.com/icm.html">Related Material</a>
%H A013588 Rikhav Shah, <a href="https://doi.org/10.1016/j.laa.2022.03.024">Determinants of binary matrices achieve every integral value up to Ω(2^n/n)</a>, Linear Algebra and its Applications, Volume 645, 2022, pp. 229-236.
%H A013588 Miodrag Živković, <a href="http://poincare.matf.bg.ac.rs/~ezivkovm/publications/massive_computation.pdf">Massive computation as a problem solving tool</a>, in Proceedings of the 10th Congress of Yugoslav Mathematicians (Belgrade, 2001), pages 113-128. Univ. Belgrade Fac. Math., Belgrade, 2001.
%H A013588 Miodrag Živković, <a href="https://arxiv.org/abs/math/0511636">Classification of small (0,1) matrices</a>, arXiv:math/0511636 [math.CO], 2005.
%H A013588 <a href="/index/Mat#binmat">Index entries for sequences related to binary matrices</a>
%H A013588 <a href="/index/De#determinants">Index entries for sequences related to maximal determinants</a>
%e A013588 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.
%o A013588 (Python)
%o A013588 from itertools import product
%o A013588 from sympy import Matrix
%o A013588 def A013588(n):
%o A013588     s, k = set(Matrix(n,n,p).det() for p in product([0,1],repeat=n**2)), 1
%o A013588     while k in s:
%o A013588         k += 1
%o A013588     return k # _Chai Wah Wu_, Oct 01 2021
%Y A013588 Cf. A003432, A089472.
%K A013588 nice,more,hard,nonn
%O A013588 1,1
%A A013588 Gerhard R. Paseman (paseman(AT)prado.com)
%E A013588 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.