# Generalizing cycle/pseudo-tree factorizations for permutations/transformations to arbitrary binary relations

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?