Do determinants of binary matrices form a set of consecutive numbers?

While pondering a solution for the problem of generating random 0-1 matrices with small absolute determinants, I once again realise how little I know about 0-1 matrices. My initial idea was to pick a random determinant, construct a 0-1 matrix to match this determinant and then permute the matrix's rows and columns. But I quickly abandoned this idea because I simply know no way to construct a 0-1 matrix with a given determinant.

In fact, I don't even know how large the determinant of a 0-1 matrix can be. The Hadamard's bound for the absolute determinant of an $n\times n$ 0-1 matrix is $\frac{(n+1)^{(n+1)/2}}{2^n}$ (online ref. 1 and ref. 2), and the bound is sharp if and only if there exists a Hadamard matrix of order $n+1$. Yet, to my knowledge, there is no known sharp upper bound for the absolute determinant of a general $n\times n$ 0-1 matrix.

While I have abandoned the aforementioned idea, the determinants of 0-1 matrices still intrigues me. So, here is my question:

Let ${\cal B}^{n\times n}$ denotes the set of all $n\times n$ 0-1 matrices and let $M=\max_{A\in B}\det A$. Is it true that for every $d\in\{0,1,\ldots,M\}$, there exists $A\in{\cal B}^{n\times n}$ such that $\det(A)=d$?

For $n\le6$, the answer is positive, but I have no idea about the general case. Edit: The answer doesn't need to be complete. If this question has been recognised as an open problem in the literature, I am glad to know the references.

Solution 1:

For size 7 it was proved by Metropolis, Stein, and Wells that the set of non-negative determinant values is $[0,18]\cup\{20,24,32\}$, which means that the answer to your question in the gray box is no. See this paper:

N. Metropolis, , Spectra of determinant values in (0, 1) matrices. In A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory: Proceedings of the Science Research Atlas Symposium No. 2 held at Oxford, from 18-23 August, 1969, pages 271–276, London, 1971. Academic Press.

For general size, the data I have suggest that the set of determinant values is "dense" up to about half of Hadamard's bound and sparse thereafter, but I have no argument why that should be the case. And my data only go up to size 22. Who knows what happens in size 200?

Here are some entries in the OEIS that might be helpful.

• A003432 - maximimal determinants of n-by-n binary matrix
• A089472 - number of different values taken by the determinant of n-by-n binary matrix
• A013588 - smallest positive integer not the determinant of an n-by-n binary matrix.

I gave a talk couple of years ago, Range and distribution of determinants of binary matrices (available here), in which I discussed this topic. That discussion starts on slide 27, but other parts of the talk may also be relevant to your question.

I've also created a web page listing determinant values that have been constructed in matrix sizes up to 16. These lists are proved to be complete in sizes up to 10 and also in size 12, but I believe that the lists are probably complete in the other sizes as well. Be careful: my page discusses $\{-1,1\}$-matrices. You'll have to subtract 1 from the matrix size if you're interested in $\{0,1\}$-matrices.

See also the Mathworld and Wikipedia pages on Hadamard's maximal determinant problem. Also relevant are the papers of Tao and Vu mentioned in my slides. There is recent work on lower bounds on the maximal determinant by Brent, Osborn, and Smith. You can find these on the arXiv.

Solution 2:

I love these questions that I feel I know the answer yet can not yet prove, because usually it leads to some great education if not a proof. My short answer is yes, it is true. At this moment I can only say that I would bet reputation points on it if we could do such a thing.

I believe the values are contiguous at the low end, but not at the high end. For example, for $10 \times 10$ matrices, the highest determinants are $315$ and $320$, but I have found none in between. My search method (make entire row or column changes at a time with maximum change in determinant) possibly could have skipped some, but I don't think so.

The larger the $d$, the more difficult the problem. For $d$ small, consider your approach you gave to the other question where you iterate $$A \leftarrow \pmatrix{A & \mathbf{b} \\ \mathbf{c} & g}$$

Since this iterates determinant $$\det(A) \leftarrow \det(A)(g - \mathbf{c}A^{-1}\mathbf{b}) $$

you know that once a smaller matrix $A$ is found with the determinant $d$ that the size may be built up while retaining the determinant, using your approach from the other question.

In order to be able to find for a large $d$, my intuition would be that the vectors (rows or columns of $A$) would need to be close to orthogonal, thus the hyper-dimensional parallelepiped would have larger volume (determinant of $A$), since the magnitudes of the vectors are obviously bounded being 0-1. However, limiting to being orthogonal limits the possibilities as well, so this would not be the best approach.

The problem as I understand it is related to integer lattices. In your iteration, take $\mathbf{b}$ as random. Then your choice for $\mathbf{c}$ and $g$ gives a determinant $$\pmatrix{\mathbf{c} & g}\pmatrix{-A^{-1}\mathbf{b}\det(A) \\ \det(A)}$$

For easier notation rename as $$\pmatrix{\mathbf{c} & g}\pmatrix{\mathbf{x} \\ y}$$

where all elements are integer. Each iteration step that gives the largest value in magnitude here appears to me to be ones for $\mathbf{c}$ that gives the largest sum (selecting all positive or all negative from $\mathbf{x}$). Such an approach might give degenerate iteration states ( thus en the end not giving largest possible $d$). I believe that some matrix with large determinant $d$ may be a found in this manner.

I know this is nowhere near a complete answer to your question. My approaches are always more constructionist than theoretical, so I hope this gives you some insight to a possible good approach.