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:

PLACEHOLDER FOR INFORMATION TO BE FILLED IN: [SHOW MORE]

One of the people editing this page intended to fill in this information at a later stage, but hasn't gotten around to doing it yet. If you see this placeholder for a long time, file an error report at the error reporting page.

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\geq 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.