Symmetric Groups

As I mentioned last time, this post is going to be about some of the most important groups in mathematics, the symmetric groups. They are not extremely difficult in that they are more natural than the dihedral groups, but they are rather difficult to explain so bear with me and, as always, ask questions.

I'm going to start using the notation Ω_n to denote the set of integers from 1 to n, or in symbols, Ω_n = {1,2,...,n} and I will use Ω to denote any arbitrary set. I'm going to define a function, σ, that takes Ω₅ to Ω₅ by σ(1)=3, σ(2)=5, σ(3)=4, σ(4)=1, and σ(5)=2. This function, σ, is called a permutation. The reason for this is that it takes each element of Ω₅ to a different element of Ω₅. The best way to think about a permutation, though, is as a way to shuffle, or rearrange the integers. Our σ function reorders Ω₅ in that applying σ to [1,2,3,4,5] gives [σ(1),σ(2),σ(3),σ(4),σ(5)] or [3,5,4,1,2]. A permutation is simply any function that takes shuffles Ω_n around in some order like σ did. As a matter of notation, if the particular permutation is implied, say σ, then we sometimes denote σ(1)=3 by 1→3. Below I'm going to give the formal definition of a permutation, but it is not a very useful definition and you don't need to be too concerned if it doesn't make much sense.

Definition: Permutation
Let Ω be any arbitrary set. A permutation of Ω is a bijection from Ω to Ω.

Like I said, this definition is more formal than the way we traditionally think of permutations. Usually a permutation is not defined as I defined σ simply because its too cumbersome. Instead, one notation is as follows.

The notation above tells where each element of Ω₅ is mapped (the elements in the top line map to the elements directly below them) and gives a good visual representation of the "shuffling." One thing to notice is that σ gets broken down into partitions. Notice that 1→3, 3→4, and 4→1. Similarly, 2→5 and 5→2. This partitions {1,3,4} from {2,5}. Pictorially, we can show this as follows:

Using this as a guideline, we introduce a new notation that we call cycle notation. We take each of these cycles and put them in parenthases in the order of their arrows (the starting point is irrelevant). As an example, σ = (1,3,4)(2,5). We think of the end of one cycle as going back to the beginning of the cycle, so then (1,3,4) = (3,4,1) because they would generate the same picture. However, it should be noted that (1,3,4) ≠ (1,4,3) because 1→3, 3→4, 4→1 is not the same as 1→4, 4→3, 3→1. If n<10 and σ is a permutation of Ω_n, then we generally leave out the commas so that σ = (134)(25).

Hopefully its now clear what a permutation of Ω_n is, and now we need to know how these permutations form a group.

Definition: The Symmetric Group, S_n
Let Ω_n = {1,2,...n} for some positive integer, n, and let S_n be the set of all permutations of Ω_n. Then S_n forms a group under the operation of function composition and is called a Symmetric Group.

I'm not going to formally prove that this is a group, but I am going to talk through the justification. First, though, it is very important to understand the operation of composition. Let σ and τ be permutations of Ω_n. As group elements, we say that σ∙τ is the composition of the two functions, σ∘τ = σ(τ). If you're not familiar with function composition, what this means is that ∀i∈Ω_n, (σ∙τ)(i) = (σ∘τ)(i) = σ(τ(i)). Suppose that σ = (134)(25) and τ = (12)(34) are elements of S₅ and we'd like to calculate σ∙τ. We can first calculate (σ∙τ)(1) = σ(τ(1)) = σ(2) = 5. A similar calculation for the rest of Ω₅ yields that σ∙τ = (134)(25)(12)(34) = (1523)(4) (it may be useful to perform this calculation yourself).

Now that we undestand function composition, I can try to convince you that S_n is a group for each positive integer, n. This is going to require some properties of bijective functions, though, and I'm going to use them without proof or explanation, but if you want an explanation, I'll be happy to provide it. Closure on S_n immediately follows from the fact that composition of bijective functions is also bijective, and associativity come for free because all functions are associative under composition. The identity element is the identity function, ε, that maps each element of Ω_n to itself. Finally, a property of every bijective function is that it is invertible, so every element in S_n has an inverse.

There are a couple more things to tidy up about the symmetric groups. We call a cycle with n elements in it an n-cycle. As an example, (134) is a 3-cycle. Also, any 1-cycle is the identity element. This is easy to see, as (1) only sends 1 to itself. Because of this, we generally omit 1-cycles. Earlier we showed a computation that resulted in σ∙τ = (1523)(4). However, the (4) is usually left off because it does not affect the cycle at all, so we write (1523)(4) = (1523). Thus, as a matter of convention, if a permutation is an element of S_n and its cycles omit some elemets of Ω_n, then it is assumed that the missing elements are mapped to themselves. One last thing that should be noted is that permutations do not have unique cycle structures. In fact, as we saw earlier, if π = (1523) then we can also write it as π = (134)(25)(12)(34). However, as we will see in my next post, every permutation can be expressed uniquely as a product of disjoint cycles (disjoint cycles don't contain any of the same numbers).

Like I said earlier, these symmetric groups are extremely important. A lot of the applications involving symmetric groups are typically deeply embedded within seeminly unrelated things, so it is probably not very informative for me to list them. However, what permutations do is shuffle things around and reorder things (our examples only shuffled numbers, put remember that Ω can be any arbitrary set), so maybe you can at least conceive of the vast usefulness of the group structure of these permutations. In my next post I'm going to discuss some of the elementary properties of symmetric groups.

References

Previous Related Post: Dihedral Groups

Text Reference: Gallain Chapter 5

Wikipedia: Symmetric Groups