18

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.

Rodrigo de Azevedo
  • 1
Ross Snider
  • 359
  • 13
    Singular matrices certainly do have a determinant; it's zero... – Qiaochu Yuan Mar 18 '10 at 06:26
  • 1
    I think this is a hard problem. As evidence, I note that the smallest positive integer which is not the determinant of a 9 x 9 binary matrix was only recently found to be 103 (http://arXiv.org/pdf/math/0511636v1); the smallest positive integer not the determinant of a 10 x 10 binary matrix seems to be unknown. – Gerry Myerson Mar 18 '10 at 06:27
  • 7
    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, http://oeis.org/A013588 – Gerry Myerson Mar 18 '10 at 06:30
  • Just a comment that you can certainly improve the efficiency of your brute force approach. For example, once you have one determinant calculated, you may as well cross off all matrices which are row or column swaps. While we're at it, the 6x6 determinants properly include into the 7x7 determinants (multiple times!), so you could skip over these if you've already done them. And I'm sure you could be much more clever than these...this was just a first thought. – Cam McLeman Mar 18 '10 at 06:52
  • 3
    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 '10 at 07:27
  • 3
    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 '10 at 14:51
  • Ahh, yes there seems to be a small problem with the determinant calculating code. I grabbed a determinant function that works with libboost online. Should have checked it for accuracy in all cases. – Ross Snider Mar 18 '10 at 18:36
  • 5
    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 http://www.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 '10 at 03:27
  • @Will, any update? – Gerry Myerson Feb 25 '17 at 22:09
  • 1
    @Gerry Unfortunately not much. The writeup mentioned in my comment above is https://arxiv.org/abs/1112.4160. It is not published yet due mostly to inattention on my part and partly to lack of enthusiasm for this kind of work from the referees. I did have some ideas a few years back for how to adapt the method for the $11\times 11$ and possibly $13\times 13$ cases, at some increase in complexity of the code and decrease in its efficiency, but have not seriously pursued it. I believe there's been no progress related to any of the conjectures in my answer below. Experts I've spoken with... – Will Orrick Feb 28 '17 at 17:43
  • …seem skeptical, both that such things might be true and there there's any hope of attacking such questions with current methods. – Will Orrick Feb 28 '17 at 17:44

3 Answers3

4

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

Gerhard Paseman
  • 3,199
  • 1
  • 18
  • 29
  • Of course, the proof is for n greater than 5. The actual proof at http://grpmath.prado.com/Lemmas.html shows that there are (0,1)matrices of size n with determinant values 0 through 2Fib(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 – Gerhard Paseman Mar 18 '10 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. – Ross Snider Mar 18 '10 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. – Gerhard Paseman Mar 18 '10 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. – Ross Snider Mar 19 '10 at 15:52
  • Thank you for accepting. The rigorous proof linked above (Lemmas.html) constructs matrices A_n for each order n, and then shows they can be augmented by one row and one column to produce many distinct determinants. It then shows that this set, along with a singular matrix and row transposition to change sign, gives 4Fib(n) - 1 distinct values for the determinant among (n+1)x(n+1) 0-1 matrices. For n > 5 I appeal to the literature for the existence of one more matrix with determinant larger than 2Fib(n) - 1, to get 2 more values. Gerhard "Ask Me About System Design" Paseman, 2010.03.19 – Gerhard Paseman Mar 19 '10 at 20:22
  • 5
    «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»! – Mariano Suárez-Álvarez Apr 16 '10 at 04:07
  • @GerhardPaseman the link on prado.com does not work, do you have it elsewhere? – Fedor Petrov Feb 06 '17 at 09:10
  • @Fedor I just noticed your comment today (I do not know why I did not earlier). The Wayback Machine (archive.org) should have a copy. The main thrust of the page is replicated (with a small and correctable error) in Zivkovic's 2005 paper on ArXiv in his section 4 (Gerry Myerson has a link above). If you don't find the archived copy of the webpage, I can probably email you photos of the slide presentation which was the source of it. If I make any more progress on this question I will update one of my answers to your question. Gerhard "It May Be Time Again" Paseman, 2017.05.07. – Gerhard Paseman May 08 '17 at 01:36
4

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.

Will Orrick
  • 2,130
3

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.

Gerry Myerson
  • 39,024
  • 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 – Gerhard Paseman Mar 18 '10 at 07:04
  • 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 – Gerhard Paseman Mar 18 '10 at 07:08
  • 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. – Will Orrick Apr 15 '10 at 03:37