One thing that I forgot to mention last time is that there is a very simple method of calculating products of permutations, and if I had 5 minutes and a chalk board, I would love to show you. However, I've been trying to think of a way that I could explain it thoroughly and concisely in writing (or in typing, whatever the case may be) but don't think I can do it, so I'm going to omit it instead of dedicating an entire entry to it. You shouldn't need to do any such calcuations while reading my blog (that is, if they're needed I'll just go ahead and give you the answers) so it shouldn't be a problem for now, but if you'd like to know, as always, feel free to ask.
In this post, I'm going to talk about some of the properties of the symmetric groups. I'm not going to prove most of them because the proofs are boring, but my hope is to explain it all well enough so that you can understand these very important groups a little bit better.
Definition: Disjoint Cycles
Let α=(a1,a2,...,ap) and β=(b1,b2,...,bq) be two cycles. Then α and β are called disjoint if their cycles have nothing in common, that is {ai : 1≤i≤p}∩{bj : 1≤j≤q}=∅
Let α=(a1,a2,...,ap) and β=(b1,b2,...,bq) be two cycles. Then α and β are called disjoint if their cycles have nothing in common, that is {ai : 1≤i≤p}∩{bj : 1≤j≤q}=∅
Theorem: Product of Disjoint Cycles
Every permutation in of a finite set can be expressed as a product of disjoint cycles.
Every permutation in of a finite set can be expressed as a product of disjoint cycles.
Recall that there are a bunch of different ways to express every permutation. In my last post I noted that (1523) = (134)(25)(12)(34) is one such example. However, what the above theorem says is that there is a "nice" way to write every permutation. What I mean by "nice" is that we like for permutations to be written as the product of cycles that don't have any numbers in common, which is what is meant by disjoint. If π = (1523) then although it is technically correct to write π = (134)(25)(12)(34), some of those cycles have numbers in common, so we prefer π = (1523). The next theorem is another reason its convenient to express a permutation as a product of disjoint cycles.
Theorem: Disjoint Cycles Commute
If α=(a1,a2,...,ap) and β=(b1,b2,...,bq) are two disjoint cycles then α∙β = β∙α.
If α=(a1,a2,...,ap) and β=(b1,b2,...,bq) are two disjoint cycles then α∙β = β∙α.
This theorem is pretty self-explanitory, but is quite nice. It is not an if and only if statement, though, which means that if two cycles commute they are not necessarily disjoint. As an example, (12)∙(21) = e = (21)∙(12) and these cycles are clearly not disjoint. However, though, it is quite rare to find two permutations that commute. In fact, for n>2, Z(Sn) = {e}.
The rest of the post is going to be dedicated to developing an important subgroup of the symmetric groups called the alternating group.
Theorem: Product of 2-Cycles
∀n>1, every permutation in Sn can be written as a product of 2-cycles.
∀n>1, every permutation in Sn can be written as a product of 2-cycles.
This theorem is best explained through examples. You can verify that (1426) = (16)(12)(14) and that (16243) = (13)(14)(12)(16). If you look at those two examples closely, hopefully you can see a pattern, and that pattern works for every cycle. We can then expand this to permutations of more than one cycles, so that (1347)(265) = (17)(14)(13)(25)(26). In fact, that particular method of turning any permutation into a product of 2-cycles is exactly how that theorem is proven. The proof of the next theorem is actually a little interesting, but it requires induction which I haven't shown you yet, so I'm going to have to leave it out.
Theorem: Always Even or Always Odd
Suppose that α∈Sn and both α = β1β2∙∙∙βp and α = γ1γ2∙∙∙γq where each βi and γj are 2-cycles. Then either p and q are both odd or p and q are both even.
Suppose that α∈Sn and both α = β1β2∙∙∙βp and α = γ1γ2∙∙∙γq where each βi and γj are 2-cycles. Then either p and q are both odd or p and q are both even.
This theorem says that if a permutation can be written as a product of an even number of 2-cycles then every way of writing that permutation as a product of 2-cycles has an even number of them and similarly, if a permutation can be written as a product of an odd number of 2-cycles then every way of writing that permutation as a product of 2-cycles has an odd number of them. Its hard to give examples of this because I can't show every possible representation of a permutation as 2-cycles (because there are an infinite number of them), however, you can observe that (13)(12)(15) = (1523) = (14)(13)(25)(12)(34). Also, (12)(34) = (12)(34)(12)(12) = (12)(34)(12)(12)(12)(12) and so on. This gives rise to the next definition.
Definition: Even and Odd Permutations
If a permutation can be written as the product of an even number of 2-cycles then that permutation is called even, and if a permutation can be written as the product of an odd number of 2-cycles then that permutation is called odd.
If a permutation can be written as the product of an even number of 2-cycles then that permutation is called even, and if a permutation can be written as the product of an odd number of 2-cycles then that permutation is called odd.
Now that we know the difference between even and odd permutations, we are ready to define the alternating group.
Theorem: An is a subgroup of Sn
For n>1, the set of all even permutations of Sn form a subgroup of Sn. This group is called the alternating group and is denoted An.
For n>1, the set of all even permutations of Sn form a subgroup of Sn. This group is called the alternating group and is denoted An.
Proof:
First note that e = (12)(12) so e∈An and An is non-empty. Now, choose α,β∈An. Note that since α and β are even, α = α1α2∙∙∙αp and β = β1β2∙∙∙βq where p and q are even integers and each αi and βj are 2-cycles. We then get that α∙β = α1α2∙∙∙αp∙β1β2∙∙∙βq so α∙β is the product of p+q 2-cycles and since each of p and q are even then p+q is even, thus α∙β∈An. Now, choose γ∈An. Then γ = γ1γ2∙∙∙γm and γ-1 = γ'1γ'2∙∙∙γ'n where m is even, n is some positive integer, and each γi and γ'j are 2-cycles. I now wish to show that n is even. Naturally we have that e = γ∙γ-1 = γ1γ2∙∙∙γm∙γ'1γ'2∙∙∙γ'n so e is the product of m+n 2-cycles. However, e = (12)(12), so e is even and m+n must also be even, but since m is even, n must also be even and thus γ-1∈An. Finally, by the two-step subgroup test, An is a subgroup of An.
First note that e = (12)(12) so e∈An and An is non-empty. Now, choose α,β∈An. Note that since α and β are even, α = α1α2∙∙∙αp and β = β1β2∙∙∙βq where p and q are even integers and each αi and βj are 2-cycles. We then get that α∙β = α1α2∙∙∙αp∙β1β2∙∙∙βq so α∙β is the product of p+q 2-cycles and since each of p and q are even then p+q is even, thus α∙β∈An. Now, choose γ∈An. Then γ = γ1γ2∙∙∙γm and γ-1 = γ'1γ'2∙∙∙γ'n where m is even, n is some positive integer, and each γi and γ'j are 2-cycles. I now wish to show that n is even. Naturally we have that e = γ∙γ-1 = γ1γ2∙∙∙γm∙γ'1γ'2∙∙∙γ'n so e is the product of m+n 2-cycles. However, e = (12)(12), so e is even and m+n must also be even, but since m is even, n must also be even and thus γ-1∈An. Finally, by the two-step subgroup test, An is a subgroup of An.
You'll note that Sn is always finite (since Ωn is always finite), so An is always finite and I could have used the finite subgroup test instead of the two-step subgroup test. I wanted to emphasise, though, that the even permutations of the permutation group on any set, Ω (even infinite sets), form a subgroup even if they aren't finite.
That's all the work we'll be doing specifically with the symmetric groups for a while except in a couple of posts I'm going to prove Cayley's Theorem. That's pretty exciting, because whenever a theorem is named after someone, its usually pretty important. Before I do that, though, I'm going to introduce isomorphisms.
References
Previous Related Post: Symmetric Groups
Text Reference: Gallain Chapter 5
Wikipedia: Symmetric Groups
No comments:
Post a Comment