Permutation groups

Now that we know the definition of a group, the question arises: how might they be described? The simplest answer is that we describe a group much as we might describe a set: we could list all its elements and give the multiplication table or we could describe all its elements and their multiplication in terms of some property from which we can verify the four properties of group. Though the first way has the distinct advantage of being explicit, it is this second alternative which is the most common since it is usually more concise.

Our objective is to introduce terminology and techniques which enable us to analyse mathematically permutation puzzles. The type of groups which arise in this context are defined next.

Definition 5.8.1   Let $X$ be a finite set. Let $g_1, g_2, ..., g_n$ be a finite set of elements of permutations of $X$ (so that they all belong to $S_X$ ). Let $G$ be the set of all possible products of the form

$$g = x_1*x_2...*x_m, m>0,$$

where each of the $x_1, ..., x_m$ is taken from the set $\{g_1, ..., g_n\}$ . The set $G$ , together with the group operation given by composition of permutations, is called a permutation group with generators $g_1, ..., g_n$ . We sometimes write

$$G = \langle g_1, ..., g_n\rangle \subset S_X.$$

Example 5.8.2   Let $X$ be the set of 54 facets of the Rubik's cube and let $R,L,U,D,F,B\in S_X$ denote the basic moves of the Rubik's cube, in the notation introduced in the previous chapter. The permutation group $G=\langle R,L,U,D,F,B\rangle \subset S_X$ is called the Rubik's cube group. We shall determine the ``structure'' (i.e., its relationship with ``known groups'') of this group later in this book.

.

It is not too hard to justify our terminology:

Lemma 5.8.3   A permutation group is a group.

proof: Let $G$ be a permutation group as in the above definition.

We shall only prove that each $g\in G$ has an inverse, leaving the remainder of the properties for the reader to verify. The set $\{g^n \vert n\geq 1\}\subset S_X$ is finite. There are $n_1>0$ , $n_2>n_1$ such that $g^{n_1}=g^{n_2}$ . Then $g^{-1}=g^{n_2-n_1-1}$ since $g\cdot g^{n_2-n_1-1}=1$ . $\Box$

Remark 5.8.4   The above definition can be generalized: Replace $S_X$ by any group $S$ which includes all the generators $g_1, ..., g_n$ . The resulting set $G$ is called the group generated by the elements $g_1, ..., g_n$ .

Algorithm:

Input: The generators $g_1, ..., g_n$ (as permutations in $S_X$ ),

Output: The elements of $G$ ,

$S = \{g_1, ..., g_n, g_1^{-1}, ..., g_n^{-1}\}$ ,

$L = S \cup \{1\}$ ,

      
     for g in S do
       for h in L do
        if g*h not in L then L = L union {g*h} endif
       endfor
     endfor

Note that the size of the list L in the for loop changes after each iteration of the loop. The meaning of this is that the if-then command is to be executed exactly once for each element of the list.

Definition 5.8.5   If $G$ is a group then the order of $G$ , denoted $\vert G\vert$ , is the number of elements of $G$ , if $G$ is a finite set, and $\vert G\vert=\infty$ , otherwise. If $g$ is an element of the group $G$ then the order of $g$ , denoted $ord(g)$ , is the smallest positive integer $m$ such that $g^m=1$ , if it exists. If such an integer m does not exist then we say that $g$ has infinite order.

Example 5.8.6   For example, there is an even permutation of order $42$ in $S_{12}$ , for example $(1,2)(3,4,5)(6,7,8,9,10,11,12)$ , and an odd permutation of order $15$ in $S_8$ , for example $(1,2,3)(4,5,6,7,8)$ .

We shall be able to make use of the following fact frequently.

Theorem 5.8.7  

(a) (Cauchy) Let $p$ be a prime dividing $\vert G\vert$ . There is a $g\in G$ of order $p$ .

(b) (Lagrange) Let $n$ be an integer not dividing $\vert G\vert$ . There does not exist a $g\in G$ of order $n$ .

Part (a) will be proven below (see Corollary 5.13.4) and part (b) is a corollary of Theorem 5.9.3 below.

As an application of this: we shall see later that the Rubik's cube group $G$ has the property that $\vert G\vert=2^{27}3^{14}5^37^2 11$ . It follows from this and Lagrange's theorem that there is no move of the Rubik's cube of order $13$ but there is one of order $11$ . Assuming this can you show taht there is no move of order $52$ ?

Exercise 5.8.8   Find the order of the following elements:

(a) $$\left( \begin{array}{cc} 0 & i \\ -i & 0 \end{array} \right)$$ in $GL(2,\mathbb{C})$ ,

(b) $(1,2)(2,3)(3,4)$ ,

(c) $(1,2,3)(3,4,5)(5,6,7)$ ,

(d) $(1,2,3)(4,5,6)(7,8)$ .

Exercise 5.8.9   Let $G=\langle g\rangle$ and $\vert G\vert=12$ . Thus, $G=\{g, g_2, g_3, ..., g_{12}=1\}$ . Note that $h=g^9$ has order $4$ and $h^k$ isn't $1$ if $1<k<4$ .

Exercise 5.8.10   Let $G=\langle g\rangle$ and $\vert G\vert=15$ . Which elements of $G$ have order $15$ ? How many elements have order $5$ ? Order $3$ ?

Exercise 5.8.11   Let $X = \{1,2,3\}$ . We use the notation of Example 5.3.1 above.

(a) Let $G$ be the permutation group with generator $s_1, G = \langle s_1\rangle$ . Verify that there are only two elements in $G$ .

(b) What is the order of $s_5$ ?

(c) Let $G$ be the permutation group with generator $s_3$ , $G = \langle s_3\rangle$ . Verify that there are only three elements in $G$ .

(d) Find the order of $s_3$ .

(e) Show that $S_X = \langle s_1,s_2\rangle$ .

Exercise 5.8.12   Find the orders of each of the elements in $S_4$ .