Décomposition d'une transformation finie

Question

Toute permutation sur un ensemble fini peut être exprimée comme un produit de cycles disjoints.
(https://groupprops.subwiki.org/wiki/Cycle_decomposition_theorem_for_permutations)

Qu'en est-il d'une transformation (une carte arbitraire d'un ensemble sur lui-même)?
Peut-il être exprimé comme un produit de transformations disjointes d'un certain type?

J'essaye d'ajuster la preuve de l'article lié aux transformations:

Laisser $t$ être une transformation sur un ensemble fini $T$.
On peut introduire une puissance d'un élément$a$ de $T$ de la manière suivante:

• $a^0 = a$,
• $a^{n+1} = t(a^n)$.

Semblable aux semi-groupes cycliques, nous pouvons introduire le noyau d'un élément de$T$. (https://en.wikipedia.org/wiki/Monogenic_semigroup)

Laisser $K_a$être le noyau de$a$: $K_a = \{ a^{m}, a^{m+1}, ..., a^{m+r-1}\}$, où $m$est l' indice , et$r$est la période de$a$.
Disons un élément$x$ de $T$ tombe sur$K_a$ s'il y a un entier non négatif $k$ tel que $x^k \in K_a$.
Notons l'ensemble de tous les éléments de$T$ qui tombent sur $K_a$ comme $F_a$.
$F_a$ induit la transformation suivante (appelons-la simple ):

• $f_a(x) = t(x)$ si $x \in F_a$;
• $f_a(x) = x$ si $x \notin F_a$.

Notons l'ensemble complémentaire de $F_a$ comme $\overline F_a$.
$\overline F_a$ induit la transformation suivante:

• $\overline f_a(x) = t(x)$ si $x \in \overline F_a$;
• $\overline f_a(x) = x$ si $x \notin \overline F_a$.

Il est facile de vérifier que $f_a$ et $\overline f_a$sont disjoints (https://math.stackexchange.com/q/3834607/427611).
Poursuivre le processus pour$\overline F_a$, nous obtiendrons une décomposition de $t$sur des transformations simples disjointes .
Est-ce correct?

En outre, les transformations sont étroitement liées aux semi-groupes (https://planetmath.org/cayleystheoremforsemigroups).
Existe-t-il un théorème de décomposition des semigroupes en sous-semigroupes d'éléments partageant le même noyau?

Je m'excuse pour ma propre terminologie: je n'ai pas pu trouver les bons termes.

Answer 1

Une carte arbitraire $f : X \to X$d'un ensemble fini à lui-même a une "décomposition en arbre de cycle"; c'est un fait très basique et fondamental mais quelque peu choquant je ne connais qu'une seule référence pour cela, qui est Bergeron, Labelle et Lerouxhttp://bergeron.math.uqam.ca/Species/especes.html (Chapitre 3), et après avoir fouillé dans ce chapitre, il est moins explicite et contient moins de détails que je ne m'en souviens.

Ça va comme ça. $f$a une éventuelle image $\text{im}^{\infty}(f)$ qui peut être décrit comme l'intersection $\cap_n \text{im}(f^n)$. Les éléments de l'image éventuelle sont exactement les points périodiques de$f$et ceux-ci se décomposent en cycles comme le font les permutations. Les éléments restants de$X$ qui ne sont pas périodiques atteignent éventuellement un point périodique (par casier), et si la trajectoire de deux points quelconque coïncide jamais à certains $f^n$puis ils coïncident pour toujours après cela, de sorte que les points non périodiques s'organisent en arbres enracinés enracinés à n'importe quel point de l'un des cycles. En particulier les «composants connectés» sont donnés par chaque cycle (et tous les arbres qui y sont attachés)

Il s'agit d'une sorte de cousin théorique des ensembles à la forme normale de Jordan, où les points périodiques sont analogues aux vecteurs propres et les points non périodiques sont analogues aux vecteurs propres généralisés. Si vous connaissez la théorie dehttps://en.wikipedia.org/wiki/Combinatorial_species il peut s'exprimer avec élégance comme suit (tous les ensembles sont ici finis): «une endofonction est un ensemble de cycles d'arbres enracinés», ou en d'autres termes l'espèce d'endofonctions est une triple composition $\text{End} = \text{Set} \circ \text{Cyc} \circ \text{Tree}$. La décomposition d'espèces correspondante pour les permutations est que "une permutation est un ensemble de cycles", donc$\text{Perm} = \text{Set} \circ \text{Cyc}$. Cette décomposition donne, entre autres,https://golem.ph.utexas.edu/category/2019/12/a_visual_telling_of_joyals_pro.html. Cet article de blog a une image d'une décomposition de l'arbre de cycle qui, espérons-le, aidera:

Le cas qui $X$est infini est plus délicat et je n'y ai pas réfléchi avec autant de détails. Il existe désormais un nouveau type de comportement limitant "à moitié infini vers la droite"$0 \to 1 \to 2 \to \dots$ c'est-à-dire non périodique mais au contraire "s'échappe à l'infini", et un nouveau type d'arbre "demi-infini à gauche" $\dots -2 \to -1 \to 0$qui peut alimenter. L'image éventuelle peut être vide. Je ne sais pas quelle est la manière la plus claire de décrire toutes les possibilités.

Answer 2

La meilleure référence sur ce sujet est [1]. La section I.2, Graphique d'une transformation (partielle) , couvre en détail la décomposition du graphique également mentionnée dans la réponse de Qiaochu Yuan. Vous pourriez également être intéressé par le chapitre III, Génération de systèmes .

[1] Ganyushkin, Olexandr; Mazorchuk, Volodymyr. Semi-groupes de transformation finie classique. Une introduction. Algèbre et applications, 9. Springer-Verlag London, Ltd., Londres, 2009. xii + 314 p. ISBN: 978-1-84800-280-7