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)

Improve this question
$\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$
    – Andreas Blass
    Commented Jul 22, 2018 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
    Commented Jul 22, 2018 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$
    – Claude Chaunier
    Commented Aug 22, 2018 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$
    – Claude Chaunier
    Commented Aug 23, 2018 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$
    – Claude Chaunier
    Commented Aug 23, 2018 at 13:35

1 Answer 1

Reset to default
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} $$

Improve this answer
$\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
    Commented Aug 25, 2018 at 19:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .