3.15 Cycle Decomposition in the Symmetric Group

In this section, \(n\) is a positive integer and \([n] = \{ 1,\ldots , n\} \). The symmetric group \(S_n\) is the group \(A([n])\) of permutation of \(n\). Elements of \(S_n\) are called permutations. We write \(e\) for the identity element of \(S_n\).

Definition 3.112

Suppose \(\sigma \in S_n\). Let \(\rho _{\sigma }:\mathbb {Z}\to S_n\) by the map \(\sigma \mapsto \sigma ^n\). This gives action of \(\mathbb {Z}\) on \([n]\), and, thus, a partition of \([n]\) into orbits. We call these orbits the orbits of \(\sigma \), and we write \(\operatorname{\mathrm{Orb}}_{\sigma } j\) for \(\operatorname{\mathrm{Orb}}_{\mathbb {Z}}(j)\), where \(\mathbb {Z}\) is acting on \([n]\) via \(\rho _{\sigma }\). So \(\operatorname{\mathrm{Orb}}_{\sigma }(j) = \{ \sigma ^k(j) : k\in \mathbb {Z}\} \).

We call an orbit trivial if has one element. Otherwise, we call the orbit nontrivial. We call \(\sigma \) a cycle if it has at most one nontrivial orbit.

Note that the identity element \(e\in S_n\) is, by this definition, a cycle. It is the only cycle which has all orbits trivial.

Definition 3.113

Suppose \(\sigma \in S_n\) is a cycle. The length of \(\sigma \) is maximum cardinality of an orbit of \(\sigma \).

So the length of a cycle \(\sigma \) is \(1\) of \(\sigma = e\), and the cardinality of the unique nontrivial orbit otherwise.

Proposition 3.114

Suppose \(i_1,i_2,\ldots , i_k\) are distinct elements of \([n]\). Write \(\sigma = (i_1 i_2 \ldots i_k)\) for the map from \([n]\) to itself given by

\begin{equation} \label{e-cycdef} \sigma (j) = \begin{cases} i_{\ell + 1},& j \in \{ i_1,\ldots , i_{k-1}\} ;\\ i_{1},& j = i_k;\\ j,& \text{otherwise.} \end{cases} \end{equation}

3.115

Then \(\sigma \) is a cycle of length \(k\). Moreover, every cycle \(\sigma \) of length \(k\) is of the above form with \(\{ i_1,\ldots , i_k\} \) the orbit of \(\sigma \) containing \(i_1\), and we have \(|\sigma | = k\).

Sketch ▼

I’ll leave it as an exercise to check that \(\sigma \) is permutation. (By the pidgeonhole principle, you just have to check either that \(\sigma \) is one-one or that \(\sigma \) is onto.) Then, for any \(j\in \{ i_1,\ldots , i_k\} \), the orbit of \(\sigma \) containing \(j\) is the set \(\{ i_1,\ldots , i_k\} \). On the other hand, for \(j\not\in \{ i_1,\ldots , k_k\} \), the orbit of \(\sigma \) containing \(j\) is just \(\{ j\} \). So \(\sigma \) is a cycle of length \(k\).

To prove the last two statements, suppose \(\sigma \) is a cycle of length \(k\). If \(k=1\), then \(\sigma = e = (j)\) for any \(j\in [n]\). So \(|\sigma | = |e| = 1 = k\). If \(k {\gt} 1\), then let \(i_1\) be an element of the orbit of \(\sigma \) of length \(k\). Then, by the orbit-stabilizer theorem, \(\operatorname{\mathrm{Stab}}_{\mathbb {Z}} i_1 = k\mathbb {Z}\). So the elements \(i_1, i_2 = \sigma (i_1),\ldots , i_k = \sigma ^{k-1}(i_1)\) are all distinct, while \(\sigma ^k(i_1) = i_1\). Thus the orbit of \(\sigma \) containing \(i_1\) is \(\{ i_1,\ldots , i_k\} \) and \(\sigma (j) = j\) for \(j\not\in \{ i_1,\ldots , i_k\} \). From this, we see that \(\sigma ^k = e\) but \(\sigma ^j \neq e\) for \(1\leq j {\lt} k\). So \(|\sigma | = k\).

Note that, in the representation of a cycle \(\sigma \) as \(\sigma = (i_1 \ldots i_k)\), the integer \(k\) is unique, but the ordered \(k\)-tuple \((i_1\ldots i_k)\) is not. For one things, if \(k =1\), then \(\sigma = e\), then \(\sigma = (j)\) for any \(j\in [n]\). If \(k=1\), then the set \(\{ i_1\ldots , i_k\} \) is uniquely determined by \(\sigma \) as the unique nontrivial orbit of \(\sigma \) acting on \([n]\). However, we can cyclicly permute the integers \(i_1,\ldots , i_k\) and get the same cycle. That is, for example, \((i_1\ldots i_k) = (i_2\ldots i_k i_1)\).

Lemma 3.119

Supose \(\sigma \in S_n\) is a permutation and \(T = \operatorname{\mathrm{Orb}}_{\sigma }(i_1)\) is a \(\sigma \)-orbit. Define a map \(\sigma _T:[n]\to [n]\) by

\[ \sigma _T (j) = \begin{cases} \sigma (j), & j\in T;\\ j, & \text{otherwise.} \end{cases} \]

Then \(\sigma _T = (i_1 i_2 \ldots i_k)\) where \(k = |T|\) and \(i_j = \sigma ^{j-1} i_1\) for \(1 {\lt} j \leq k\). In particular, \(\sigma _T\) is a cycle.

Proof ▼

The stablizer \(\operatorname{\mathrm{Stab}}_{\mathbb {Z}} i_1\) is \(k\mathbb {Z}\) by the orbit-stabilizer theorem. So \(\sigma _T(j) = (i_1 i_2 \ldots i_k)\) for \(j\in T\). But then for \(j\not\in T\) they agree as well.

Definition 3.122

Suppose \(\sigma \in S_n\). We set \(\operatorname{\mathrm{Fix}}\sigma = \{ i\in [n]: \sigma (i) = i\} \) and \(\operatorname{\mathrm{Mov}}\sigma = [n] \setminus \operatorname{\mathrm{Fix}}\sigma \). We say two permutations \(\sigma , \tau \in S_n\) are disjoint if \(\operatorname{\mathrm{Mov}}\sigma \cap \operatorname{\mathrm{Mov}}\tau = \emptyset \).

Lemma 3.123

Suppose \(\sigma = (i_1\ldots i_a)\) is a cycle. If \(a = 1\), then \(\operatorname{\mathrm{Fix}}\sigma = [n]\). So \(\operatorname{\mathrm{Mov}}\sigma =\emptyset \). Otherwise, \(\operatorname{\mathrm{Mov}}\sigma = \{ i_1,\ldots i_a\} \). So \(\operatorname{\mathrm{Fix}}\sigma = [n] \setminus \{ i_1,\ldots i_a\} \).

Proof ▼

The case \(a = 1\) is clear because, in that case \(\sigma = e\). The case \(a {\gt} 1\) is also clear from the definition.

Lemma 3.124

Suppose \(\sigma = (i_1\ldots i_a)\) and \(\tau = (j_1\ldots j_b)\) are disjoint cycles. Then \(\sigma \tau = \tau \sigma \).

Proof ▼

If \(a\) or \(b\) is \(1\) then it is obvious as \(\sigma \) or \(\tau \) is trivial. So assume \(a, b {\gt}1\). Then multiply it out using the fact that \(\{ i_1,\ldots , i_a\} \cap \{ j_1,\ldots , j_b\} = \emptyset \).

Theorem 3.125

Let \(\sigma \in S_n\) and let \(T_1,\ldots , T_k\) be the orbits of \(\sigma \) on \([n]\). Then \(\sigma = \sigma _{T_1} \cdots \sigma _{T_k}\). In particular, \(\sigma \) is a product of disjoint cycles.

Proof ▼

Suppose \(j\in [n]\). The cycles \(\sigma _{T_i}\) are disjoint. So they commmute. So we can rearrange them and assume \(j\in T_1\). Then \(\sigma _{T_2}\cdots \sigma _{T_k} (j) = j\). So \(\sigma _{T_1}\cdots \sigma _{T_k} (j) = \sigma _{T_1}(j) = \sigma (j)\).

Definition 3.126

A partition of \(n\) is a nonincreasing sequence \(\{ \lambda _i\} _{i=1}^k\) of positive integers \(\lambda _1\geq \lambda _2\geq \lambda _3\geq \cdots \lambda _k\) such that \(\sum \lambda _i = n\).

Suppose \(\sigma \in S_n\) and write \(T_1,\ldots , T_k\) for the orbits of \(\sigma \) acting on \(n\). We can do this in such a way that, setting \(\lambda _i = |T_i|\), we get a partition of \(n\). This partition \(\lambda = \lambda (\sigma )\) is then uniquely determined by \(\sigma \) and is called the type of \(\sigma \).

Theorem 3.127

Two permutation have the same type if and only if they are conjugate in \(S_n\).

Proof ▼

Suppose \(\sigma \in S_n\) has type \(\lambda = \lambda (\sigma )\). Then we can write

\[ \sigma = (i_1\cdots i_{\lambda _1})(i_{\lambda _1+1}\cdots i_{\lambda _1+\lambda _2}) \cdots (i_{n-\lambda _k+1}\cdots i_{n}) \]

as a product of disjoint cycles. Let \(\tau \) be the permutation

\[ \tau = \begin{pmatrix} 1 & 2 & \cdots n \\ i_1 & i_2 & \cdots n \end{pmatrix}. \]

Then

\[ \tau ^{-1}\sigma \tau = (1\cdots \lambda _1)(\lambda _1+1\cdots \lambda _1+\lambda _2) \cdots (n-\lambda _k+1 \cdots n), \]

which depends only on \(\lambda \). This shows that two permutations with the same type are conjugate.

The converse is left as an exercise. (The idea is that the conjugate of a cycle is still a cycle and conjugating disjoint cycles by the same permutation keeps them disjoint.)