3: The Symmetric Groups
( \newcommand{\kernel}{\mathrm{null}\,}\)
Recall that if n is a positive integer, [n]={1,2,…,n}. A permutation of [n] is a one-to-one, onto function from [n] to [n] and Sn is the set of all permutations of [n]. If these terms are not familiar, it would be a good idea to take some time to study Appendix B before proceeding.
Let us discuss the different ways to specify a function from [n] to [n] and how to tell when we have a permutation. It is traditional (but not compulsory) to use lower case Greek letters such as σ, τ, α, β, etc., to indicate elements of Sn. To be specific let n=4. We may define a function σ:[4]→[4] by specifying its values at the elements 1,2,3, and 4. For example, let’s say: σ(1)=2σ(2)=3σ(3)=1σ(4)=4. Another way to specify σ is by exhibiting a table which gives its value: σ=(12342314). We call this the two line or two row notation. The function σ just defined is one-to-one and onto, that is, it is a permutation of [4].
For another example, let τ=(12341314). The function τ is not one-to-one since 1≠3 but τ(1)=τ(3). This problem can always be identified by the existence of the same element more than once in the second line of the two line notation. τ is also not onto since the element 2 does not appear in the second line.
Let σ=(12⋯nσ(1)σ(2)⋯σ(n)). be the two line notation of an arbitrary function σ:[n]→[n]. Then:
- σ is one-to-one if and only if no element of [n] appears more than once in the second line.
- σ is onto if and only if every element of [n] appears in the second line at least once.
Thus σ is a permutation if and only if the second row is just a rearrangement or shuffling of the numbers 1,2,…,n.
The Composition of Two Permutations
If σ and τ are elements of Sn, then στ is defined to be the composition of the functions σ and τ. That is, στ is the function whose rule is given by: στ(x)=σ(τ(x)), for all x∈[n]. We sometimes call στ simply the product of σ and τ. Let’s look at an example to see how this works. Let σ and τ be defined as follows: σ=(123213),τ=(123231) It follows that στ(1)=σ(τ(1))=σ(2)=1στ(2)=σ(τ(2))=σ(3)=3στ(3)=σ(τ(3))=σ(1)=2 Thus we have στ=(123132) One can also find products of permutations directly from the two line notation as follows: First Step:(123213)(123231)=(1231−−) Second Step:(123213)(123231)=(12313−) Third Step:(123213)(123231)=(123132)
Problem 3.1 Compute the following products in S4:
(1)(12344321)(12341234) (2)(12341234)(12344321) (3)(12344321)(12344321) (4)(12341432)(12344123)
Whenever we need to prove two functions are equal, we require the following definition:
If σ:A→B and τ:A→B are functions then σ=τ if and only if σ(x)=τ(x),for all x∈A. In particular, if σ and τ are in Sn then σ=τ if and only if σ(x)=τ(x),for all x∈[n].
The identity of Sn
The identity of Sn is the so-called identity function ι:[n]→[n]. which is defined by the rule: ι(x)=x, for all x∈[n]. In the two line notation ι is described by ι=(12⋯n12⋯n) The function ι is clearly one-to-one and onto and satisfies ισ=σand σι=σ, for all σ∈Sn. So ι is the identity of Sn with respect to the binary operation of composition.
The inverse of an element σ∈Sn:
If σ∈Sn, then by definition σ:[n]→[n] is one-to-one and onto. Hence the rule σ−1(y)=x if and only if σ(x)=y defines a function σ−1:[n]→[n]. The function σ−1 is also one-to-one and onto (check this!) and satisfies σσ−1=ι and σ−1σ=ι, so it is the inverse of σ in the group sense also.
In terms of the two line description of a permutation, if σ=(⋯x⋯⋯y⋯) then σ−1=(⋯y⋯⋯x⋯)
The inverse of a permutation in the two line notation may be obtained by interchanging the two lines and then reordering the columns so that the numbers on the top line are in numerical order. Here’s an example: σ=(123231) Interchanging the two lines we have: (231123). Reordering the columns we obtain σ−1=(123312).
Problem 3.2 Find the inverses of each of the following permutations in two line notation. Check in each case that σσ−1=ι and σ−1σ=ι.
-
σ=(12342314)
-
σ=(1234523451)
For any three functions α:A→B,β:B→C,γ:C→D we have (γβ)α=γ(βα).
Proof Let x∈A. Then (γβ)α(x)=γβ(α(x))=γ(β(α(x))). and γ(βα)(x)=γ(βα(x))=γ(β(α(x))). It follows that (γβ)α(x)=γ(βα)(x) for all x∈A. Hence (γβ)α=γ(βα).
Corollary 3.2 The binary operation of composition on Sn is associative.
With this corollary, we complete the proof that Sn under the binary operation of composition is a group.
The Cycle Diagram of a Permutation
An important way to visualize an element σ of Sn is as follows. Arrange n dots in the plane. Number the dots 1 through n. For all i∈[n], if σ(i)=j draw an arrow from dot number i to dot number j. We call this picture the cycle diagram of σ. To get a nice picture, it is best to use the following technique for drawing the diagram.
- Draw a dot and number it 1. Let i1=σ(1). If i1≠1 draw another dot and label it i1.
- Draw an arrow from dot 1 to dot i1. (Note that i1=1 is possible.)
- Assume that dots numbered 1,i1,i2,…,ik have been drawn. Consider two cases:
- (i)
-
There is an arrow leaving every dot drawn so far. In this case let ik+1 be the smallest number in [n] not yet labeling a dot. If there are no such then stop, you have completed the diagram, otherwise draw a new dot and label it ik+1
- (ii)
-
There is a dot numbered j with no arrow leaving it. In this case let ik+1=σ(j). If there is no dot labeled ik+1 draw a new dot and label it ik+1. Draw an arrow from dot j to dot ik+1.
- Now repeat step 3 with k+1 replacing k.
Example 3.1: The cycle diagram of the following permutation is given in Figure 3.1. α=(123456789101112131415131176543102121411598).
Notice that the diagram consists of five “cycles”: one “6-cycle”, one “4-cycle”, two “2-cycles” and one “1-cycle”. Every cycle diagram will look something like this. That’s why we call it the cycle diagram.
[diagram goes here]
The cycle diagram of α from Exercise 3.1
Problem 3.3 Draw the cycle diagrams for all 24 elements of S4. You will need a systematic way to list the elements S4 to make sure you have not missed any.
We now give a more precise definition of a “cycle”.
Let i1,i2,…,ik be a list of k distinct elements from [n]. Define a permuation σ in Sn as follows: σ(i1)=i2σ(i2)=i3σ(i3)=i4⋮⋮⋮σ(ik−1)=ikσ(ik)=i1 and if x∉{i1,i2,…,ik} then σ(x) = x Such a permutation is called a cycle or a k-cycle and is denoted by (i1 i2 ⋯ ik). If k=1 then the cycle σ=(i1) is just the identity function, i.e., σ=ι.
For example, let σ be the 3-cycle defined by σ=(3 2 1). σ may be considered as an element of S3 in which case in two line notation we have σ=(123312). Notice that according to the definition if x∉{3,2,1} then σ(x)=x. So we could also consider (3 2 1) as an element of S4. In which case we would have: σ=(12343124). Or we could consider (3 2 1) as an element of S5. In which case we would have: σ=(1234531245). Similarly, (3 2 1) could be an element of Sn for any n≥3. Note also that we could specify the same permutation by any of the following σ=(3 2 1),σ=(2 1 3),σ=(1 3 2). In this case, there are three numbers 1, 2, 3 in the cycle, and we can begin the cycle with any one of these. In general, there are k different ways to write a k-cycle. One can start with any number in the cycle.
Problem 3.4 Below are listed 5 different cycles in S5.
(a) Describe each of the given cycles in two line notation.
(b) Draw the cycle diagram of each cycle.
- (4)
- (3 4)
- (4 1 5)
- (1 3 5 4)
- (1 3 5 4 2)
Two cycles (i1 i2 ⋯ ik) and (j1 j2 ⋯ jℓ) are said to be disjoint if the sets {i1,i2,…,ik} and {j1,j2,…,jℓ} are disjoint.
So, for example, the cycles (1 2 3) and (4 5 8) are disjoint, but the cycles (1 2 3) and (4 2 8) are not disjoint.
If σ and τ are disjoint cycles, then στ=τσ.
Proof Let σ=(a1⋯ak) and τ=(b1⋯bℓ). Let {c1,⋯,cm} be the elements of [n] that are in neither {a1,…,ak} nor {b1,⋯,bℓ}. Thus [n]={a1,…,ak}∪{b1,⋯,bℓ}∪{c1,⋯,cm}. We want to show στ(x)=τσ(x) for all x∈[n]. To do this we consider first the case x=ai for some i. Then ai∉{b1,⋯,bℓ} so τ(ai)=ai. Also σ(ai)=aj, where j=i+1 or j=1 if i=k. So also τ(aj)=aj. Thus στ(ai)=σ(ai)=aj=τ(aj)=τ(σ(ai)=τσ(ai). Thus, στ(ai)=τσ(ai). It is left to the reader to show that στ(x)=τσ(x) if x=bi or x=ci, which will complete the proof.
Problem 3.5 Show by example that if two cycles are not disjoint they need not commute.
The factorization (3.41) is called the disjoint cycle decomposition of σ.
To save time we omit a formal proof of this theorem. The process of finding the disjoint cycle decomposition of a permutation is quite similar to finding the cycle diagram of a permutation. Consider, for example, the permutation α∈S15 α=(123456789101112131415131176543102121411598). The disjoint cycle decomposition of α is α=(1 13 15 8 10 12)(2 11 14 9)(3 7)(4 6)(5). Compare this with the cycle diagram given for this same permutation on page . To obtain this, one starts a cycle with 1, since α(1)=13 we have the partial cycle (1 13. Next, we observe that α(13)=15. This gives the partial cycle (1 13 15. We continue in this way till we obtain the cycle (1 13 15 8 10 12). Then we pick the smallest number in [15] not used so far, namely, 2. We start a new cycle with 2: Noting that α(2)=11 we have the partial cycle (2 11. Continuing we obtain the cycle (2 11 14 9). And we continue in this way till all the elements of [15] are in some cycle.
Problem 3.6 Find the disjoint cycle decomposition of the following permutations in S6:
σ=(123456234165)
σ=(123456324651)
σ=(123456125436)
Problem 3.7 Find the disjoint cycle decomposition of the following permutations in S6: [Each permutation is given as a product of cycles. Try to do this without converting the cycle notation to the two line notation.]
(1) (1 2 3)(2 4 5)
(2) (3 4 5 1 2)(4 5 6)(1 2 3)
(3) (1 3)(1 2)
(4) (1 4)(1 3)(1 2)
Problem 3.8 (a) Verify that if a,b,c,d,e are distinct elements of [n] then each of the following cycles can be written as a product of 2-cycles: [Hint: look at (3) and (4) in Problem 3.7.] (b) Verify that the inverse of each of these cycles is a cycle of the same size.
(1) (a b c).
(2) (a b c d)
(3) (a b c d e).
An element of Sn is called a transposition if and only if it is a 2-cycle.
Note that the transposition (i j) interchanges i and j and leaves the other elements of [n] fixed. It transposes i and j.
An integer n is even if n=2k for some integer k. It is odd if n=2k+1 for some integer k. The parity of an integer is the property of being even or odd. Two integers have the same parity if they are both even or if they are both odd. They have different parity if one is even and the other is odd.
Every element of Sn can be written as a product of transpositions. The factors of such a product are not unique, however, if σ∈Sn can be written as a product of k transpositions and if the same σ can also be written as a product of ℓ transpositions, then k and ℓ have the same parity. ◼
The first part of this theorem is easy. Generalizing Problem 3.7, we see that every cycle can be written as a product of transpositions as follows: (i1 i2 i3 ⋯ik)=(i1 ik)⋯(i1 i3)(i1 i2). Then, since each permutation is a product of cycles, we can obtain each permutation as a product of transpositions. The second part is more difficult to prove and, in the interest of time, we omit the proof. A nice proof may be found in Fraleigh (, page 108.)
Problem 3.9 Write the permutation α on page as a product of transpositions. Do it in more than one way. How many transpositions are in each of your products?
Problem 3.10 Give the disjoint cycle decomposition of each of the 6 elements of S3. Also write each element of S3 as a product of transpositions.
A permutation is even if it is a product of an even number of transpositions and is odd if it is a product of an odd number of transpositions. We define the function sign:Sn→{1,−1} by sign(σ)={1if σ is even−1if σ is odd If n=1 then there are no transpositions. In this case to be complete we define the identity permutation ι to be even.
Problem 3.11 Show that the function sign satisfies sign(στ)=sign(σ)sign(τ) for all σ and τ in Sn.
Let A=[aij] be an n×n matrix. The determinant of A may be defined by the sum det For example, if n=2 we have only two permutations \iota and (1 \ 2). Since \mathrm{sign}(\iota) = 1 and \mathrm{sign}((1 \ 2)) = -1 we obtain \det(A) = a_{1 1}a_{2 2} - a_{ 1 2}a_{2 1}.
Problem 3.12 Find the sign of each element of S_3 and use this information to write out the formula for \det (A) when n = 3. (Note that in this case the determinant is a sum of 6 terms.)
Problem 3.13 If n=10 how many terms are in the above formula for the determinant?
If (G,*) is a group, the number of elements in G is called the order of G. We use \vert G\vert to denote the order of G.
Note that \vert G\vert may be finite or infinite. If it is finite \vert G\vert=n for some positive integer n. An interesting but difficult problem is that of determining all groups of a fixed order n. For small n this can be done as we shall see, but there seems to be no hope of answering the question for all values of n in spite of the efforts of many mathematicians who specialize in the study of finite groups.
Problem 3.14 Find \vert GL(2,\mathbb{Z}_2) \vert and \vert M_2(\mathbb{Z}_2) \vert.
\vert S_n \vert = n! for all n \ge 1.
Proof Let n be any positive integer. Elements of S_n have the form
\left ( \begin{array} {ccccc} 1&2&3&\dots&n \\ a_1&a_2&a_3&\dots &a_n \end{array} \right) where a_1, a_2, \dots , a_n is any rearrangement of the numbers 1,2, \dots, n. So the problem is how many ways can we select the a_1, a_2, \dots , a_n? Note that there are n ways to select a_1. Once a choice is made for a_1, there are n-1 remaining possibilities for a_2. Thus, there are altogether n(n-1) ways to select a_1a_2. Then, for each choice of a_1a_2, there are n-2 remaining possibilities for a_3. Thus, there are n(n-1)(n-2) ways to select a_1a_2a_3. Continuing in this way, we see that there are n(n-1)(n-2)\cdots2\cdot 1 = n! ways to choose a_1, a_2, \dots , a_n. \blacksquare
Problem 3.15 Show that the inverse of a k-cycle is also an k-cycle. Hint: Show that if a_1,a_2, \dots, a_k are distinct elements of [n] then (a_1 \ a_2)^{-1} = (a_2 \ a_1) (a_1 \ a_2 \ a_3)^{-1} = (a_3 \ a_2\ a_1) (a_1 \ a_2 \ a_3 \ a_4)^{-1} =(a_4 \ a_3 \ a_2 \ a_1) and more generally (a_1 \ a_2 \ \cdots \ a_k)^{-1} =(a_k \ \cdots \ a_2 \ a_1) Hint: Let \sigma = (a_1 \ a_2 \ \cdots \ a_k) and \tau = (a_k \ \cdots \ a_2 \ a_1). Show that \tau (\sigma(a_i)) = a_i for all i by considering three cases: i \notin \{1,2,\dots, k\}, i \in \{1,2,\dots, k-1\} and i=k.
Problem 3.16 Show that if \sigma is a k-cycle then \mathrm{sign}(\sigma) =1 if k is odd and \mathrm{sign}(\sigma) = -1 if k is even.
Problem 3.17 [Challenge Problem] For \sigma \in S_n prove that \begin{aligned} \sigma \mbox{ is even } &\Longleftrightarrow& \prod_{i<k} \frac {\sigma(k) -\sigma (i)}{k-i} = 1 \\ \qquad \sigma \mbox{ is odd } \; \; &\Longleftrightarrow& \prod_{i<k} \frac {\sigma(k) -\sigma (i)}{k-i} = - 1\end{aligned}