Let $M$ be an $n\times m$ matrix, say with entries in $\left\{0,1\right\}$ ; and let $\mathcal C(M)$ be the $n\times m$ matrix such that there exists $P$, $m\times m$ permutation matrix such that $M.P=\mathcal C(M)$ and such that the columns of $\mathcal C(M)$ are *lexicographically increasing* (1) (for a formal definition of (1) see [reflexive relations that are "tridiagonally cycle-indexed" (or "almost ordered" matrices/relations)](https://mathoverflow.net/questions/298321/reflexive-relations-that-are-tridiagonally-cycle-indexed-or-almost-ordered))
$\mathcal R(M):= \mathcal C(M^t))^t$ is the matrix you get from $M$ that rows are lexicographically increasing. 


We now say that $\mathcal L=\mathcal C\,o\,\mathcal R$.


Let $Q$ be a $m\times m$ permutation matrix s.t. $Q^q=Id$. We define $\mathcal L\_Q$ to be such that $\mathcal L\_Q(M)=\mathcal L(M).Q$ for all $M$ of size $n\times m$. 



> 
> Does there exists $r\in \mathbb N$ such that $\mathcal L\_Q^{r+iq}(M)=\mathcal L\_Q^r(M)$ for any $i\in \mathbb N$
> 
> 
> 


The cases that seem the most interesting to me are $\mathcal L\_{Id}=\mathcal L$ and $\mathcal L\_J$ where $J$ is the $i\mapsto m-i$ permutation matrix, I talked about these cases in the upper link.




---


Example with $m=n=4$ 


$Q=J=\begin{matrix}
0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1& 0 & 0 & 0 
\end{matrix}$


(so $q=2$)


Let's take
 $M=\begin{matrix}
0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1& 1 & 1 & 0 
\end{matrix}$


We range rows according to lexicographic order :


$\mathcal R(M)=\begin{matrix}
0 & 0 & 1 & 1\\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 
\end{matrix}$


And now columns...
$\mathcal L(M)=\begin{matrix} 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 
\end{matrix}$


And we multiply on the right by $J$:


$\mathcal L\_J(M)= \begin{matrix} 1 & 1 & 0 & 0\\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 
\end{matrix}$


If we apply $\mathcal L\_J$ to $\mathcal L\_J(M)$ we then get :


$\mathcal L^2\_J(M)= \begin{matrix} 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 
\end{matrix}$


etc....


We will get :


$\mathcal L^4\_J(M)=\mathcal L^6\_J(M)=\begin{matrix} 1 & 1 & 0 & 0\\ 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 
\end{matrix}$


We could verify that $\mathcal L^3\_J(M)\ne \mathcal L^5\_J(M)(\ne L^4\_J(M))$ and then $r=4$ is the smallest possible (and $k$ such that $i\mapsto L^{r+i}\_J(M)$ is $2$-periodic but not constant)



order of a permutation and lexicographic order
There are counterexamples for $Q=J$. 


Here is a binary $6\times7$ binary matrix $M$ that belongs to an orbit of $\mathcal{L}\_J$ with period $3$:


$\begin{matrix}
1&1&1&0&0&0&0\\
1&1&0&1&1&0&0\\
0&0&1&1&0&1&0\\
0&0&1&0&1&0&1\\
1&0&0&1&0&1&1\\
0&1&0&0&1&1&1\\
\end{matrix}$


Here is another with period $4$:


$\begin{matrix}
1&1&0&0&0&0&0\\
1&0&1&1&0&0&0\\
0&1&1&0&1&0&0\\
0&1&0&1&0&1&1\\
1&0&0&0&1&1&0\\
0&0&0&1&1&1&0\\
\end{matrix}$


and another with period $6$:


$\begin{matrix}
1&1&1&0&0&0&0\\
1&1&0&1&1&0&0\\
0&0&1&1&0&1&0\\
0&0&1&1&0&0&1\\
1&0&0&0&0&1&1\\
0&1&0&0&0&1&1\\
\end{matrix}$


On the whole set of $7\times 7$ binary matrices, $\mathcal{L}\_J$ gets
$$
\begin{array}{r l}
 326\,166&\text{fixed matrices}\\
 86\,146\,036&\text{distinct orbits of length }2\\
 94&\text{distinct orbits of length }3\\
 5\,400&\text{distinct orbits of length }4\\
 8&\text{distinct orbits of length }5\\
 196&\text{distinct orbits of length }6\\
\end{array}
$$


