18
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • 13
    $\begingroup$ Singular matrices certainly do have a determinant; it's zero... $\endgroup$
    – Qiaochu Yuan
    Commented Mar 18, 2010 at 6:26
  • 7
    $\begingroup$ 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 $\endgroup$
    – Gerry Myerson
    Commented Mar 18, 2010 at 6:30
  • 3
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Mar 18, 2010 at 7:27
  • 3
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Mar 18, 2010 at 14:51
  • 5
    $\begingroup$ 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. $\endgroup$
    – Will Orrick
    Commented Apr 15, 2010 at 3:27

3 Answers 3

Reset to default
4
$\begingroup$

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.

Gerhard "Ask Me About System Design" Paseman, 2010.03.19

Improve this answer
$\endgroup$
8
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Mar 18, 2010 at 15:06
  • $\begingroup$ 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. $\endgroup$
    – Ross Snider
    Commented Mar 18, 2010 at 18:40
  • $\begingroup$ 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. $\endgroup$
    – Gerhard Paseman
    Commented Mar 18, 2010 at 22:24
  • $\begingroup$ 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. $\endgroup$
    – Ross Snider
    Commented Mar 19, 2010 at 15:52
  • 5
    $\begingroup$ «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»! $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Apr 16, 2010 at 4:07
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I'm hoping to talk about this in Hyderabad. Will email sent to the maxdet address reach you personally? $\endgroup$
    – Gerhard Paseman
    Commented Apr 15, 2010 at 22:52
  • $\begingroup$ Also, in the spectrum URL above, I get better results replacing math with www. $\endgroup$
    – Gerhard Paseman
    Commented Apr 16, 2010 at 0:13
  • $\begingroup$ 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. $\endgroup$
    – Will Orrick
    Commented Apr 16, 2010 at 3:02
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This subject is a current research interest of mine. Orrick maintains a web site which contains conjectured determinant spectra, Miodrag Zivkovic has done exhaustive reseearch involving Smith Normal forms up to 9x9, and I am searching for another class of matrices to push the bound above 4 times the nth Fibonacci number. A search for "Paseman determinant" will give you some of the internet links. Post more questions here and I will share what I know and believe. Gerhard "Ask Me About System Design" Paseman, 2010.03.19 $\endgroup$
    – Gerhard Paseman
    Commented Mar 18, 2010 at 7:04
  • $\begingroup$ I am also interested in applications. I may be induced to help you with your application. Gerhard "Ask Me About System Design" Paseman, 2010.03.19 $\endgroup$
    – Gerhard Paseman
    Commented Mar 18, 2010 at 7:08
  • $\begingroup$ Interestingly, the problem was studied by Metropolis, Stein, and Wells (see 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.) who had computed the answers up to n=7 back in 1969 (and claimed to be able to handle n=8). I wasn't aware of this work when I wrote the aforementioned paper. $\endgroup$
    – Will Orrick
    Commented Apr 15, 2010 at 3:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .