Any permutation on a finite set can be expressed as a product of disjoint cycles.
(https://groupprops.subwiki.org/wiki/Cycle_decomposition_theorem_for_permutations)
What about a transformation (an arbitrary map of a set onto itself)?
Can it be expressed as a product of disjoint transformations of certain kind?
I am trying to adjust the proof from the linked article to transformations:
Let $t$ be a transformation on a finite set $T$.
We can introduce a power of an element $a$ of $T$ in the following way:
- $a^0 = a$,
- $a^{n+1} = t(a^n)$.
Similar to cyclic semigroups, we can introduce the kernel of an element of $T$. (https://en.wikipedia.org/wiki/Monogenic_semigroup)
Let $K_a$ be the kernel of $a$: $K_a = \{ a^{m}, a^{m+1}, ..., a^{m+r-1}\}$, where $m$ is the index, and $r$ is the period of $a$.
Let's say an element $x$ of $T$ falls onto $K_a$ if there is a non-negative integer $k$ such that $x^k \in K_a$.
Let's denote the set of all elements of $T$ that fall onto $K_a$ as $F_a$.
$F_a$ induces the following transformation (let's call it simple):
- $f_a(x) = t(x)$ if $x \in F_a$;
- $f_a(x) = x$ if $x \notin F_a$.
Let's denote the complement set of $F_a$ as $\overline F_a$.
$\overline F_a$ induces the following transformation:
- $\overline f_a(x) = t(x)$ if $x \in \overline F_a$;
- $\overline f_a(x) = x$ if $x \notin \overline F_a$.
It is easy to check that $f_a$ and $\overline f_a$ are disjoint (Disjoint transformations).
Continuing the process for $\overline F_a$, we will get a decomposition of $t$ onto disjoint simple transformations.
Is this correct?
Also, transformations are closely related to semigroups (https://planetmath.org/cayleystheoremforsemigroups).
Is there a theorem of decomposition of semigroups onto sub-semigroups of elements that share the same kernel?
I apologize for my own terminology: I was not able to find the right terms.
An arbitrary map $f : X \to X$ from a finite set to itself has a "cycle-tree decomposition"; this is a very basic and fundamental fact but somewhat shockingly I only know a single reference for this, which is Bergeron, Labelle, and Leroux's Combinatorial Species and Tree-like Structures (Chapter 3), and after poking around in that chapter it's less explicit and has fewer details than I remember somehow.
It goes like this. $f$ has an eventual image $\text{im}^{\infty}(f)$ which can be described as the intersection $\cap_n \text{im}(f^n)$. The elements of the eventual image are exactly the periodic points of $f$ and these decompose into cycles just like permutations do. The remaining elements of $X$ which are not periodic hit a periodic point eventually (by pigeonhole), and if the trajectory of any two points ever coincides at some $f^n$ then they coincide forever after that, so the non-periodic points organize themselves into rooted trees rooted at any point of any of the cycles. In particular the "connected components" are given by each cycle (and all the trees attached to it)
This is a sort of set-theoretic cousin to the Jordan normal form, where the periodic points are analogous to eigenvectors and the non-periodic points are analogous to generalized eigenvectors. If you're familiar with the theory of combinatorial species it can be expressed elegantly as follows (all sets are finite here): "an endofunction is a set of cycles of rooted trees," or in other words the species of endofunctions is a triple composition $\text{End} = \text{Set} \circ \text{Cyc} \circ \text{Tree}$. The corresponding species decomposition for permutations is that "a permutation is a set of cycles," so $\text{Perm} = \text{Set} \circ \text{Cyc}$. This decomposition gives, among other things, Joyal's proof of Cayley's tree formula. This blog post has a picture of a cycle-tree decomposition which will hopefully help:
The case that $X$ is infinite is trickier and I haven't thought about it in as much detail. There is now a new kind of limiting behavior "half-infinite to the right" $0 \to 1 \to 2 \to \dots$ that is non-periodic but instead "escapes to infinity," and a new kind of tree "half-infinite to the left" $\dots -2 \to -1 \to 0$ that can feed in. The eventual image may be empty. I'm not sure what the cleanest way of describing all the possibilities is here.