Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $A$ be a symmetric row-column increasing $n \times n$ matrix (i.e. $A(i, j) < A(i+1,j)$ and $A(i, j) < A(i, j+1)$) with integer entries $A(i, j) \in \{1, 2, ..., n^2\}$. Moreover, let us assume that $A$ contains $\Theta(n^2)$ distinct entries, so the set of entries has positive density.

Define a "row discrepancy" for a rectangle $R=\{A(i,j); a_1 \leq i \leq a_2, b_1 \leq j \leq b_2 \}$ as $$D(R) = \frac{(a_2-a_1)(b_2-b_1)}{\max_{b_1 \leq j \leq b_2} (A(a_2, j)-A(a_1, j))}.$$ Let us also define the total "row discrepancy" $D_r$ as a supremum of $D(R)$ over all rectangles $R$. Is it true that $D_r$ must go to infinity as $n \to \infty$ for any $A$?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

This is my updated answer, probably still wrong somewhere...

If $A(i,j)=\lfloor (i+j)n/10\rfloor $, then the matrix is symmetric and satisfies strict inequalities if $n$ is at least $10$.

Also $A(a_2,j)-A(a_1,j)=(a_2-a_1)n/10$ (plus/minus 1, if you want integers and round the $A(i,j)$'s) and since $b_2-b_1\le n$, we get that $D(R)\le 10$.

share|improve this answer
    
by merely rounding will lead to a matrix that does not satisfy strict inequalities... –  Suvrit Sep 26 '12 at 16:50
2  
The matrix should be symmetric... –  Ilya Bogdanov Sep 27 '12 at 6:11
    
@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 –  DmitryZ Sep 27 '12 at 10:23
    
Right, but is seems that it is simple to make it symmetric, so there should be some other problem with my solution... –  domotorp Sep 27 '12 at 11:57
    
@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. –  DmitryZ Sep 27 '12 at 14:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.