MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Number of unique determinants for an NxN (0,1)-matrix.

I'm interested in bounds for the number of unique determinants of NxN (0,1)-matrices. Obviously some of these matrices will be singular and therefore won't have a determinant. While it might also be interesting to ask what number of NxN (0,1)-matrices are singular or non-singular, I'd like to ignore singular matrices altogether in this question.

To get a better grasp on the problem I wrote a computer program to search for the values given an input N. The output is below:
1x1: 2 possible determinants
2x2: 3 ...
3x3: 5 ...
4x4: 9 ...
5x5: 19 ...

Because the program is simply designed to just a brute force over every possible matrix the computation time grows with respect to $O(2^{N^2})$. Computing 6x6 looks like it is going to take me close to a month and 7x7 is beyond hope without access to a cluster. I don't feel like this limited amount of output is enough to make a solid conjecture.

I have a practical application in mind, but I'd also like to get the bounds to satiate my curiosity.

-
Singular matrices certainly do have a determinant; it's zero... – Qiaochu Yuan Mar 18 2010 at 6:26
I'm sorry, I was a bit careless above; the 10 x 10 number is 269, but the 11 x 11 is unknown. See A013588 in the Online Encyclopedia of Integer Sequences, research.att.com/~njas/sequences/A013588 – Gerry Myerson Mar 18 2010 at 6:30
I remember doing the 7x7 spectrum by hand years ago after some computer searching with a single desktop computer of 1990's vintage. It feels good to be compared to a computing cluster. Gerhard "Ask Me About System Design" Paseman, 2010.03.18 – Gerhard Paseman Mar 18 2010 at 7:27
I also did the smaller cases by hand. For 4x4 I got 7, for 5x5 I got 11 and 6x6 I got 19. You might check your computer program. Gerhard "Ask Me About System Design" Paseman, 2010.03.18 – Gerhard Paseman Mar 18 2010 at 14:51
The 12 x 12 case has recently been settled by a calculation of Richard Brent, Judy-anne Osborn, Paul Zimmermann, and myself: the conjecture at indiana.edu/~maxdet/spectrum13.html is correct. (The link is to the n=13 case of {-1,1} matrices, which corresponds to the 12 x 12 case of {0,1} matrices.) We hope to write up these and other results soon. The answer for 11 x 11 is still unknown, as our code works only for odd-sized {-1,1} matrices. – Will Orrick Apr 15 2010 at 3:27

I have given some detail in a comment to another answer. I have a proof that the number of determinants is greater than 4 times the nth Fibonacci number for (n+1)x(n+1) (0,1) matrices, and I conjecture that for large n the number of distinct determinants approaches a constant times n^(n/2). Math Overflow has some hints of the proof in answers I made on other questions.

I am interested in your idea for an application, and am willing to share more information on this subject.

-
show 1 more comment

From Hadamard's bound the largest possible determinant of an $n\times n$ (0,1) matrix is $h_n=2^{-n}(n+1)^{(n+1)/2}$. The data at http://www.indiana.edu/~maxdet/spectrum.html suggest several conjectures:

1. The spectrum is "dense" up to a certain point, after which it becomes "sparse". An integer in the "dense" part is almost certain to be the determinant of some $n\times n$ (0,1) matrix; and integer in the "sparse" part is almost certain not to be. The point at which the spectrum becomes sparse is asymptotically some constant times $h_n$. The data suggest that the constant is near 0.5. I think this is basically the conjecture made by Gerhard Paseman in his answer.
2. A stronger statement is as follows: let $g_n$ be the position of the first "gap", that is, the first positive integer that is not the determinant of some $n\times n$ (0,1) matrix. Then asymptotically $g_n$ is some constant times $h_n$, and again the constant appears to be close to 0.5. If $D_n$ denotes the set of positive $n\times n$ determinants, and if the above ideas are on the right track, then it seems likely that asymptotically $g_n/|D_n|$ is 1.

I don't have even a heuristic explanation as to why such conjectures ought to be true, and one can always worry about how much one should try to conclude from data that, in fact, go only as high as $n=21$. As mentioned in some of the comments to other answers, $D_n$ is really only known for $n\le 10$ and $n=12$. The sets $D_n$ for these $n$ are given at the above link, as are conjectures for all $n$ up to 16. Data for $17\le n\le21$ have not yet been added to the site. (Note that the $n$ on the web site refers to $(-1,1)$ matrices, so one should subtract 1 from it if one is talking about $(0,1)$ matrices.) I do have high confidence that the listed sets $D_n$ up to $n=16$ are not missing any values, even the ones that have not been proved complete.

-
 I'm hoping to talk about this in Hyderabad. Will email sent to the maxdet address reach you personally? – Gerhard Paseman Apr 15 2010 at 22:52 Also, in the spectrum URL above, I get better results replacing math with www. – Gerhard Paseman Apr 16 2010 at 0:13 Sorry that I won't be in Hyderabad to hear your talk. I do check the maxdet email account regularly. Thanks for pointing out the bad URL. Fixed now. – Will Orrick Apr 16 2010 at 3:02

There are some answers in W P Orrick, The maximal {-1,1}-determinant of order 15, http://arXiv.org/pdf/math/0401179v1. Despite the title, toward the end of the paper the author does look at {0,1} matrices, and at the entire range, not just the maximal. The author also refers to an older paper on the topic, R Craigen, The range of the determinant function on the set of $n\times n$ (0,1) matrices, J Combin Math Combin Comput 8 (1990) 161-171.

-