# root of identity matrix and lexicographic order

I asked a question here order of a permutation and lexicographic order but it seems*** that a very powerful and rich generalization can be made!

Let $A$ be a finite ring together with an arbitrary total order $<^*$ and let $L: M_n(A)\to M_n(A)$ be the application that sorts the rows of a matrix according to the (increasing) lexicographic order (induced by $<^*$) and the columns of the matrice we get, according to the increasing lexicographic order (increasingly too). We then define $L_Q(M):=L(M).Q$ for any $Q\in M_n(A)$.

Suppose that $Q^q=Id$ for some $q\in \mathbb N$ and $Q\in GL_n(A)$. Is is true that for any $M\in M_n(A)$, there exists $r\in \mathbb N$ such that for any $i\in \mathbb N$, we have $L_Q^r(M)=L_Q^{r+iq}(M)$ ?

[edit : it is not true for $A=\mathbb Z$, but it seems asymptotically true up to a scalar multiplication of matrices, anyway I edited and ask $A$ to be finite]

• This question makes me think of mathoverflow.net/questions/131373/…. Is there any link? Aug 13, 2018 at 12:59
• @Chris Birkbeck : I'm not sure to see one yet, but maybe. Also, I don't understand all the notations. Is $*$ the usual product in the question you mentioned ? or something else? Aug 13, 2018 at 18:21
• Yes I'm pretty sure * is the usual product. It just reminded me of this, since in a way SNF is looking for the smallest entries on each row, but this is probably too vague to be of any use. Aug 13, 2018 at 22:36

Iterating $\mathsf L_Q$ over an initial matrix shall always yield a periodic sequence at some point because there is only finitely many possible matrices, but the period is not necessarily $q$ or a multiple or divisor of $q$.

Here is an example where the period is $4$ while $q=3$. It is a modification of yours where now $Q$ permutes the 3 first columns.

$Q= \;\;\begin{matrix}0&1&0&0\\0&0&1&0\\1&0&0&0\\0&0&0&1\end{matrix}\;\;$ and $\;M= \;\;\begin{matrix}0&0&1&1\\1&0&0&1\\0&1&1&0\\1&1&1&0\end{matrix}\;\;$



$\xrightarrow{\mathsf R} \;\;\begin{matrix}0&0&1&1\\0&1&1&0\\1&0&0&1\\1&1&1&0\end{matrix}\;\; \xrightarrow{\mathsf C} \;\;\begin{matrix}0&0&1&1\\0&1&0&1\\1&0&1&0\\1&1&0&1\end{matrix}\;\; \xrightarrow{\mathsf Q} \color{red}{ \;\;\begin{matrix}1&0&0&1\\0&0&1&1\\1&1&0&0\\0&1&1&1\end{matrix}\;\; }$



$\xrightarrow{\mathsf R} \;\;\begin{matrix}0&0&1&1\\0&1&1&1\\1&0&0&1\\1&1&0&0\end{matrix}\;\; \xrightarrow{\mathsf C} \;\;\begin{matrix}0&0&1&1\\0&1&1&1\\1&0&0&1\\1&1&0&0\end{matrix}\;\; \xrightarrow{\mathsf Q} \;\;\begin{matrix}1&0&0&1\\1&0&1&1\\0&1&0&1\\0&1&1&0\end{matrix}\;\;$



$\xrightarrow{\mathsf R} \;\;\begin{matrix}0&1&0&1\\0&1&1&0\\1&0&0&1\\1&0&1&1\end{matrix}\;\; \xrightarrow{\mathsf C} \;\;\begin{matrix}0&0&1&1\\0&1&0&1\\1&0&1&0\\1&1&1&0\end{matrix}\;\; \xrightarrow{\mathsf Q} \;\;\begin{matrix}1&0&0&1\\0&0&1&1\\1&1&0&0\\1&1&1&0\end{matrix}\;\;$



$\xrightarrow{\mathsf R} \;\;\begin{matrix}0&0&1&1\\1&0&0&1\\1&1&0&0\\1&1&1&0\end{matrix}\;\; \xrightarrow{\mathsf C} \;\;\begin{matrix}0&0&1&1\\0&1&0&1\\1&1&0&0\\1&1&1&0\end{matrix}\;\; \xrightarrow{\mathsf Q} \;\;\begin{matrix}1&0&0&1\\0&0&1&1\\0&1&1&0\\1&1&1&0\end{matrix}\;\;$



$\xrightarrow{\mathsf R} \;\;\begin{matrix}0&0&1&1\\0&1&1&0\\1&0&0&1\\1&1&1&0\end{matrix}\;\; \xrightarrow{\mathsf C} \;\;\begin{matrix}0&0&1&1\\0&1&0&1\\1&0&1&0\\1&1&0&1\end{matrix}\;\; \xrightarrow{\mathsf Q} \color{red}{ \;\;\begin{matrix}1&0&0&1\\0&0&1&1\\1&1&0&0\\0&1&1&1\end{matrix}\;\; }$

• Thank you very much, this is more than I expected because I was kind of convinced that the statement was true if $Q$ is a permutation matrix. I think the result is true if $Q$ is the $n\times n$ matrix associated to $i\mapsto n-i$, but I only showed this if $M$ is an "order matrix"... Thank you again for this great answer. I'm kind of relieved that the statement is wrong because, I was quite annoyed by not being able to prove it^^ Aug 14, 2018 at 16:29
• You are welcome. This is interesting. I'll investigate the case $n-i$ with a computer search. What do you mean by "order matrix"? The adjacency matrix of a partially ordered set? Aug 15, 2018 at 17:59
• :Yes it is what I mean, sorry for the unusual terminology! Aug 16, 2018 at 1:19