1
$\begingroup$

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)) $\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)

$\endgroup$
10
  • 1
    $\begingroup$ I think I'm misunderstanding the question, because it seems to me that $r=1$ would work. Could you give me an example where $r$ can't just be $1$? I hope that such an example will clear up my confusion. $\endgroup$ Jul 22 '18 at 14:12
  • $\begingroup$ I'm sorry I completely forgot a step in my construction (the composing with transposition part (that occurs in the link) is missing!!) I 'm editing write now!! $\endgroup$
    – jcdornano
    Jul 22 '18 at 17:45
  • 1
    $\begingroup$ I brute-force went through all binary matrices with $n=m\le6$, and it happens to holds for $Q=Id$ and $Q=J$ on those small sizes. It doesn't hold for many $Q$'s however. I'll list those for which it holds. $\endgroup$ Aug 22 '18 at 16:35
  • 1
    $\begingroup$ Great, I understand your explanation about $Id$. In other words : the first column never increases as a binary number, so it is going to stay the same at some point, as two blocks of $00\ldots0$ and $11\dots1$. At that point the same holds for the 2nd column for each sublock, and so on. $\endgroup$ Aug 23 '18 at 13:31
  • 1
    $\begingroup$ Now get ready for a shock. There is no such general truth for $Q=J$ and period $2$. For a few $6\times 7$ binary matrices, the period is $4$. For a few others, it is $6$. Some others, $3$. I'll show you those counterexamples in an answer. I'll also explore random big matrices to see better. $\endgroup$ Aug 23 '18 at 13:35
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ What a great precious ( and chocking!) information. I'm going to check if I have a proof of the statement for $Q=J$ and $M$ is the adjacency matrix of a partial order... because I did the "sketch" in my mind a bit quickly,especially to the light of the counterexamples that you found!! $\endgroup$
    – jcdornano
    Aug 25 '18 at 19:30

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.