Transformation Monoid

What happens when we consider every possible way to map a set of items to itself and then chain these actions together? This simple premise gives rise to a powerful algebraic object: the transformation monoid. While the study of reversible actions leads to the elegant world of groups, the inclusion of irreversible, information-losing functions creates a far richer and more complex landscape. This article aims to demystify this structure, bridging the gap between its abstract definition and its tangible impact. We will first delve into the core principles and mechanisms governing these transformations, exploring key concepts like idempotents, cancellativity, and the profound ordering provided by Green's relations. Subsequently, we will witness these ideas in action, discovering the surprising connections between transformation monoids and diverse fields such as computer science, number theory, and graph theory. Let us begin our exploration by examining the fundamental building blocks of this versatile algebraic world.

Imagine a collection of simple machines. Each machine takes an object from a specific set of locations, say $\{1, 2, 3\}$, and moves it to another location within that same set. One machine might swap the objects at positions 1 and 2. Another might take any object, no matter where it is, and move it to position 3. The world of these machines—all possible functions from a set to itself—is what we are about to explore. When we start connecting these machines in series, letting the output of one become the input of the next, we are performing ​​function composition​​. This simple act of chaining functions together gives rise to a rich and beautiful algebraic structure known as a ​​transformation monoid​​.

A ​​monoid​​ is a simple concept: it's a set of things (here, our functions) with a way to combine them (composition) that is associative, and it contains a special "do-nothing" element. For transformations, this is the ​​identity function​​, $id$, which leaves every object in its original place. It's the equivalent of a straight piece of wire that passes a signal through unchanged. Associativity, the rule that $(f \circ g) \circ h = f \circ (g \circ h)$, is just a statement of common sense: the net effect of three machines chained together doesn't depend on whether you group the first two or the last two first.

If we limit ourselves only to functions that are fully reversible—those that shuffle objects around without losing any or leaving any spots empty—we get a very tidy, well-behaved structure called a ​​group​​. These reversible functions are the ​​bijections​​, the aristocrats of the function world. But the transformation monoid is a much wilder, more democratic place. It includes every possible function, and most of them are not so well-behaved. Let's meet some of the locals.

First, we have the ultimate information destroyers: the ​​constant functions​​. A function like $f(x) = c$ for all $x$ is a machine that takes any input and produces the exact same output, $c$. These functions are the "dictators" of the monoid. Once a constant function has acted, no subsequent function in the chain can change the final outcome. This is because $(c \circ g)(x) = c(g(x)) = c$, meaning $c \circ g = c$. In the language of algebra, these are called ​​left-zeros​​. The transformation monoid on a set with $n$ elements has exactly $n$ such left-zeros, one for each possible constant output. Interestingly, there are no ​​right-zeros​​—no function $f$ (other than on a single-element set) for which $g \circ f = f$ holds for every possible $g$.

Next, we encounter the ​​idempotent functions​​. An idempotent function is one that, if you apply it twice, gives the same result as applying it once: $f \circ f = f$. Think of a machine that projects 3D objects onto a 2D screen. The first time you use it, a sphere becomes a circle. If you feed that flat circle back into the projector, it just comes out as the same circle. The operation has stabilized. Idempotent functions have a wonderfully elegant internal structure: the set of all possible outputs of an idempotent function (its ​​image​​) is precisely the set of all points that the function leaves unchanged (its ​​fixed points​​). For any point $y$ in the image of an idempotent $f$, it must be that $f(y) = y$. This insight allows us to systematically construct and count all idempotent functions on a set. For a set of 3 elements, for instance, there are 10 such functions, only one of which is the identity map.

In the familiar arithmetic of numbers, we take certain rules for granted. For instance, if $a \times b = a \times c$ and $a$ isn't zero, we can confidently cancel $a$ from both sides. Does this logic hold in the transformation monoid?

Let's find out. Consider the set $\{1, 2\}$ and the four functions on it: the identity $id$, the swap $t$, the constant-1 function $c_1$, and the constant-2 function $c_2$. Now, let's look at the composition $c_1 \circ id$. This just gives $c_1$. What about $c_1 \circ t$? This also gives $c_1$, because no matter how $t$ shuffles the inputs, $c_1$ will map the result to 1. So we have $c_1 \circ id = c_1 \circ t$, but clearly $id \neq t$. We cannot cancel $c_1$! This failure of ​​cancellativity​​ is a direct consequence of having functions that are not one-to-one (injective). Because $c_1$ maps both 1 and 2 to the same output, it erases information, and this loss of information prevents us from working backwards. A similar argument shows that the existence of functions that are not onto (surjective) breaks right-cancellativity. The transformation monoid is a non-cancellative world.

This leads us to a deeper question about "undoing" functions—the concept of an inverse. A ​​left inverse​​ $g$ for a function $f$ is one that undoes it from the left: $g \circ f = id$. A ​​right inverse​​ $h$ undoes it from the right: $f \circ h = id$.

• For $g \circ f$ to be the identity, $f$ must not have merged any two distinct inputs, because if it did, $g$ would have no way to know which original input to map back to. In other words, having a left inverse requires $f$ to be ​​injective​​.
• For $f \circ h$ to be the identity, its image must be the entire set. This means that $f$ must be able to produce every possible output. In other words, having a right inverse requires $f$ to be ​​surjective​​.

Here, we stumble upon a profound difference between finite and infinite worlds. On a ​​finite set​​, the famous pigeonhole principle tells us that a function from the set to itself is injective if and only if it is surjective. You can't place $n$ items into $n$ boxes without repetition unless you use every single box. This means that for a function on a finite set, having a left inverse guarantees it has a right inverse, and vice-versa. There are no "one-sided" invertible functions; a function is either fully invertible (a bijection) or has no inverse at all.

On an ​​infinite set​​, this equivalence shatters. Consider the natural numbers $\mathbb{N}=\{1, 2, 3, \dots\}$. The function $f(n) = n+1$ shifts every number up by one. It is clearly injective (no two numbers have the same successor), but it is not surjective (it misses 1). Therefore, it has a left inverse (e.g., the function $g$ where $g(n)=n-1$ for $n>1$ and $g(1)=1$) but can have no right inverse. Similarly, the function $f(n)=2n$ is injective but not surjective. These functions possess left inverses but no right ones, a phenomenon impossible in the finite realm.

While the transformation monoid may seem chaotic compared to a group, it is governed by its own deep and elegant principles. A key property is that it is a ​​regular semigroup​​. This means that for any function $f$, no matter how complicated or information-destroying, there always exists another function $g$ such that $f \circ g \circ f = f$. This $g$ is called a generalized inverse.

What does this equation mean? It tells us that we can find a function $g$ that acts as a partial "undo" button. The function $g$ takes the outputs of $f$ and maps them back to some valid original inputs in such a way that applying $f$ again restores the original result of $f$. This guarantees a kind of structural resilience; no function is ever truly "lost" in the monoid, as it can always be recovered from itself with the help of a suitable partner.

This underlying regularity is best understood through a powerful classification scheme known as ​​Green's relations​​. These relations partition all the functions in the monoid into families, or classes, based on their fundamental structure. Two of the most important are the $\mathcal{L}$ and $\mathcal{R}$ relations.

• Two functions $f$ and $g$ are ​​$\mathcal{L}$-related​​ if they can be transformed into one another by composing with some other functions on the left (i.e., $h \circ f = g$ and $k \circ g = f$ for some $h, k$). This abstract algebraic definition has a stunningly simple translation: $f$ and $g$ are $\mathcal{L}$-related if and only if they have the same ​​kernel​​. The kernel of a function is the way it partitions the domain—which sets of inputs get mapped to the same output. So, two functions are in the same $\mathcal{L}$-class if they "glue together" their inputs in the exact same pattern. For example, all constant functions on a set are $\mathcal{L}$-related because they all have the "universal" kernel that glues every single input element together.

• Dually, two functions $f$ and $g$ are ​​$\mathcal{R}$-related​​ if they can be transformed into one another by composing on the right ($f \circ h = g$ and $g \circ k = f$). The beautiful corresponding property here is that $f$ and $g$ are $\mathcal{R}$-related if and only if they have the same ​​image​​. That is, they land on the exact same set of outputs, even if they get there from different inputs.

These relations reveal that the apparent chaos of the transformation monoid is an illusion. Beneath the surface lies a "crystal" structure, where functions are neatly sorted by their most fundamental properties: what they merge (kernel) and where they land (image). It is a perfect example of how mathematics uncovers profound and beautiful order in what at first appears to be a world of arbitrary complexity.

Now that we have acquainted ourselves with the principles and mechanisms of transformation monoids, we are ready to embark on a journey. It is a journey to see where this seemingly abstract idea comes alive. You might be surprised to find that we are not venturing into some remote, esoteric corner of science. Instead, we will find these structures in the very heart of computation, in the patterns of numbers, in the symmetries of networks, and even in the swirling unpredictability of chance. The transformation monoid is the secret language describing action, and once you learn to recognize it, you will begin to see it everywhere.

Let's start where the idea feels most at home: in the world of simple computing devices known as finite automata. Imagine a machine designed to read a string of 0s and 1s and tell you if it has ever seen the sequence "01". This machine has a few states of "memory"—perhaps a "start" state, a "just saw a 0" state, and an "accept" state (because "01" was seen). Each input symbol—a 0 or a 1—causes a transformation, a change from one state to another.

What is the collection of all possible transformations this machine can undergo? It's not infinite! Although we can feed it infinitely many different strings, many strings end up having the exact same overall effect on the machine's states. For instance, the strings "111" and "1" both leave the machine in whatever state it started. The strings "00" and "0" both move the machine to the "just saw a 0" state. When we collect all the unique transformations induced by all possible input strings, we get the machine's transformation monoid. This monoid, a finite set of functions, is the machine's true character, its computational "soul." It tells us everything about what the machine can do.

This connection between machines and algebra can be stunningly elegant. Consider a machine that accepts strings of 'a's whose length is a multiple of $k$. Its internal states simply count the number of 'a's seen, modulo $k$. The transformations on these states correspond to adding numbers modulo $k$. And so, the transformation monoid of this machine is none other than the familiar cyclic group $\mathbb{Z}_k$, the group of integers under addition modulo $k$. A simple computational task has an equally simple and beautiful algebraic soul.

This algebraic viewpoint gives us incredible predictive power. What if we want to know if a machine's decision depends only on the last few symbols it has read? Such a language is called "definite." We don't need to test infinite strings to find out. We can just look at its monoid. A machine recognizes a definite language if and only if its monoid has a special property: any transformation corresponding to a sufficiently long input string becomes a "constant" function—it sends all possible starting states to the same single destination state. It's a "reset." The machine's memory is wiped clean, and its state now depends only on that final, resetting sequence of inputs. The behavior of the language is perfectly mirrored in the structure of its algebra.

The algebraic structures that emerge are not always as simple as cyclic groups. Sometimes, they contain beautiful and surprising complexity. Let’s look at a problem from number theory: how can we build a machine that recognizes binary numbers divisible by 3? The machine only needs three states, corresponding to the remainder of the number seen so far when divided by 3 (0, 1, or 2).

What is the "soul" of this machine? When we analyze the transformations induced by the inputs '0' and '1', we find they don't just move states around; they permute them. The input '0' swaps state 1 and state 2, while leaving state 0 fixed. The input '1' swaps state 0 and state 1, leaving state 2 fixed. What happens when we compose these transformations over and over? We generate a group of six permutations—the full set of ways to reorder three things. This is the symmetric group $S_3$! A simple question of divisibility gives rise to a rich, non-commutative algebraic structure.

This discovery—that groups can be "hiding" inside these monoids—is profound. It means that some sequences of actions don't degrade information into a reset; they shuffle it, reversibly. We can even hunt for the specific strings that correspond to specific permutations. In one such automaton, for example, the input string "xy" might be precisely the sequence of actions needed to produce the permutation that swaps state 1 and state 3 while leaving state 2 alone. This interplay between groups of permutations and "reset" transformations is the key to the famous Krohn-Rhodes theorem, which states that any automaton, no matter how complex, can be constructed by wiring together simpler components that perform either group-like permutations or resets. It is the fundamental theorem of finite automata, and its language is that of transformation monoids.

Even the physical diagram of the machine, its state graph, holds algebraic secrets. The "loopy" parts of the graph—the simple cycles where the machine can run in circles—correspond directly to special transformations in the monoid known as "idempotents." An idempotent is an action that, once done, changes nothing if you do it again. It has stabilized. There is a deep and beautiful theorem which states that the number of distinct simple cycles in a machine's graph is directly related to the number of these stabilizing, idempotent elements in its monoid. The geometry of the machine is perfectly reflected in the algebra of its actions.

The power of this idea extends far beyond automata. A transformation monoid is simply the set of all structure-preserving maps of an object into itself. What if the object isn't an automaton?

• ​​In Graph Theory:​​ Let's consider a graph, for instance, a simple triangle (the complete graph $K_3$). What are its "transformations"? They are mappings of its vertices to themselves that preserve the edge structure—if two vertices were connected, their images must be connected or identical. These are called graph endomorphisms. For a complete graph like $K_3$, any such transformation must be either a permutation of the vertices or a constant map. The endomorphism monoid of $K_3$ is therefore composed of the symmetric group $S_3$ and the three constant maps. It is a moment of pure scientific joy to see the same core algebraic group, $S_3$, emerge in structures from two completely different worlds: recognizing numbers divisible by 3, and preserving the symmetries of a triangle.

• ​​In Probability Theory:​​ Imagine a system that jumps between different states according to certain probabilities—a Markov chain. When is such a system "irreducible," meaning it's possible to get from any state to any other state? This is a fundamental question about the system's long-term behavior. The structure of the monoid of possible transitions holds the key. For instance, a strong condition that guarantees irreducibility is if the invertible transformations within the monoid form a group that acts transitively on the set of states. More generally, the algebra of the underlying transformations dictates the connectivity and ergodic properties of the entire probabilistic system.

• ​​In Engineering and Control Systems:​​ Many systems, from digital circuits to robotic controllers, can be modeled as Mealy machines, which not only change state but also produce an output at each step. We can still study the semigroup of their internal state transformations. We might ask: under what conditions do these transformations form a group, implying every action is reversible? For a certain family of such machines, the answer is not found in logic or engineering, but in number theory. The transformations form a group precisely when a parameter $k$ is coprime to the number of states $n$ (i.e., $\gcd(k, n) = 1$). The microscopic behavior of the system is governed by macroscopic number-theoretic properties.

We have seen transformations on states, vertices, and numbers. What is the most general kind of "thing" we can transform? The answer comes from the highly abstract field of category theory, which studies mathematical structures and the relationships between them.

Let's think not about a single set, but about the process of making a list. This process, or "functor," can take any set (of numbers, of people, of other lists) and produce the set of all possible lists from it. Now, what is a "transformation" of this list-making process itself? It would have to be a rule that can be applied to any list, regardless of what's inside it. Examples include "reverse the list," "delete every other element," "duplicate the entire list," or "create a new list using the 1st, 3rd, and 2nd elements of the original."

These "natural transformations" on the list functor form a monoid themselves! The composition is just doing one after the other. This monoid is astoundingly complex and beautiful. Its elements can be described by an infinite sequence of "instruction words" that specify, for each possible list length, how to reorder, duplicate, or delete its elements. This is the idea of a transformation monoid taken to its ultimate conclusion—a monoid of operations on operations.

From the concrete gears of a finite machine to the ethereal realm of universal processes, the transformation monoid provides a unifying thread. It is a testament to one of the deepest truths in science: that the study of actions and their compositions—the simple question of what happens when you "do this, then do that"—has a rich and beautiful algebraic structure that echoes through countless fields of human inquiry.