Understanding the cycle decomposition

From Groupprops
Jump to: navigation, search
This is a definition understanding article -- an article intended to help better understand the definition(s):cycle decomposition for permutations
View other definition understanding articles| View other survey articles about cycle decomposition for permutations

A permutation on a set S is a bijective map from S to itself. The permutations on a set form a group under composition; this group is termed the symmetric group.

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.

To get a full list of cycle decompositions of permutations written alongside the one-line notation, see element structure of symmetric group:S3#Elements and element structure of symmetric group:S4#Elements.

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:

Cycledecomposition1.png

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 vertex 4 has an indegree of zero -- there are no incoming edges to this vertex.

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:

Cycledecomposition2.png

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.

Cycledecomposition3.png

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

Further information: cycle decomposition theorem for permutations

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.

Some easy examples

Integers modulo seven with some polynomial maps

Let G be the group of integers modulo seven under addition. In other words, we have:

\! G = \{ 0,1,2,3,4,5,6 \}.

Suppose f:G \to G is the map:

\! f(x) = 2x + 3.

We want to determine the cycle decomposition for f.

First, we compute the images of all the elements of G under f. We have:

\! f(0) = 3, f(1) = 5, f(2) = 0, f(3) = 2, f(4) = 4, f(5) = 6, f(6) = 1

Cycledecomposition4.png

Notice that the cycle decomposition makes clearly visible some things that are not so obvious otherwise: there is exactly one fixed point (the element 4, which has a loop around it) and there are two cycles of size three each.

Here's another map:

\! f(x) = 3x^5 + 1

For this, we obtain:

\! f(0) = 1, f(1) = 4, f(2) = 6, f(3) = 2, f(4) = 0, f(5) = 3, f(6) = 5.

We now make the cycle decomposition:

Cycledecomposition5.png

From the cycle decomposition, we see that there is a 4-cycle \! (2,6,5,3) and a 3-cycle \! (0,1,4).

Writing the cycle decomposition

Writing each cycle

Each cycle is written in parentheses, with the members of the cycle written in cyclic order. In other words, the image of any member under the permutation is the next member, and the image of the right-most member is the left-most member. The cycle decomposition involves juxtaposing the expressions for each of the cycles.

The individual members of the cycle are preferably separated by commas, although some abbreviated conventions allow for simply writing the members without separating symbols.

For instance, the permutation described above on the set \! G = \{ 0,1,2,3,4,5,6 \}:

\! f(x) = 2x + 3

Cycledecomposition4.png

The cycle decomposition of this is written as:

\! (1,5,6)(0,3,2)(4)

The order in which the individual cycles are written does not matter, so this is the same as:

\! (0,3,2)(1,5,6)(4)

or:

\! (0,3,2)(4)(1,5,6).

Finally, within each cycle, the ordering of elements can be permuted cyclically, so (1,5,6) can be rewritten as (5,6,1). However, it is not the same as (1,6,5), because the latter sends 1 to 6, rather than to 5.

For the second example:

Cycledecomposition5.png

we can write the cycle decomposition as:

\! (2,6,5,3)(0,1,4).

Thus, there are two sources of ambiguity in the expression for the cycle decomposition:

  • The ordering between cycles is immaterial -- any ordering is fine.
  • Within a cycle, the choice of which element to start the cycle with is arbitrary. Once the left-most element of the cycle is chosen, subsequent elements are decided (because each is the image of its predecessor).

Omission of fixed points

When writing the cycle decomposition, we can omit cycles of size 1, i.e., fixed points. Thus, the permutation above:

\! (0,3,2)(4)(1,5,6)

can be written as:

\! (0,3,2)(1,5,6)

Computation using cycle structure

Cycle type of a permutation

Further information: cycle type of a permutation, cycle type determines conjugacy class

The cycle type of a permutation is the information comprising the sizes of its cycles. For instance, if a permutation has two cycles of size three and one cycle of size one, we say that it has cycle type (3,3,1).

Note that the cycle type of a permutation corresponds to an unordered tuple of natural numbers that add up to the total size of the set. Thus, it corresponds to an unordered integer partition of the size of the set. In particular:

Cycle types of permutations on a set \leftrightarrow Unordered integer partitions of the size of the set

A few things should be noted carefully:

  • The cycle type is unordered. Thus, a cycle type of (3,3,1) is the same as a cycle type of (3,1,3) or (1,3,3).
  • What really matters in the cycle type is the number of cycles of each size. Thus, we can store the information of the cycle type as an ordered list where that j^{th} member is the number of cycles of size j. (This point is a little tricky). For instance, a cycle type of (3,3,1) can be stored using the ordered list 1,0,2, indicating that there is one cycle of size one, zero cycles of size two, and two cycles of size three.

Computing the powers of a permutation

The cycle structure of a permutation is a very convenient tool for computing its powers. For instance, to compute the j^{th} power of a permutation, we simply start at a vertex, and flow along the arrows in its cycles j steps. To compute the inverse of a permutation, we go backward along the cycle.

For instance, the dotted lines below demonstrate the cycle decomposition of the inverse permutation to our first example:

Cycledecomposition4rev.png

Thus we get:

\! ((0,3,2)(1,5,6))^{-1} = (2,3,0)(6,5,1)

Note that fixed points remain fixed points, so they do not need to be written on either side.

Next, we show how the square of the second permutation is computed, with the dotted arrows representing the cycle decomposition of the square permutation:

Cycledecomposition5rev.png

In symbols, we have:

\! ((2,6,5,3)(0,1,4))^2 = (2,5)(6,3)(4,1,0)

Computing the order of a permutation

The order of a permutation is the least common multiple of the orders of all the cycles that comprise that permutation. To see this, note that for the j^{th} power of a permutation to be the identity map, it should cycle each element back to itself.

For instance, the first permutation has a cycle decomposition with cycles of sizes 3,3,1, so the order is 3. For the second permutation, the cycles have sizes 3 and 4, so the order is 12.