1
$\begingroup$

It's well known every permutation has a unique factorization into disjoint cycles (up to a re-ordering of these factors since they commute), while similarly it can be shown that every transformation has a unique factorization into disjoint pseudo-trees (again up to a re-ordering of these factors because they commute). Also these factors can be further decomposed into transpositions and idempotents collapsing exactly two elements (for details see: Rhode's/Steinberg's q-theory of finite semigroups). Now, with that said, given any finite binary relation $R$, if we let $L_1,L_2,\dotsc L_n\subseteq R$ be the edge sets of the weakly connected components in the directed graph $D=(\text{dom}(R)\cup\text{rng}(R),R)$, and for every $1\leq k\leq n$ we let $\hat{L}_k=L\cup\{(x,x):x\in\text{dom}(R\setminus L)\cup\text{rng}(R\setminus L)\}$, then we have:

$$R=\hat{L}_1\circ \hat{L}_2\circ \hat{L}_3\circ \dotsb \circ\hat{L}_n$$

where $\circ$ denotes relational composition. Moreover, note the relations $\hat{L}_1,\hat{L}_2,\dotsc, \hat{L}_n$ commute with each other, so that, in fact, for any $\sigma\in S_n$, we have $R=\hat{L}_{\sigma(1)}\circ \hat{L}_{\sigma(2)}\circ \hat{L}_{\sigma(3)}\circ \cdots \circ\hat{L}_{\sigma(n)}$. Thus this decomposition for the binary relation $R$ is always unique except for the order in which these factors are being composed together.

Now this result can be seen as a generalization of the facts mentioned at the start, namely, if $R$ is the functional graph of a permutation, we see $\hat{L}_1,\hat{L}_2,\dotsc, \hat{L}_n$ are disjoint cycles, while, if $R$ is the functional graph of a transformation, then $\hat{L}_1,\hat{L}_2,\dotsc, \hat{L}_n$ are disjoint pseudo-trees. Where, as noted at the beginning for these two special cases, we can further decompose the factors $\hat{L}_1,\hat{L}_2,\dotsc, \hat{L}_n$ into transpositions/idempotents collapsing exactly two elements.

Now my question is, in our general case where $R$ is not necessarily a permutation/transformation but rather an arbitrary binary relation, can we also decompose the factors $\hat{L}_1,\hat{L}_2,\dotsc, \hat{L}_n$ into smaller constituents, similar to how we can decompose transformations into transpositions/idempotents?

$\endgroup$
1
$\begingroup$

The situation for binary relations is more complicated than for transformations. Of course your weak component relations can be further decomposed, but into what is less clear. The symmetric groups and the full transformation monoids have generating sets with the same number of generators in all degrees. It was proved by Devadze, see https://link.springer.com/article/10.1007/s00233-011-9305-y, that the minimal number of generators for binary relations on an n-element set grows exponentially in n.

The key issue is the existence of prime relations, ones which if factored must have one of the factors a unit. These are non regular elements and each generating set must contain a representative of each orbit of prime relations under the two sided action of permutations.

$\endgroup$

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.