What are the symmetries of the configuration of three objects above? There are 6 possible ways to place the objects. The symmetries of a configuration of identical objects are called permutations.

To represent a permutation, we’ll use the following notation. The first row refers to the positions of these objects in the configuration. The second row represents the final configuration of the objects after permuting them.

$$ \begin{align*} \rho = \begin{pmatrix}1 & 2 & 3 \\ 3 & 2 & 1\end{pmatrix} \end{align*} $$

So in the above, the objects in positions 1 and 3 will be switched while the object in position 2 will stay in place.

$$ \begin{align*} \rho = \begin{pmatrix}1 & 2 & 3 \\ 2 & 3 & 1\end{pmatrix} \end{align*} $$

In the above, the object in position 1 will move to position 2. The object in position 2 will move to position 3 and the object in position 3 will move to position 1.


Permutations and Symmetries

The set of permutations of \(n\) identical objects and the set of symmetries of a geometric figure share the following properties

  • The multiplication of permutations is associative.
  • There is an identity element.
  • For each permutation \(\sigma\), there is an inverse permutation \(\sigma^{-1}\).

We know that maps from a set to itself can be composed and the composition is associative. Furthermore, if \(f\) and \(g\) are bijective, then \(f \circ g\) is also bijective. Now, consider the maps from a set \(X\) to itself. Let \(\text{Sym}(X)\) be the set of all bijective maps from the set \(X\) to itself. This set satisfies

  • composition of these maps is associative.
  • There is an identity map \(id_X\) such that the composition of this map with any \(f \in \text{Sym}(X)\).
  • The inverse of any map \(f \in \text{Sym}(X)\) is \(f^{-1}\) and the composition of these two maps is \(id_X\).

We can see now that a permutation of \(n\) objects can really be represented with a bijective function on the set \(\{1,...,n\}\). The multiplication of permutations is really the same as the composition of these bijective maps. Instead of writing \(\text{Sym}(X)\), we write \(S_n\) where \(n\) is the number of elements in the set.


Cycle Notation

Additionally, instead of writing the whole two rows like we did earlier, we typically write these permutations or maps in an alternative form. Instead of writing

$$ \begin{align*} \rho = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 3 & 1 & 2 & 6 & 5 & 7\end{pmatrix} \end{align*} $$

we write

$$ \begin{align*} \rho = \begin{pmatrix}1 & 4 & 2 & 3\end{pmatrix}\begin{pmatrix}5 & 6\end{pmatrix} \end{align*} $$

This form takes 1 to 4, 4 to 2, 2 to 3 and 3 to 1. It also takes 5 to 6 and 6 to 5. A permutation that permutes several numbers cyclically is called a cycle. And two cycles are disjoint if each will leave the numbers moved by the other cycle fixed. An example is the above permutation which has two disjoint cycles. With this representation though, all of the following permutations are equal

$$ \begin{align*} \begin{pmatrix}1 & 4 & 2 & 3\end{pmatrix} = \begin{pmatrix}4 & 2 & 3 & 1\end{pmatrix} = \begin{pmatrix}2 & 3 & 1 & 4\end{pmatrix} = \begin{pmatrix}3 & 1 & 4 & 2\end{pmatrix} \end{align*} $$



Multiplication with Cycle Notation

Suppose we want to compose or multiply the following permutations

$$ \begin{align*} f = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{pmatrix} \end{align*} $$

and

$$ \begin{align*} g = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 5 & 2 & 4 \end{pmatrix} \end{align*} $$

With the non-cycle notation, we can easily see that \(g(1) = 3\) and \(f(3) = 4\) so this means that 1 gets mapped to 4. Similarly, \(g(2) = 1\) and \(f(1) = 3\) so 2 gets mapped to 3. Furthermore, \(f(g(3)) = f(5) = 2\). \(f(g(4)) = f(2) = 5\). So we see that

$$ \begin{align*} f \circ g = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 5 & 1 \end{pmatrix} \end{align*} $$

In cycle notation, we know that we can write \(f\) and \(g\) as follows

$$ \begin{align*} f &= \begin{pmatrix} 1 & 3 & 4 \end{pmatrix} \begin{pmatrix} 2 & 5 \end{pmatrix} \\ g &= \begin{pmatrix} 1 & 3 & 5 & 4 & 2 \end{pmatrix} \end{align*} $$

Suppose we want compose \(f\) and \(g\) in cycle notation. We’ll take one element at a time and see where it goes so

  • From \(g\) above we see that 1 goes to 3 and from \(f\), we see that 3 goes to 4. Therefore, \(f(g(1)) = 4\)
  • Similarly using the cycle notation we see that 2 goes to 1 above with \(g\) and \(f\) takes 1 to 3. Therefore, \(f(g(2)) = 3\)
  • Following the same pattern, \(f(g(3))=f(4)=2\). \(f(g(4)) = f(2) = 5\) and finally, \(f(g(5)) = f(4) = 1\)

Writing the result in cycle notation, we can start with any element to start building a cycle. If we start with 1, then we see that 1 gets mapped to 4. 4 gets mapped to 5. 5 gets mapped to 1. So that’s a cycle. For the second cycle, if we start with 2, then 2 gets mapped 3 and then 3 gets mapped to 2. So that’s the second cycle or a transposition. Therefore we can write the following

$$ \begin{align*} f \circ g = \begin{pmatrix}1 & 4 & 5\end{pmatrix}\begin{pmatrix}2 & 3\end{pmatrix} \end{align*} $$




References