8.5 Symmetric Groups and Cycles

We have already met symmetric groups, but not with that name. A symmetric group is just the group of all permutations of a set. We’ll only really consider finite sets, although the definition makes sense for any set.

Definition 8.21:
  • Let X be a set. The symmetric group on X is the group S(X) of all permutations of X (i.e., bijective functions f:X\to X), with composition as the group operation.

  • The symmetric group S_n of degree n is the group of all permutations of the set \{1,2,\dots,n\} of n elements.

Let’s think of ways of describing permutations. Of course, we could just say what f(i) is for each value of i, and so, for example, refer to the element f of S_6 with f(1)=3, f(2)=6, f(3)=1, f(4)=4, f(5)=2 and f(6)=5.

This is quite hard to read, and one easy way to set out the information in a more easily readable form is to use a “double row” notation with 1,2,\dots,n along the top row, and f(1),f(2),\dots,f(n) along the bottom row.

For example, if f is the element of S_6 described above, then we could write f=\begin{pmatrix}1&2&3&4&5&6\\3&6&1&4&2&5\end{pmatrix}.

But there’s an even more compact method, that is also much more convenient for understanding group theoretic aspects of permutations.

Definition 8.22:

Let k and n be positive integers with k\leq n. A k-cycle f in S_n is a permutation of the following form. There are k distinct elements i_1,i_2,\dots,i_k\in\{1,2,\dots,n\} such that f(i_1)=i_2, f(i_2)=i_3, \dots, f(i_{k-1})=i_k,f(i_k)=i_1 and f(i)=i for i\not\in\{i_1,i_2,\dots,i_k\}. (So f “cycles” the elements i_1,i_2,\dots,i_k and leaves other elements unmoved.)

Such an f is denoted by f=(i_1,i_2,\dots,i_k).

We call k the length of this cycle.
Example:

In S_8, the 6-cycle g=(2,7,8,5,6,3) has g(2)=7,g(7)=8,g(8)=5,g(5)=6,g(6)=3,g(3)=2,g(1)=1\text{ and }g(4)=4, or, written in double row notation, \begin{pmatrix} 1&2&3&4&5&6&7&8\\1&7&2&4&6&3&8&5\end{pmatrix}. The notation (2,7,8,5,6,3) would also denote an element of S_9 with g(9)=9, so this notation doesn’t specify which symmetric group we’re looking at, although that is rarely a problem.

Note that the 6-cycle (7,8,5,6,3,2) is exactly the same permutation as g, so the same cycle can be written in different ways (in fact, a k-cycle can be written in k different ways, as we can choose to start the cycle with any of the k elements i_1,i_2,\dots,i_k).
Remark:
We’ll allow k=1, but every 1-cycle (i_1) is just the identity permutation, since it send i_1 to i_1 and every i\neq i_1 to i, so we’ll rarely bother to write down 1-cycles.
Definition 8.23:
A transposition is another name for a 2-cycle. So this is just a permutation that swaps two elements and leaves all other elements unmoved.
Etymology:

Transposition comes from the Latin trans meaning “across, beyond” and positus meaning “to put”. A transposition takes two elements and put them across each other, i.e. swap position.

Of course, not every permutation is a cycle. For example, the permutation f=\begin{pmatrix}1&2&3&4&5&6\\3&6&1&4&2&5\end{pmatrix} that we used as an example earlier is not. However, we can write it as a composition f=(1,3)(2,6,5) of two cycles. These two cycles are “disjoint” in the sense that they move disjoint set of elements \{1,3\} and \{2,5,6\}, and this means that it makes no difference which of the two cycles we apply first. So also f=(2,6,5)(1,3).

Definition 8.24:

A set of cycles in S_n is disjoint if no element of \{1,2,\dots,n\} is moved by more than one of the cycles.

Theorem 8.25:

Every element of S_n is may be written as a product of disjoint cycles.

Proof.

We give a constructive proof, that is we give a method which will write any f \in S_n as such a product.

We’ll write down a set of disjoint cycles by considering repeatedly applying f to elements of \{1,2,\dots,n\}, starting with the smallest elements.

So we start with 1, and consider f(1),f^2(1),\dots until we reach an element f^k(1) that we have already reached. The first time this happens must be with f^k(1)=1, since if f^k(1)=f^l(1) for 0<l<k then f^{k-1}(1)=f^{l-1}(1), and so we’d have repeated the element f^{l-1}(1) earlier. So we have a cycle (1,f(1),f^2(1),\dots,f^k(1)).

Now we start again with the smallest number i that is not involved in any of the cycles we’ve already written down, and get another cycle (i,f(i),\dots, f^s(i)) for some s.

We keep repeating until we’ve dealt with all the elements of \{1,2,\dots,n\}.

This will probably be clearer if we look at an example.

Example:

Consider the element f=\begin{pmatrix} 1&2&3&4&5&6&7&8&9\\ 2&5&1&9&7&6&3&4&8\end{pmatrix} of S_9 written in double row notation. To write this as a product of disjoint cycles, we start with 1, and calculate f(1)=2,f(2)=5,f(5)=7,f(7)=3,f(3)=1, so we have a 5-cycle (1,2,5,7,3).

The smallest number we haven’t yet dealt with is 4, and f(4)=9,f(9)=8,f(8)=4, so we have a 3-cycle (4,9,8).

The only number we haven’t dealt with is 6, and f(6)=6, so finally we have a 1-cycle (6).

So f=(1,2,5,7,3)(4,9,8)(6) as a product of disjoint cycles. Since 1-cycles are just the identity permutation, we can (and usually will) leave them out, and so we can write f=(1,2,5,7,3)(4,9,8).

Since the order in which we apply disjoint permutations doesn’t matter, we could write the cycles in a different order, or we could start each cycle at a different point. So, for example, f=(9,8,4)(5,7,3,1,2) is another way of writing the same permutation as a product of disjoint cycles.

It’s very easy to read off the product of permutations written in disjoint cycle notation, just by using the method in the proof of Theorem 8.25.

Example:

Let f=(1,5,3,4)(2,6,7) and g=(3,4,8,1,2,5) be elements of S_8 written in disjoint cycle notation. Let’s calculate fg and gf. fg=(1,5,3,4)(2,6,7)(3,4,8,1,2,5), but of course these are not disjoint cycles. So we start with 1 and calculate where it is sent by performing the permutation fg repeatedly:

  • 1 is sent to 2 by (3,4,8,1,2,5), which is sent to 6 by (2,6,7), which is not moved by (1,5,3,4). So fg(1)=6.
  • 6 is not moved by (3,4,8,1,2,5). It is sent to 7 by (2,6,7), which is not moved by (1,5,3,4). So fg(6)=7.
  • 7 is not moved by (3,4,8,1,2,5). It is sent to 2 by (2,6,7), which is not moved by (1,5,3,4). So fg(7)=2.
  • 2 is sent to 5 by (3,4,8,1,2,5), which is not moved by (2,6,7) and is sent to 3 by (1,5,3,4). So fg(2)=3.
  • 3 is sent to 4 by (3,4,8,1,2,5), which is not moved by (2,6,7), and sent to 1 by (1,5,3,4). So fg(3)=1.
  • So we’ve completed our first cycle (1,6,7,2,3).
  • 4 is sent to 8 by (3,4,8,1,2,5), which is not moved by (2,6,7) or (1,5,3,4). So fg(4)=8.
  • 8 is sent to 1 by (3,4,8,1,2,5), which is not moved by (2,6,7) and sent to 5 by (1,5,3,4). So fg(8)=5.
  • 5 is sent to 3 by (3,4,8,1,2,5), which is not moved by (2,6,7) and sent to 4 by (1,5,3,4). So fg(5)=4.
  • So we’ve completed another cycle (4,8,5).
  • We’ve now dealt with all the numbers from 1 to 8, so fg=(1,6,7,2,3)(4,8,5) as a product of disjoint cycles.
Similarly, gf=(3,4,8,1,2,5)(1,5,3,4)(2,6,7)=(1,3,8)(2,6,7,5,4) as a product of disjoint cycles.
Example:
It is easy to write down the inverse of a permutation written as a product of disjoint cycles. Just write the permutation backwards. For example, if f=(1,4,3,5,7)(2,6,8) then f^{-1}=(8,6,2)(7,5,3,4,1). Of course, we have a choice of which order to take the cycles, and where to start each cycle, and if we carried out the method in the proof of Theorem 8.25 then we’d get the alternative representation f^{-1}=(1,7,5,3,4)(2,8,6).
History:

Symmetric groups were one of the first type of groups to emerge as mathematicians studied the permutation of roots of equations in the 1770s. This was before the formal abstract definition of a group was introduced - around 100 years later in the 1870s.