# Is a "row discrepancy" of symmetric row-column increasing matrices unbounded?

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

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$.
• @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 '12 at 10:23
• @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 '12 at 14:54