# 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 will trivially have zero 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... Commented 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, oeis.org/A013588 Commented 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 Commented 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 Commented 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. Commented 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.

• Of course, the proof is for n greater than 5. The actual proof at grpmath.prado.com/Lemmas.html shows that there are (0,1)matrices of size n with determinant values 0 through 2*Fib(n-1) - 1, for all positive n. For n > 6, I use in addition a matrix with maximal determinant to get 4* fib(n-1) + 1 distinct values, both positive and negative and including 0. (Yes, I know about the faulty timestamp.) Gerhard "Ask Me About System Design" Paseman, 2010.03.18 Commented Mar 18, 2010 at 15:06
• The application isn't fully fleshed out. I was looking into the growth of the number of determinants to see asymptotic behaviour. I am looking to see if comparing determinants of adjacency matrices of simple graphs (after being processed by various transforms) can be used to solve the isomorphism problem probabilistically. I just started looking into the idea - no great progress or insight to be had yet. Commented Mar 18, 2010 at 18:40
• Another possibility is to use a characteristic polynomial, det( A- Ix ) for A the adjacency matrix and x an indeterminate. Unfortunately there are a couple of nonisomorphic trees on something like 10 vertices which have the same polynomial. However, the determinant in combination with something else might be useful in making the equivalence classes almost as small as the isomorphism classes. Commented Mar 18, 2010 at 22:24
• I am accepting this answer because it provides an interesting lower bound, even if you haven't proved it rigorously here, and because it seems like the flurry of activity on this question has died out. Commented Mar 19, 2010 at 15:52
• «Math Overflow has some hints of the proof in answers I made on other questions» is as helpful as the proverbial «It is in Euler's works somewhere»! Commented Apr 16, 2010 at 4:07

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.

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.