Cycles and cycle notation

Again we denote by $A = \{1, 2, ..., n\}$ the set on which the permutation acts. We shall frequently denote by $a_i$, $a_j$, etc. arbitrary elements of $A$.

Definition 3.1.1   Suppose that $f$ is a permutation of $A = \{1, 2, ..., n\}$, which has the following effect on the elements of $A$: There exists an element $a_1 \in A$ such that. $f(a1) = a2$, $f(a2) = a3$, ..., $f(a_{k- 1}) = a_k$, $f(a_k) = a_1$, and $f$ leaves all other elements (if there are any) of $A$ fixed, i.e., $f(a_j) = a_j$ for $j\not= 1, 2, ..., k$. Such a permutation $f$ is called a cycle or a $k$-cycle.

We use the following notation for a $k$-cycle, $f$, as given above

$$f = (a_1,a_2, ... ,a_k).$$ (3.1)

Let us elaborate a little further on the notation employed in (3.1). The cycle notation is read from left to right, it says $f$ takes $a_1$ into $a_2$, $a_2$ into $a_3$, etc., and finally $a_k$, the last symbol, into $a_1$, the first symbol. Moreover, $f$ leaves all the other elements not appearing in the representation (3.1) fixed. Note that one can write the same cycle in many ways using this type of notation; e.g., $f = (a_2,a_3, ..., a_k,a_1)$, etc. (How many ways?) Also we call $k$ the length of the cycle. Note we allow a cycle to have length $1$, i.e., $f = (a_1)$; moreover, this is just the identity map. For this reason, we will usually designate the identity of $S_n$ by $(1)$. (Of course, it also could be written as $(a_i)$ where $a_i \in A$.)

If $f$ and $g$ are two cycles, they are called disjoint if the elements moved by one are left fixed by the other, i.e., their representations (3.1) contain different elements of the set $A$ (their representations are disjoint as sets).

We claim that if $f$ and $g$ are disjoint cycles, then they must commute, i.e., $fg = gf$. Indeed, since the cycles $f$ and $g$ are disjoint, each element moved by $f$ is fixed by $g$ and vice versa. First suppose $f(a_i) \not= a_i$. This implies that $g(a_i) = a_i$ and $f^2(a_i) \not= f(a_i)$ (WHY?). But since $f^2(a_i) \not= f(a_i)$, $g(f(a_i)) = f(a_i)$. Thus $(fg)(a_i) = f(g(a_i)) = f(a_i)$ while $(gf)(a_i) = g(f(a_i)) = f(a_i)$. Similarly if $g(a_j)\not= a_j$, then $(fg)(a_j) = (gf)(a_j)$. Finally, if $f(a_k) = a_k$ and $g(a_k) = a_k$ then clearly $(fg)(a_k) = a_k = (gf)(a_k)$. Thus $gf = fg$, proving the claim.

Before proceeding further with the theory, let us consider a specific example. Let $A = \{1, 2, ..., 8\}$ and let

$$f= \left( \begin{array}{cccccccc} 1 & 2 & 3&4&5&6&7 & 8\\ 2& 4& 6&5&1&7&3& 8 \end{array}\right)$$

using the representation in (2.1). We pick an arbitrary number from the set $A$, say $1$. Then $f(1) = 2$, $f(2) =4$, $f(4) =5$, $f(5) = 1$. Now select an element from $A$ not in the set $\{1, 2, 4, 5\}$, say $3$. Then $f(3) = 6$, $f(6) = 7$, $f(7) = 3$. Next select any element of $A$ not occurring in the set $\{1, 2, 4, 5\}\cup \{3, 6, 7\}$. The only element left is $8$, and $f(8) = 8$. It is clear that we can now write the permutation $f$ as a product of cycles:

$$f = (1,2,4,5) (3,6,7) (8),$$

where the order of the cycles is immaterial since they are disjoint and therefore commute. It is customary to omit such cycles as $(8)$, i.e., elements left fixed by $f$, and write $f$ simply as

$$f = (1245) (367);$$

it being understood that the elements of $A$ not appearing are left fixed by $f$.

It is not difficult to generalize what was done here for a specific example, and show that any permutation $f$ can be written uniquely, except for order, as a product of disjoint cycles. Thus let $f$ be a permutation on the set $A = \{1, 2, ... n\}$, and let $a_1 \in A$. Let $f(a_1) = a_2$, $f^2(a_1) = f(a_2) = a_3$, etc., and continue until a repetition is obtained. We claim that this first occurs for $a_1$, i.e., the first repetition is say $f^k(a_1) = f(a_k) = a_{k+1} = a_1$. For suppose the first repetition occurs at the $kth$ iterate of $f$ and

$$f^k(a_1) = f(a_k) = a_{k+1} ,$$

and $a_{k+1} = a_j$, where $j < k$. Then

$$f^k(a_1) = f^{j-1}(a_1),$$

and so $f^{k-j+1}(a_1) = a_1$, However, $k - j + 1 < k$ if $j \not= 1$, and we assumed that the first repetition occurred for $k$. Thus, $j = 1$ and so $f$ does cyclically permute the set $\{a_1, a_2, ..., a_k\}$. If $k < n$, then there exists $b_1 \in A$ such that. $b_1 \notin \{a_1, a_2,..., a_k\}$ and we may proceed similarly with $b_1$. We continue in this manner until all the elements of $A$ are accounted for. It is then seen that $f$ can be written in the form

$$f=(a_1,...,a_k)(b_1,...,b_\ell)(c_1,...,c_m)...(h_1,...,h_t).$$ (3.2)

Note that all powers $f^i(a_1)$ belong to the set $\{a_1=f^0(a_1)=f^k(a_1),a_2=f^1(a_1), ...,a_k=f^{k-1}(a_1)\}$, all powers $f^i(b_1)$ belong to the set $\{b_1=f^0(b_1)=f^\ell(b_1), b_2=f^1(b_1), ...,b_\ell=f^{\ell-1}(b_1)\}$, ... . Here, by definition, $b_1$ is the smallest element in $\{1,2,...,n\}$ which does not belong to $\{a_1=f^0(a_1)=f^k(a_1),a_2=f^1(a_1), ...,a_k=f^{k-1}(a_1)\}$, $c_1$ is the smallest element in $\{1,2,...,n\}$ which does not belong to

$$\{a_1=f^0(a_1)=f^k(a_1),a_2=f^1(a_1), ...,a_k=f^{k-1}(a_1)\}... ...^\ell(b_1), b_2=f^1(b_1), ...,b_\ell=f^{\ell-1}(b_1)\}, ...\ .$$

Therefore by construction, all the cycles in (3.2) are disjoint. From this it follows that $k+\ell +m+...+t=n$. It is clear that this factorization is unique except for the order of the factors since it tells explicitly what effect $f$ has on each element of $A$.

In summary we have proven the following result.

Theorem 3.1.2   Every permutation of $S_n$ can be written uniquely as a product of disjoint cycles.

Let us pause to consider some examples. It is readily seen that the elements of $S_3$ (see Example 2.1.15) can be written in cycle notation as $1 = (1), (1,2), (1,3), (2,3), (1,23,), (1,3,2)$. This is the largest symmetric group which consists entirely of cycles. In $S_4$, for example, the element $(1,2) (3,4)$ is not a cycle. Suppose we multiply two elements of $S_3$ say $( 1,2)$ and $(1,3)$. Now we recall from Example 2.1.15, that in forming the product or composite here, we read from right to left. Thus to compute $(1,2) (1,3)$: We note the permutation $(1,3)$ takes $1$ into $3$ and then the permutation $( 1,2)$ takes $3$ into $3$ so the composite $(1,2) (1,3)$ takes $1$ into $3$. Continuing the permutation $(1,3)$ takes $3$ into $1$ and then the permutation $( 1,2)$ takes $1$ into $2$, so the composite $(1,2) (1,3)$ takes $3$ into $2$. Finally $(1,3)$ takes $2$ into $2$ and then $( 1,2)$ takes $2$ into $1$ so $(1,2) (1,3)$ takes $2$ into $1$. Thus we see

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

The reader should note that $(1,2) = f_3$ and $(1,3) = f_2$ so $(1,2) (1,3) = f_3f_2 = r_2$ and $r_2 = (1,3,2)$ by the notation used in Example 2.1.15.

As another example of ``cycle multiplication,'' consider the product in $S_5$,

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

Reading from right to left $1\longmapsto 2\longmapsto 2 \longmapsto 4 \longmapsto 4$ so $1 \longmapsto 4$. Now $4 \longmapsto 4 \longmapsto 4 \longmapsto 5 \longmapsto 5$ so $4 \longmapsto 5$. Next $5 \longmapsto 1 \longmapsto 3 \longmapsto 3\longmapsto 3$ so $5 \longmapsto 3$. Then $3\longmapsto 3 \longmapsto 1 \longmapsto 1 \longmapsto 2$ so $3\longmapsto 2$. Finally $2 \longmapsto 5 \longmapsto 5 \longmapsto 2 \longmapsto 1$, so $2 \longmapsto 1$. Since all the elements of $A= \{1, 2, 3, 4, 5\}$ have been accounted for, we have

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