1
$\begingroup$

Let's take $M$ be a $n\times n$ matrix whose entries are $0$ or $1$. (then we can call it the characteristic matrix of any relation $R_M\subset \left\{a_1,...,a_n\right\}^2$, such that $M_{ij}=1$ iff $(a_i,a_j)\in R$)

$\mathcal C(M)$ is defined to be the matrix that columns are the same than that of $M$ but ordered according to the lexicographic order.

(i.e there exists $M_{\mathcal C}$ permutation matrix such that $\mathcal C(M).M_{\mathcal C}=M$ and such that $[2^n,2^{n-1},...,1]\mathcal C(M)(e_i-e_j)>0$, for any $i,j\in [1,n]$ , where $e_i$ is the column with $0$ everywhere except on the $i$-th projection).

We also define $\mathcal R(M):=(-C(-M^t))^t$

(i.e $\mathcal R(M)$ is obtained by ordering rows of $M$ in the decreasing lexicographic order.) And we now consider $\mathcal L=\mathcal R\,o_,\mathcal C$ and $\mathcal L^2=\mathcal L\,o\,\mathcal L$, that any fixed point is called "cycle matrix". Then a relation that characteristic matrix is a cycle matrix will be said cycle-indexed)

Is it true that for any matrix $M$ there is an integer $k$ such that $\mathcal L^{k+2}(M)=\mathcal L^k(M)$

In other words, is any binary relation on a set, "cycle-indexable"?

-Note that one can chose an ordinal indexation of any set equipped with a binary relation, such that the following consideration are still relevant for infinity...

I think the answer to the question is yes and that it may not be to hard to prove, but my biggest interest, is for the matrices that are both cycle matrix and up-tridiagonal with $1$ on the diagonal. If $M$ is such a matrix, and if $\mathcal L(M)$ is also up-tridiagonal, I will call it an almost ordered matrice. And the reason for this is that characteristic matrix of partial ordered relation are, up to a fine indexation of the partial ordered set, almost ordered matrix. Meaning that for any "order matrix" $M$, you can find $P$ permutation matrix such that $P^t.M.P$ is an almost order. And there is more : for any permutation matrix $P$ and $Q$, we can say that $\mathcal L(P.M.Q) $ is a tridiagonal matrix, it is quite easy to see, but I find this quite nice anyway... There is already plenty of questions that are coming to me and I will ask some specifics ones in other topics. Just to give an example : if you remove elements of a partial ordered "cycle indexed" set, then you trivially get a partial ordered set, but it is quite amazing to constate that the induced indexation is still a cycle-indexation ! [edit : this is only true fore some éléments of the ordered set, like the one with top index :maybe it is true in a lattice if the removed element is a meet-irreducible... but I've got to check, however characterizing these elements that when you remove them, you still get a cycle, seems interesting)] this is far from being true for general matrices/relations!) I also suspect that this very simple $\mathcal L$ could have applications to lattices and to graph theory (cycle matrix of symmetric matrix is not always symmetric "but" ...?...), complexity (how many cycle indexation compare to $(n!)^2$...) and also other areas (arithmetic progression seem concerned too...), but before going into this work, and in order to get a direction and an evaluation of the application and the "meaning" of this "almost transitivity" that would have an anti-symmetric and reflexive relation that would not be a "partial" but an "almost order", I'm going to ask a question that is a bit general :

Is there a nice characterization of tridiagonaly cycle-indexed relations ("almost order") ?

I would be pleased with any answer that would give some interesting properties even if not a proper characterization**, and I also would like to know if this subject has already been treated in literature...

**If there is not such a "nice" characterization, maybe there is useful properties that we can use in a smart=relevant generalization of partial orders. For if there is no "nice" characterization, it could even be more exciting, because that would kind of suggest that it is potentially a mean-full or self-mean concept...

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.