Understanding the cycle decomposition

This is a survey article related to:cycle decomposition for permutations
View other survey articles about cycle decomposition for permutations

A permutation on a set $S$ is a bijective map from $S$ to itself. There are many ways of describing permutations: one way is to give a formula for the function; another is to write the permutation down using the one-line or two-line notation. However, these ways of writing permutations down often fail to provide a feel for the dynamics of a permutation, and its group-theoretic nature.

The cycle decomposition of a permutation is a form of expressing the permutation that captures its dynamics as well as its group-theoretic behavior. This survey article builds the idea of cycle decompositions in a number of ways, and provides some useful examples.

The directed graph associated with a function

Description of the directed graph

Suppose $S$ is a set and $f:S\to S$ is a function. We define the directed graph associated with $f$ as follows.

• The vertices, or points, or nodes, of the graph are the elements of $S$. In other words, we begin by drawing all the elements of $S$ as separate points.
• There is a directed edge from a vertex $u$ to a vertex $v$ if and only if $f(u)=v$. Note that if $u=f(u)$, we get a directed edge from $u$ to itself -- this is called a loop.

Notice the following:

• Since $f$ is a function, there is a unique value of $f(u)$ for every $u\in S$. Thus, there is a unique directed edge coming out from $u$, and this edge is headed towards $f(u)$.
• The edges coming to $v\in S$ represent all the points $u\in S$ such that $f(u)=v$.
• $f$ is injective if and only if, for every $v\in S$, there is at most one edge entering $v$.
• $f$ is surjective if and only if, for every $v\in S$, there is at least one edge entering $v$.
• $f$ is bijective if and only if, for every $v\in S$, there is exactly one edge entering $v$.

Finite examples

Suppose $S$ is the set $\{1,2,3,4\}$ and the function $f$ is defined by:

$f(1)=3,f(2)=2,f(3)=2,f(4)=1$.

The directed graph associated with $f$ looks like this:

Notice that $f$ is neither injective nor surjective. Both $2$ and $3$ map to $2$, leading to the vertex $2$ having an indegree of two -- two incoming edges. On the other hand, the vertices $3$ and $4$ have indegrees of zero -- there are no incoming edges to these vertices.

In contrast, consider the function:

$f(1)=4,f(2)=5,f(3)=3,f(4)=2,f(5)=1$.

This function is bijective, and the graph clearly shows this:

Infinite examples

In the infinite case, there are examples of functions that are injective and not surjective, and there are also examples of functions that are surjective but not injective. Here are some, along with finite fragments of their graphs:

• The function $x\mapsto 2x$ on the set of integers. This is injective, but not surjective: its image is the set of even integers. The picture makes this clear.
• The function that sends $x$ to $x/2$ if $x$ is even and to $x$ if $x$ is odd. This is surjective (every element is the image of its double) but is not injective (the odd numbers have two incoming edges).

The inverse of a bijective function

If $f:S\to S$ is bijective, i.e., $f$ is a permutation, the directed graph associated with $f$ has the property that every vertex has indegree one and every vertex has outdegree one. Further, there is a simple relation between the graph of $f$ and the graph of $f^{-1}$.

For any $v\in S$, $f^{-1}(v)$ is the unique $u$ satisfying $f(u)=v$. In other words, it is the starting point of the directed edge that ends at $v$. This suggests that if we reverse the direction of the edge, we get an edge sending $v$ to $f^{-1}(v)$.

The upshot: given a bijective function, the directed graph of the inverse function is obtained by simply reversing the direction on all edges in its directed graph.

Iteration and dynamics

Another advantage of the directed graph is that it helps see what happens on iterating the function. To understand this, recall that to know $f(u)$, we need to start at $u$ and flow along the unique edge emanating from $u$. Thus, to find $f(f(u))$, we need to first reach $f(u)$, and then flow along the unique edge emanating from that point. More generally, to find $f^{(n)}(u)$, we need to start at $u$ and move forward $n$ steps along the edges of the graph.

The cycle decomposition: how it can loop back

We already understand the local picture for the directed graph associated with a permutation. Let's try to understand the implications of this picture more closely.

Suppose $f:S\to S$ is a permutation (i.e., a bijective function). Suppose I start at a point $u\in S$ and consider the sequence of points $u,f(u),f(f(u)),f(f(f(u)),\dots$. Essentially, I start at the point $u\in S$ and move forward along the edges of the graph.

Notice the following: if I ever repeat a point, the first point I repeat must be $u$. To see this, observe that if $f^{(j)}(u)=f^{(k)}(u)$, and $j>k\ge 1$, then $f(f^{(j-1)}(u))=f(f^{k-1}(u))$, and the injectivity of $f$ yields that $f^{(j-1)}(u)=f^{(k-1)}(u)$. A downward induction thus shows that $f^{(j-k)}(u)=u$.

This can also be seen pictorially: the graph cannot loop back to a point other than $u$, because this point already has an incoming edge. Thus, the graph must loop back to $u$ itself, or not loop back at all.

Note that when $f$ is not injective, the graph can cycle back to a point other than $u$, giving a classic $\rho$ shape.

The cycle decomposition: cycles or chains

When $S$ is a finite set and $f$ is a permutation of $S$, we know that if we start moving along from any vertex $u$ along the graph, we'll eventually repeat a vertex. The remarks made above thus show that we get a cycle at $u$.

When $S$ is infinite, cycles are not the only possibility. It is also possible that applying $f$ repeatedly never returns to the original point. An example is the translation map on the group of integers: the map $x\mapsto x+1$. Here, iterating the permutation keeps the point moving to the right, and there is no looping back.

If there is no looping back, we can also go backward for an infinite duration without looping back. For instance, for the map $x\mapsto x+1$, for which there is no looping back, the inverse map $x\mapsto x-1$ also has no looping back. Thus, instead of a cycle, we obtain a straight chain extending indefinitely in both directions.

Note that for an injective map (as opposed to a bijective map) there may exist chains that extend indefinitely in the forward direction, but can be extended only to a finite extent in the backward direction. An example is the map $x\mapsto x+1$ on the set of positive integers.

The cycle decomposition: obtaining the decomposition

We've seen that starting from any element $u$, we can trace either a cycle or a chain containing $u$, obtained by following the flow of the edges. Explicitly, the cycle of $u$ gives, in (cyclic) sequence the points $f^{(j)}(u)$.

Since every element has its own unique cycle or chain, the cycles and chains form a partition of the whole set $S$. In the finite case, there are no chains, so the set $S$ is partitioned as a union of disjoint cycles.

Here is another way of thinking about the cycle decomposition. We start with a point $u\in S$ and trace the cycle of $u$. Note that for any point in the cycle of $u$, the cycle of that point is the same as the cycle of $u$. Now, if the cycle contains all points of $S$, we are done. Otherwise, pick a point not in the cycle, and trace its cycle. This cycle cannot intersect the previous cycle, since that would contradict the fact that there is a unique edge coming into every vertex. Thus, we get a new cycle, that covers some new elements. We repeat this process until the whole finite set is covered.

In infinite sets, this repeat until idea cannot be used in a naive sense, but the more sophisticated idea of being in the same cycle as an equivalence relation works.