Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
@ThomasAndrews $n^{n/2}$ is the original Hadamard's bound for the determinants of matrices with real entries in $[-1,1]$. It is far inferior to the improved Hadamard bound mentioned in the question. Note the $2^n$ in the denominator! ;-D –  user1551 Jan 9 '13 at 16:19
    
Yep, definitely missed the denominator. –  Thomas Andrews Jan 9 '13 at 16:44
1  
I have found a $20 \times 20$ 0-1 matrix with determinant $31524239$ –  adam W Jan 10 '13 at 0:35
    
35411790, closer to the halfway point. @Will do you have a link to the 20 (21 dim) case maximal found? –  adam W Jan 10 '13 at 16:03
    
And yet larger... I'll stop commenting for now... –  adam W Jan 10 '13 at 16:10
show 2 more comments

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer
    
What I big surprise! I've never thought that the determinant spectrum can be noncontiguous as soon as $n=7$. And I also didn't know that the relevant literature is so vast. Thanks a lot for your answer and the references. There is one more thing I want to ask. Certainly, the spectrum for $n$ must be a subset of the spectrum for $n+1$, but from your webpage, it seems that we have something more: the spectrum for $n$ lies inside a continguous subspectrum for $n+1$. Is this also a known result? –  user1551 Jan 10 '13 at 9:00
    
@user1551: That is a nice observation. As far as I know, it is not a known result. In fact, the only contiguity result I know of is Gerhard Paseman's Fibonacci matrix construction. There used to be a website describing it, but I can't find it anymore. Gerhard doesn't seem to be on MSE these days, although he is active on MathOverflow. –  Will Orrick Jan 11 '13 at 2:47
    
The most surprising thing to me in that data is that the range of contiguity seems be a roughly constant fraction of the Hadamard bound, while determinants of random matrices are sharply peaked at roughly $e^{-n}$ times the Hadamard bound. –  Will Orrick Jan 11 '13 at 2:53
    
Thank you again. –  user1551 Jan 11 '13 at 8:11
add comment

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.

share|improve this answer
    
+1 Thanks for the detailed answer! I think the answer is yes too, but am afraid of being entrapped by the law of small numbers, as it takes millions of simulations to find even a matrix with det=18 when n=7! Anyway, with your notations, to make $\pmatrix{\mathbf{c}&g}\pmatrix{\mathbf{x}\\y}$ as large as possible, $x$ and $y$ should be large too. Since $x$ involves minors of $A$ and $y$ involves $\det A$, it seems that a matrix with large det. tends to have many submatrices with large determinants. I'm not sure if I'm being too far fetched, but your answer does shed some new light to me. –  user1551 Jan 9 '13 at 18:35
    
It does take work for a random matrix, I have looked at LDU factorization, replacing diagonal of D with ones. That usually (depends on the number of ones, usually all but one) returns the matrix with only one row changed, but still relatively small. I then do lattice reduction techniques to reduce that further, with success (I may be remembering -1 0 1 not 0-1 matrix) only up to 20, maybe 30 dimensions. –  adam W Jan 9 '13 at 18:42
    
But the Laplacian expansion along any row gives a different lattice to which to reduce, which is why I believe finding small determinant is always easy. It is the other end with large determinant that I wonder about. So if you sequence is not consecutive, it will be interrupted on the larger end of values. –  adam W Jan 9 '13 at 18:46
    
(1) Here I don't follow. Why would replacement of D by I in LDU gives you an integer matrix? (2) I like this "interruption on the larger end" bit. Thanks. (3) I meant to verify whether dets of 7x7 matrices are consecutive, I spent millions of simulation trials to find one with det=18. So I haven't tried to find matrices with even higher dets and I haven't finished verifying the n=7 case. It may take only a few minutes to complete the verification, but for even slightly higher n, say n=14, verification of the contiguity hypothesis is already several orders of magnitude more difficult. –  user1551 Jan 9 '13 at 19:03
    
Yes, I just realized you meant as high as 18, I was thinking you meant as low as 18. And as for the LDU, I meant a partial calculation of the Smith Normal form as I did integer only operations. –  adam W Jan 9 '13 at 19:07
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.