Timeline for Number of unique determinants for an NxN (0,1)-matrix
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 8, 2017 at 1:36 | comment | added | Gerhard Paseman | @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. | |
| Feb 6, 2017 at 9:10 | comment | added | Fedor Petrov | @GerhardPaseman the link on prado.com does not work, do you have it elsewhere? | |
| Apr 16, 2010 at 4:07 | comment | added | Mariano Suárez-Álvarez | «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»! | |
| Mar 19, 2010 at 20:22 | comment | added | Gerhard Paseman | 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 4*Fib(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 2*Fib(n) - 1, to get 2 more values. Gerhard "Ask Me About System Design" Paseman, 2010.03.19 | |
| Mar 19, 2010 at 15:52 | vote | accept | Ross Snider | ||
| Mar 19, 2010 at 15:52 | comment | added | Ross Snider | 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. | |
| Mar 18, 2010 at 22:24 | comment | added | Gerhard Paseman | 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. | |
| Mar 18, 2010 at 18:40 | comment | added | Ross Snider | 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. | |
| Mar 18, 2010 at 15:06 | comment | added | Gerhard Paseman | 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 | |
| Mar 18, 2010 at 7:22 | history | answered | Gerhard Paseman | CC BY-SA 2.5 |