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

-

## 1 Answer

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

-
by merely rounding will lead to a matrix that does not satisfy strict inequalities... –  Suvrit Sep 26 '12 at 16:50
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