1
$\begingroup$

Given a integer value $n$, we generate a $n^2 \times n^2$ integer matrix $M$ in the following way.

  1. Each ceil has value range $[1~n]$
  2. In each row, the value is nondecreasing. E.g. $M[i, j] \leq M[i, j+1]$
  3. In each column, the value is nondecreasing. E.g. $M[i, j] \leq M[i+1, j]$

For example the following is a example of $n=2$ & $4*4$ matrix.

1 1 1 2

1 1 1 2

2 2 2 2

2 2 2 2

We define the concept of turning point $(i,j)$ as

  1. $M[i,j] = M[i, j+1] - 1$

  2. $M[i,j] = M[i+1, j] - 1$

We can treat turning points as skyline points if you may. $M[n^2,n^2]$ is a special turning point.

For the above example, the turning points are $(2,3)$ and $(4,4)$.

We want to calculate the upper bound of total number of turning points, we denoted by $|P|$.

It is easy to proof that the upper bound size of set P is $O(n^3)$.

However, the real data shows that $|P|$ is always failing in the complexity of $n^2$ range.

Is there a way to proof that the upper bound of $|P|$ is $n^2$?

$\endgroup$
2
  • $\begingroup$ why is (4,4) a turning point? $\endgroup$
    – Wolfgang
    Jan 11, 2016 at 12:38
  • $\begingroup$ That is a special turning point. $\endgroup$ Jan 11, 2016 at 13:23

1 Answer 1

7
$\begingroup$

Probably the best possible, in any case a matrix with $O(n^3)$ turning points, is $$\begin{pmatrix} 1&1&\dots&&&\color{red}1&2\\ \vdots&\vdots&&&\!\!\!\color{red}{ {_{\displaystyle \raise -3pt\cdot}\displaystyle\cdot \,^{\displaystyle \cdot}}}&\color{red}2&3\\ \vdots&\vdots&&& \!\!\! \color{red}{ {_{\displaystyle \raise -3pt \cdot}\displaystyle\cdot\, ^{\displaystyle \cdot}}} &\color{red} \vdots& \vdots \\ 1&1&\dots &&&\color{red}{n-1} &n\\ 1&1&\dots &&\!\!\!\!\color{red}{n-1} &n&n\\ \vdots&\color{red}{ {_{\displaystyle\raise -3pt \cdot}\displaystyle\cdot \,^{\displaystyle \cdot}}}&\color{red}{ {_{\displaystyle \raise -3pt\cdot}\displaystyle\cdot \,^{\displaystyle \cdot}}}&&& \vdots & \vdots \\ \color{red}1&\color{red}2&\dots&&&n & n \\ 2&3&\dots&&&n & n \\ \end{pmatrix}$$ with constant antidiagonals, which has $\displaystyle \sum_{i=1}^{n-1}(n^2-i)=n^3-n^2-\frac{n(n-1)}2=O(n^3)$ turning points (in red). Or am I missing something?
(BTW is there a Latex command for rising \ddots?)

$\endgroup$
6
  • $\begingroup$ Do you mean \udots? $\endgroup$
    – user41593
    Jan 11, 2016 at 13:18
  • $\begingroup$ @EmanueleTron Does that work for you? For me, it doesn't. $\endgroup$
    – Wolfgang
    Jan 11, 2016 at 13:26
  • $\begingroup$ I don't think this answer works. @Wolfgang, would you explain it a bit more? $\endgroup$ Jan 12, 2016 at 5:25
  • $\begingroup$ For each $i=2,...,n-1$ there is exactly one antidiagonal $D_i$ with only $i$'s on it. For each $D_i$, and for the $D_1$ just above $D_2$, all its elements except the rightmost one are turning points. And this is best possible, as for any $M$ each column except the rightmost one can have at most $n-1$ turning points. $\endgroup$
    – Wolfgang
    Jan 12, 2016 at 7:28
  • 1
    $\begingroup$ Thanks, corrected. $\endgroup$
    – Wolfgang
    Jul 31, 2022 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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