0
$\begingroup$

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]

$\endgroup$
3
  • $\begingroup$ This question makes me think of mathoverflow.net/questions/131373/…. Is there any link? $\endgroup$ Aug 13, 2018 at 12:59
  • $\begingroup$ @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? $\endgroup$
    – jcdornano
    Aug 13, 2018 at 18:21
  • $\begingroup$ 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. $\endgroup$ Aug 13, 2018 at 22:36

1 Answer 1

1
+50
$\begingroup$

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}\;\; } $

$\endgroup$
3
  • $\begingroup$ 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^^ $\endgroup$
    – jcdornano
    Aug 14, 2018 at 16:29
  • $\begingroup$ 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? $\endgroup$ Aug 15, 2018 at 17:59
  • $\begingroup$ :Yes it is what I mean, sorry for the unusual terminology! $\endgroup$
    – jcdornano
    Aug 16, 2018 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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