We also saw that the set of symmetries \(\text{Sym}(S)\) of a shape \(S\), such as the equilateral triangle below, with composition form a group. We will return to symmetry groups later in this lesson.
Today we are going to learn about symmetric groups, and the relationship between symmetry groups and symmetric groups! But before we jump in, let’s do a quick recap of last weeks lesson. Recall that a group is a set \(G\), together with a binary operation \(\bullet\), such that the following group axioms hold:
(Associativity) For every \(a,b,c\in G\), \((a\bullet b)\bullet c = a\bullet (b\bullet c)\).
(Identity element) There exists \(\text{id}_G\in G\) such that for all \(a\in G\), \(\text{id}_G\bullet a = a = a \bullet\text{id}_G\).
(Inverse element) For every \(a\in G\), there exists \(a^{-1}\in G\) such that \(a\bullet a^{-1} = \text{id}_G = a^{-1}\bullet a\).
We write \((G,\bullet)\) to represent the group \(G\) with binary operation \(\bullet\).
As an example, we saw that the integers \[\mathbb{Z}=\{\dots,-3,-2,-1,0,1,2,3,\dots\}\] with addition form a group. In other words, \((\mathbb{Z},+)\) is a group.
We also saw that the set of symmetries \(\text{Sym}(S)\) of a shape \(S\), such as the equilateral triangle below, with composition form a group. We will return to symmetry groups later in this lesson.
Today we are going to focus on a special class of groups called symmetric groups. Like most classes of groups, symmetric groups appear all over mathematics. They are in particular important to the area of combinatorics! At the end of the lesson, we will see how the theory of symmetric groups can be used to solve a problem that has to do with "switching minds"! Recall again that a group is a set together with a binary operation. To get started, we first learn about this underlying set.
The underlying set of a symmetric group is a certain collection of objects called permutations. You likely come across permutations in your every day life! For example, consider a full deck of cards:
Source: Wikimedia Commons. English pattern playing cards deck [Online]. Available from: https://commons.wikimedia.org/wiki [Accessed March 24 2023].
A standard deck of cards contains 52 distinct cards. We consider cards with the same number to be distinct because they have different suits. Similarly, cards with the same suit are considered distinct because they have different numbers. Any shuffling of this deck of cards is an example of a permutation. So, in this example, we are looking at permutations of cards. In card games, the ordering of the cards in the deck matters and can affect the outcome of the game!
There are two key things to note in this example:
Cards are being shuffled in various arrangements, and
The order of cards matters.
Together, these two key points describe what a permutation is!
If \(X\) is a set with a finite number of elements, meaning that \(X\) has \(n\) elements for some \(n\in\mathbb{N}\), then we call \(X\) a finite set.
Note: The definition of set requires that all elements of a set are distinct. In other words, we don’t allow duplicate objects to appear in a set. So, if \(X\) has \(n\) elements, this means that there are \(n\) distinct elements in \(X\).
If \(X\) is a finite set, then roughly put, a permutation of \(X\) is an arrangement of its elements into some order.
Let \(X\) be a finite set. A
permutation of \(X\)
is an arrangement of the elements of \(X\) into some order such that every element
of \(X\) appears in the arrangement
exactly once.
The verb we use to describe the action of arranging the elements is
permute. In present tense, we say that "we are
permuting the elements of \(X\)".
Let \(X=\{a,b,c\}\). This is a finite set since there are 3 elements in it. Below are all possible permutations of \(X\): \[(a,b,c) \quad (a,c,b) \quad (b,a,c) \quad (b,c,a)\quad (c,a,b) \quad (c,b,a).\]
Note that the definition of permutation requires that every element of \(X\) appears exactly once. We see that the arrangements in Example 1 satisfy this. Now, for instance, \((a,b)\) is not a permutation of \(X=\{a,b,c\}\) since \(c\) does not appear. Also, \((a,b,b,c)\) is not a permutation of \(X=\{a,b,c\}\) since \(b\) appears more than once.
For another example, consider \(X=\{1,2,3\}\). Below are all possible permutations of \(X\): \[(1,2,3) \quad (1,3,2) \quad (2,1,3) \quad (2,3,1) \quad (3,1,2) \quad (3,2,1).\]
Let \(X=\{1,2,3,4\}\). List all of the permutations of \(X\).
Do you see a connection between the permutations in Example 1 and Example 2?
You may have noticed that the permutations in Example 1 and Example 2 are basically the same. More precisely, if we label \(a\) with the number \(1\), \(b\) with the number \(2\), and \(c\) with the number \(3\), then the permutations of \(\{a,b,c\}\) are exactly the same as the permutations of \(\{1,2,3\}\). In fact, this phenomenon is true in general! The permutations of a given set do not depend on what the elements look like, it only matters how many elements are in the set.
Let \(X\) be a finite set with \(n\in\mathbb{N}\) elements. Going forward, we may assume that \(n\geq 1\) because if \(n=0\), then \(X\) is the set containing no elements (i.e., the empty set) and so there are no elements to permute. Recall that the elements of a set are always distinct, meaning that there are no repeating elements. Since \(X\) has \(n\) distinct elements, we can write \[X=\{x_1,\dots,x_n\},\] where \(x_1,x_2,\dots,x_n\) are considered to be all distinct from each other. In other words, we label each element of \(X\) with the symbol \(x_i\) for some \(1\leq i\leq n\). For example, we can label the elements of \(\{a,b,c\}\) as \(x_1=a,x_2=b\), and \(x_3=c\).
Notice that the permutations of \(X\) are the same as the permutations of \(\{1,\dots,n\}\). Why? Well, if we permute the elements \(x_i\) of \(X\) around, it’s the same as permuting the indices \(i\) of the \(x_i\) around. So, really, we are just permuting elements of the set \(\{1,\dots,n\}\). Because of this, we can assume that our sets take the form \(\{1,\dots,n\}\) for some \(n\in\mathbb{N}\). This phenomenon tells us that finite sets with the same number of elements have the same permutations. So, we can make the following definition.
Let \(X\) be a finite set with \(n\) elements. The set of permutations of \(\boldsymbol{X}\) is denoted by \(S_n\).
Given a finite set \(X\) with \(n\in\mathbb{N}\) elements, we can form the set \(S_n\). The set \(S_n\) together with a certain binary operation forms a group. This group is called the symmetric group on \(X\), or the symmetric group on \(\{1,\dots,n\}\). Let’s learn about this binary operation on \(S_n\).
For each \(n\in\mathbb{N}\), consider the set \(S_n\). We want to find a binary operation on \(S_n\). In other words, we want to find a way to combine two permutations of \(\{1,\dots,n\}\) into another permutation of \(\{1,\dots,n\}\). To do this, we introduce some new notation called two-line notation. It’s a bit tricky to define this new notation without introducing more symbols, so we are going to explain the new notation using examples.
Let \(X=\{1,2,3\}\) and consider the permutation \(\sigma=(2,3,1)\). The permutation \(\sigma\) shuffles the natural ordering \(1,2,3\) into \(2,3,1\). We can think of this as \(1\) being replaced by \(2\), \(2\) being replaced by \(3\), and \(3\) being replaced by \(1\). We can illustrate this information using the following diagram:
In fact, we can think of \(\sigma\) as an operation that takes in \(1\) and outputs \(2\), takes in \(2\) and outputs \(3\), and takes in 3 and outputs 1. In words, it is common to say "1 goes to 2, 2 goes to 3, and 3 goes to 1". By ignoring the arrows in the above diagram, we can represent \(\sigma\) using the following two-line notation: \[\sigma=\begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix}.\] The top row is the inputs, the elements of the set \(X\). The bottom row is the outputs, the values each number is mapped to.
Let \(X=\{1,2,3,4\}\) and consider the permutation \(\sigma=(1,3,4,2)\). In our new notation, we write \[\sigma= \begin{pmatrix} 1 & 2 & 3 & 4\\ 1 & 3 & 4 & 2 \end{pmatrix}.\]
Given permutations \(\sigma,\beta\in S_n\), we can combine them to make a new permutation \(\sigma\circ\beta\) in \(S_n\). The permutation \(\sigma\circ\beta\) is read as the composition of \(\sigma\) with \(\beta\). In general, note that the permutation \(\sigma\circ\beta\) is not necessarily equal to the permutation \(\beta\circ\sigma\).
Composition is a binary operation on \(S_n\).
Defining the binary operation composition on \(S_n\) requires a lot of extra notation, so we will learn how it works through examples.
Let \(X=\{1,2,3\}\) and consider the following two permutations in \(S_3\) \[\sigma= \begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix} \quad \beta=\begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2 \end{pmatrix}.\] The composition \(\sigma\circ\beta\) is given as follows: \[\sigma\circ\beta= \begin{pmatrix} 1 & 2 & 3\\ 2 & 1 & 3 \end{pmatrix}.\] Let’s explain how we got this. Looking at \(\beta\), we see that \(1\) goes to \(1\). We then look at \(\sigma\) to see where \(1\) goes. In \(\sigma\) see that \(1\) goes to \(2\). So the result is that \(1\) goes to \(2\). This is where the first column of \(\sigma\circ\beta\) comes from. Next, looking at \(\beta\) we see that \(2\) goes to \(3\). Then looking at \(\sigma\) we see that \(3\) goes to \(1\). So the result is that \(2\) goes to \(1\). This is where the second column of \(\sigma\circ\beta\) comes from. Lastly, looking at \(\beta\) we see that 3 goes to 2. Then looking at \(\sigma\) we see that 2 goes to 3. So the result is that 3 goes to 3. This is where the third column of \(\sigma\circ\beta\) comes from. We can think of \(\sigma\circ\beta\) as first shuffling \(1,2,3\) into \(1,3,2\) and then shuffling \(1,3,2\) according to \(\sigma\).
Let \(X=\{1,2,3,4\}\) and consider the following two permutations of \(S_4\) \[\sigma = \begin{pmatrix} 1 & 2 & 3 & 4\\ 2 & 3 & 1 & 4 \end{pmatrix} \quad \beta=\begin{pmatrix} 1 & 2 & 3 & 4\\ 4 & 3 & 2 & 1 \end{pmatrix}.\] Then \[\sigma\circ\beta=\begin{pmatrix} 1 & 2 & 3 & 4\\ 4 & 1 & 3 & 2 \end{pmatrix} \quad\text{and}\quad \beta\circ\sigma =\begin{pmatrix} 1 & 2 & 3 & 4\\ 3 & 2 & 4 & 1 \end{pmatrix}.\] This example illustrates that \(\sigma\circ\beta\neq \beta\circ\sigma\). Here, the symbol \(\neq\) means "not equal".
Let \(X=\{1,2,3,4,5\}\) and consider the following two permutations of \(S_5\) \[\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 1 & 2 & 3 & 4 \end{pmatrix}\quad \beta= \begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 1 & 4 & 3 & 5 \end{pmatrix}.\] Compute the compositions \(\sigma\circ\beta\) and \(\beta\circ\sigma\).
Convince yourself that \((S_3,\circ)\) is a group.
\(\boldsymbol{\ast \ast}\) See solutions to Exercise 3 before reading on \(\boldsymbol{\ast \ast}\)
The explanation in Exercise 3 can be generalized to show that \((S_n,\circ)\) is a group for any \(n\in\mathbb{N}\). So, in general, \(S_n\) with composition forms a group! Let’s sketch how this works. To do this, we need to convince ourselves that the group axioms hold for \(S_n\) with composition \(\circ\). So, let \(\sigma,\beta,\alpha \in S_n\).
Axiom 1: For associativity to hold, we need \((\sigma\circ\beta)\circ\alpha\) to be the same permutation as \(\sigma\circ(\beta\circ\alpha)\). Similar to symmetry groups, this axiom is a bit tough to argue given our current mathematical tools. As mentioned in Example 5, we can view permutations as operations, or more formally as functions. If you know a bit about functions, then by viewing each permutations as a function, it isn’t too hard to show that \[(\sigma\circ\beta)\circ\alpha = \sigma\circ\beta\circ\alpha= \sigma\circ(\beta\circ\alpha).\] If you were able to convince yourself that associativity holds in Exercise 3, that is plenty good enough!
Axiom 2: Not shuffling \(1,2,\dots,n\) out of it’s natural ordering is a valid permutation of \(\{1,\dots,n\}\). In other words, \[\begin{pmatrix} 1 & 2 & \cdots & n\\ 1 & 2 & \cdots & n \end{pmatrix}\] is a permutation in \(S_n\). This is the identity element in \(S_n\) because if you compose this permutation with \(\sigma\) you get \(\sigma\) back. We write \[\text{id}_{S_n} = \begin{pmatrix} 1 & 2 & \cdots & n\\ 1 & 2 & \cdots & n \end{pmatrix}.\]
Axiom 3: Lastly, given a permutation \(\sigma\) in \(S_n\) we can construct it’s inverse \(\sigma^{-1}\) as follows. Write \(\sigma\) using the two-line notation. The inverse \(\sigma^{-1}\) of \(\sigma\) is obtained by switching the rows of \(\sigma\) and then reordering the columns so that the top row is in the order \(1,\dots, n\).
We call the group \((S_n,\circ)\) the symmetric group on \(\{1,\dots,n\}\).
We are going to first compare the symmetry group of the equilateral triangle with the symmetric group on \(\{1,2,3\}\). Last time we saw that the symmetries of the equilateral triangle are
counter-clockwise rotations by multiples of 120 degrees, and
reflections in the 3 axes that pass through the center and a tip of the triangle.
If we label the tips of the triangle with the numbers \(1\), \(2\), \(3\) then we can view the symmetries of the triangle as certain permutations of \(\{1,2,3\}\). It doesn’t matter how we label the triangle, but we will use the labelling below for this lesson:
Just as a permutation in \(S_3\) shuffles the natural ordering \(1,2,3\), a symmetry of the triangle shuffles the positions of the numbers on the triangle above. Let’s see how symmetries of the triangle can be identified with permutations in \(S_3\). First consider the symmetry which is counter-clockwise rotation by \(120\) degrees:
We see that this symmetry moves \(1\) from the top tip of the triangle to the left tip, \(2\) from the left tip to the right tip, and \(3\) from the right tip to the top tip. Alternatively, we can think of this as \(1\) moving to where \(2\) was, \(2\) moving to where \(3\) was, and \(3\) moving to where \(1\) was. In words, we can say "\(1\) goes to \(2\), \(2\) goes to \(3\), and \(3\) goes to \(1\)" (sound familiar? See Example 3). Given this, this symmetry corresponds to the permutation \[\begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix}.\] Next, consider counter-clockwise rotation by \(240\) degrees:
Similar to above, this symmetry sends \(1\) to \(3\), \(2\) to \(1\), and \(3\) to \(2\). In words, we can say \(1\) goes to \(3\), \(2\) goes to \(1\), and \(3\) goes \(2\). Given this, this symmetry corresponds to the the permutation \[\begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2 \end{pmatrix}.\] The last rotation symmetry of the triangle is counter-clockwise rotation by \(360\) degrees, or equivalently, the identity symmetry which "does nothing":
This symmetry does nothing, and so the positions of the numbers on the triangle do not change. Here, we say \(1\) goes to \(1\), \(2\) goes to \(2\), and \(3\) goes to \(3\). To no surprise, the identity symmetry of the triangle corresponds to the identity permutation \[\begin{pmatrix} 1 & 2 & 3\\ 1 & 2 & 3 \end{pmatrix}.\] Next, consider the symmetry that reflects in the yellow axis drawn below:
This symmetry fixes \(1\) in the top position, but interchanges \(2\) and \(3\). So, we can say \(1\) goes to \(1\), \(2\) goes to \(3\), and \(3\) goes to \(2\). This symmetry corresponds to the permutation \[\begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2 \end{pmatrix}.\] The permutations corresponding to the last two symmetries shown below are \[ \begin{pmatrix} 1 & 2 & 3\\ 3 & 2 & 1 \end{pmatrix}\quad\text{ and }\quad \begin{pmatrix} 1 & 2 & 3\\ 2 & 1 & 3 \end{pmatrix}, \] respectively.