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:
1×1: 2 possible determinants
2×2: 3 …
3×3: 5 …
4×4: 9 …
5×5: 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 6×6 looks like it is going to take me close to a month and 7×7 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.
Best Answer
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