Timeline for Probability of zero in a random matrix
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 6, 2012 at 10:22 | history | edited | Brendan McKay | CC BY-SA 3.0 |
note another formulation
|
| Jun 6, 2012 at 2:18 | answer | added | Gjergji Zaimi | timeline score: 6 | |
| Jun 5, 2012 at 11:44 | comment | added | Gjergji Zaimi | Regarding your edit: there is a counterexample to your property for such polynomials with only two nonzero $h_i$'s. However in the case of the Birkhoff polytope, we have the additional property that $h_i$ and $h_{d-i}$ are equal, as well as that $h_i$ is unimodal. This is still not enough to conclude log-concavity of $M$ but perhaps it can prove your inequality? | |
| Jun 5, 2012 at 8:42 | answer | added | Pietro Majer | timeline score: 3 | |
| Jun 5, 2012 at 2:25 | history | edited | Brendan McKay | CC BY-SA 3.0 |
oops
|
| Jun 4, 2012 at 18:24 | answer | added | David E Speyer | timeline score: 17 | |
| Jun 4, 2012 at 18:07 | comment | added | Greg Martin | Perhaps a silly comment, but you are trying to prove the inequality $|M(n,k-n)| \cdot|M(n,k+1)| \le |M(n,k)| \cdot|M(n,k+1-n)|$; there might be a combinatorial proof - an injection from $M(n,k-n) \times M(n,k+1)$ into $M(n,k) \times M(n,k+1-n)$.... | |
| Jun 4, 2012 at 16:02 | comment | added | Gerhard Paseman | My "first unsolved problem" involved a setup similar to yours. One approach I did not try which might work here is to turn the relation P(n,k) < P(n,k+1) into a statement that a certain 2x2 integer determinant is nonnegative. Ira Gessel might have some suggestions as to how to approach the problem frrom that direction. Gerhard "8f It Works, Tell Someone" Paseman, 2012.06.04 | |
| Jun 4, 2012 at 15:41 | comment | added | Brendan McKay | @Douglas: For fixed $n$, $|M(n,k)|$ is a polynomial in $k$ of degree $(n-1)^2$. It's called the Ehrhart polynomial of the Birkhoff polytope. See math.binghamton.edu/dennis/Birkhoff for a paper on it and the explicit polynomial for $n\le 9$. | |
| Jun 4, 2012 at 10:50 | comment | added | Douglas Zare | What is known about $|M(n,k)|$ for fixed $n$? It looks like log-concavity would imply the inequality you want. | |
| Jun 3, 2012 at 23:25 | history | edited | Brendan McKay | CC BY-SA 3.0 |
note polytope version of problem
|
| Jun 3, 2012 at 23:24 | comment | added | Brendan McKay | @Gerhard: That's one of the reasons I think the result is surely true, but can you turn it into a quantitative argument? The number of ways to write a matrix that way varies a great deal between matrices so you don't get a random matrix by adding together random permutation matrices. It is plausible that the relationship between $M(n,k)$ and $M(n,k+1)$ defined by having a difference which is a permutation matrix can be analyzed enough to give it. | |
| Jun 3, 2012 at 21:10 | answer | added | Vidit Nanda | timeline score: 2 | |
| Jun 3, 2012 at 16:29 | comment | added | Gerhard Paseman | Can't you use something like an element of M(n,k) is the sum of k permutation matrices to get your desired result for k>n? Gerhard "Ask Me About System Design" Paseman, 2012.06.03 | |
| Jun 3, 2012 at 15:23 | comment | added | cardinal | I can prove it for $n=1$. | |
| Jun 3, 2012 at 10:52 | history | asked | Brendan McKay | CC BY-SA 3.0 |