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
    Commented Jan 11, 2016 at 12:38
  • $\begingroup$ That is a special turning point. $\endgroup$ Commented 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
    Commented Jan 11, 2016 at 13:18
  • $\begingroup$ @EmanueleTron Does that work for you? For me, it doesn't. $\endgroup$
    – Wolfgang
    Commented Jan 11, 2016 at 13:26
  • $\begingroup$ I don't think this answer works. @Wolfgang, would you explain it a bit more? $\endgroup$ Commented 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
    Commented Jan 12, 2016 at 7:28
  • 1
    $\begingroup$ Thanks, corrected. $\endgroup$
    – Wolfgang
    Commented Jul 31, 2022 at 14:36

You must log in to answer this question.

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