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$?


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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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