most recent 30 from http://mathoverflow.net 2013-05-19T20:00:52Z http://mathoverflow.net/feeds/question/18547 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/18547/number-of-unique-determinants-for-an-nxn-0-1-matrix Ross Snider 2010-03-18T06:02:39Z 2010-04-16T02:53:51Z

<p>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.<br><br> 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:<br> 1x1: 2 possible determinants<br> 2x2: 3 ...<br> 3x3: 5 ...<br> 4x4: 9 ...<br> 5x5: 19 ...<br><br></p> <p>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.</p> <p>I have a practical application in mind, but I'd also like to get the bounds to satiate my curiosity.</p>

http://mathoverflow.net/questions/18547/number-of-unique-determinants-for-an-nxn-0-1-matrix/18550#18550 Gerry Myerson 2010-03-18T06:40:21Z 2010-03-18T06:40:21Z

<p>There are some answers in W P Orrick, The maximal {-1,1}-determinant of order 15, <a href="http://arXiv.org/pdf/math/0401179v1" rel="nofollow">http://arXiv.org/pdf/math/0401179v1</a>. 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. </p>

http://mathoverflow.net/questions/18547/number-of-unique-determinants-for-an-nxn-0-1-matrix/18554#18554 Gerhard Paseman 2010-03-18T07:22:22Z 2010-03-18T07:22:22Z

<p>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.</p> <p>I am interested in your idea for an application, and am willing to share more information on this subject.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2010.03.19</p>

http://mathoverflow.net/questions/18547/number-of-unique-determinants-for-an-nxn-0-1-matrix/21510#21510 Will Orrick 2010-04-15T22:25:11Z 2010-04-16T02:53:51Z

<p>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 <a href="http://www.indiana.edu/~maxdet/spectrum.html" rel="nofollow">http://www.indiana.edu/~maxdet/spectrum.html</a> suggest several conjectures:</p> <ol> <li>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.</li> <li>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.</li> </ol> <p>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.</p>