Number of turning points on a nondecreasing $n^2 \times n^2$ matrix

Question

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

Answer 1

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