1
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ by merely rounding will lead to a matrix that does not satisfy strict inequalities... $\endgroup$
    – Suvrit
    Commented Sep 26, 2012 at 16:50
  • 2
    $\begingroup$ The matrix should be symmetric... $\endgroup$
    – Ilya Bogdanov
    Commented Sep 27, 2012 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
    Commented Sep 27, 2012 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
    Commented Sep 27, 2012 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
    Commented Sep 27, 2012 at 14:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .