Timeline for Is a "row discrepancy" of symmetric row-column increasing matrices unbounded?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 28, 2012 at 4:18 | vote | accept | DmitryZ | ||
| Sep 28, 2012 at 4:17 | comment | added | DmitryZ | @domotorp You're right again. I should think more what are plausible conditions to make the question more interesting. My initial intuition was that if the matrix is dense in a sense it contains, say, all consecutive numbers $\\{1,..,cn^2\\$ than you can't avoid small jumps between neighboring entries keeping it row-column increasing symmetric. For example, if $S_i$ are entries $ni, ..., \(n+1)i$ than we have a partition of the square to approx $n$ symmetric row-column convex sets $S_i$ of size $n$ such that almost all rows contain elements from almost all of $S_i$. | |
| Sep 27, 2012 at 17:19 | comment | added | domotorp | That won't help, as A(i,j) can be any number from the [(i+j)n/10,(i+j)n/10+n/20] interval, all the conditions will remain true (if A(i,j)=A(j,i) and now by choosing many different values from these intervals for i+j constant we get cn^2 distinct entries. | |
| Sep 27, 2012 at 14:54 | comment | added | DmitryZ | @domotorp OK you're right. To avoid such counterexamples one should add that $A$ must contain $\Theta(n^2)$ distinct entries, which is important. I have updated the question. | |
| Sep 27, 2012 at 11:57 | comment | added | domotorp | Right, but is seems that it is simple to make it symmetric, so there should be some other problem with my solution... | |
| Sep 27, 2012 at 11:54 | history | edited | domotorp | CC BY-SA 3.0 |
added 136 characters in body
|
| Sep 27, 2012 at 11:52 | history | undeleted | domotorp | ||
| Sep 27, 2012 at 11:50 | history | deleted | domotorp | ||
| Sep 27, 2012 at 10:23 | comment | added | DmitryZ | @domotorp As Ilya said, the matrix should be symmetric. But you're right, $A(i,j) = n*(i-1)+j$ gives a counterexample in the non-symmetric case. P. S. It's more convenient to consider $A(i, j) \in \\{1,...,n^2\\}$, see the update | |
| Sep 27, 2012 at 6:11 | comment | added | Ilya Bogdanov | The matrix should be symmetric... | |
| Sep 26, 2012 at 16:50 | comment | added | Suvrit | by merely rounding will lead to a matrix that does not satisfy strict inequalities... | |
| Sep 26, 2012 at 14:58 | history | answered | domotorp | CC BY-SA 3.0 |