The Unapologetic Mathematician

Mathematics for the interested outsider

Permutation groups

UPDATE: Since I noticed later that the convention that makes things simplest in group actions is to compose permutations right-to-left, I’ve gone back and tweaked that here.

Today I want to go into an example of a group in a lot more detail. It looks pretty long, so I’ll just put the whole thing behind the jump

A permutation is just a rearrangement. You have some number of things in a row, then the permutation picks them up and shuffles them about. We can write this down by making a table listing first what place in line an object has before the permutation, and then what place it has after.
|1 2 3 4|
|2 1 4 3|

This one — call it f — picks up whatever is in slot 1 and puts it into slot 2. Whatever was in slot 2 goes to slot 1. Similarly it swaps the contents of slots 3 and 4.
|1 2 3 4|
|4 2 1 3|

This one — call it g — leaves slot 2 alone and cycles the contents of the other three slots: 1 goes to 4 goes to 3 goes to 1.

In each of these, we determine where it puts the contents of a given slot by finding that slot in the top row and reading off the number below it. We can use this method to put together two rearrangements to make a third. For example, if we first do f and then do g we see that f sends what’s in slot 1 to slot 2, which g leaves alone. Check the rest of the slots to verify that this composition, which I’ll write as gf, is expressed as
|1 2 3 4|
|2 4 3 1|

while if we compose in the other order the result fg is
|1 2 3 4|
|3 1 2 4|

so the order of composition definitely makes a difference. As a side note, some authors write group composition the other way around, so what I call gf they call fg and vice versa. It doesn’t really matter in the long run; the important thing is to pick a convention and stick with it. [Actually, originally I had written these the other way around, thinking it would be clearer to read left-to-right. If this convention seems confusing, think of it like function composition: fg is like f(g(x)).]

Now, that notation above really wastes a lot of space. The whole first line is completely redundant, for instance, and in this medium I can’t write them inline. Here’s another way to write down a permutation: I look at f and start with slot 1, writing
(1
Now I see that slot 1 is sent to slot 2, so I write that down
(1 2
I see that 2 is sent back to 1, which puts me back where I started. I’ll close off this loop and start over with 3.
(1 2)(3
Now 3 is sent to 4, which goes back to 3, closing off this loop too. Since I’ve used all four slots, I’m done. The expression is
(1 2)(3 4)

We read one of these from left to right, each slot moving to the next in line, and the one before a closing paren looping around to the beginning again. As another example, g becomes (1 4 3)(2). Slot 1 goes to 4 goes to 3 goes back to 1, and slot 2 is left alone. In fact from here we’ll just assume that any slot that doesn’t show up is left alone, so we write g as (1 4 3). It’s important to note that the parens here do not denote the same thing as they do in arithmetic, telling which operations to do first. These parens mark out the cycles in the permutation.

We can even use this notation for compositions, reading the permutations from right to left. The composition fg becomes (1 2)(3 4)(1 4 3). Reading this from the right, the first cycle sends 1 to 4, which the second sends to 3 and the third leaves alone. The first cycle sends 3 to 1, and the third sends that to 2. Now 2 makes it all the way through to the third cycle. This produces (1 3 2) and 4 must be sent to itself, as it’s the only slot left. The composition in the opposite order gives (1 4 3)(1 2)(3 4) = (1 2 4). See if you can get this result.

Now, every example up until this point has been working with permutations on 4 slots. I’ve shown how to compose such permutations, doing one after the other. Doing nothing also counts as a permutation, and it’s the identity permutation we need. Finally, it should be clear that any permutation can be undone, leaving things as they were before. This means that these permutations form a group which we call S_4 for the “symmetric group on 4 elements”. If the permutations shuffled around five things we’d get the group S_5, and so on for any number n we can make the group S_n.

These groups have all sorts of nice properties. For one thing, it’s easy to find their size. First we have n choices of where to send 1, then we have n-1 choices of where to send 2 (since it can’t be sent to the same place we just sent 1), and so on until we only have one choice left where to send n. We multiply all these numbers together to get the total number of choices: n*(n-1)*(n-2)*...*2*1. We say “n factorial” for this product of all the numbers from 1 to n, writing it n!.

Here’s another neat thing: any permutation can be written as a composition of cycles of length 2. Obviously it can be written in terms of cycles, since that’s the second notation we gave. What I’m saying is that you can break long cycles down into just swaps. For 3-cycles and 4-cycles verify these expressions
(a\,b\,c\,)=(a\,c)(a\,b)
(a\,b\,c\,d)=(a\,d)(a\,c)(a\,b)
and see if you can recognize the general rule.

There are many ways to write a given permutation in terms of swaps, but one thing is always true: the number of swaps needed is either always even or always odd, and we call permutations “even” or “odd” according to which case they fall into, called the “parity” of the permutation. I’m not going to prove this fact here, though it’s not hard to find a proof. This fact turns out to be amazingly significant in all sorts of unexpected ways.

Again I’ll close with a few problems to play with

  • The identity permutation is even
  • An n-cycle is even if n is an odd number, and vice versa
  • How does the parity of fg relate to the parities of f and g?
  • How does the parity of f^{-1} relate to that of f?
  • Fill in the details showing that S_n is a group. That is, show that composition is associative, that the identity permutation really behaves like an identity, and that every permutation has an inverse.
About these ads

February 3, 2007 - Posted by | Algebra, Group theory, Structure of Groups

43 Comments »

  1. what’s next on jour agenda? Galois theory?

    Comment by babi | February 4, 2007 | Reply

  2. I don’t really have an agenda, babi. I’m not following a text or anything here.

    That said, if I ever do Galois theory it will be much further along. I don’t see how one could present it at this point, which makes me wonder (along with your penchant for creating straw men in other commend threads) if you’re being facetious here. No matter.

    I’m not sure what I’ll do next, but homomorphisms are right up there.

    Comment by John Armstrong | February 4, 2007 | Reply

  3. [...] else the same, and the permutations of the corners and the edges are either both even or both odd (remember what we mean by “even” and “odd” permutations). I’ll prove the last one [...]

    Pingback by Rubik’s Magic Cube « The Unapologetic Mathematician | February 22, 2007 | Reply

  4. [...] work out how symmetric groups act on themselves by conjugation. As I’m writing I notice that what I said before about composition of permutations is sort of backwards. It’s one of those annoying [...]

    Pingback by Conjugacy classes in symmetric groups « The Unapologetic Mathematician | February 23, 2007 | Reply

  5. Hi. Just stumbled upon your site. I’ve been working with cycles on a purely intuitive basis in music composition. I’ve been trying to assign cycles into families based on mapping. I wonder if you could steer a non-mathematician in the right direction. Thanks.

    Comment by John | March 1, 2007 | Reply

  6. Oh it turns out there’s quite a lot of group theory in music theory these days. I suppose I should post about that sometime. I first heard of it from this posting by John Baez. There’s a bunch of links in there that should take you into other stuff.

    Sometime soon I’ll try to see what I can say about it and make a post myself.

    Comment by John Armstrong | March 1, 2007 | Reply

  7. [...] you can’t lift them up. How can you rearrange them? At first, you might think this is just a permutation group all over again, but not quite. Let’s move two shells around each other, taking a picture of [...]

    Pingback by Braid groups « The Unapologetic Mathematician | March 14, 2007 | Reply

  8. I have a question. At the beginning you write:
    |1 2 3 4|
    |4 2 1 3|

    and call this permutation g. You further write
    “This one — call it g — leaves slot 2 alone and cycles the contents of the other three slots: 1 goes to 4 goes to 3 goes to 1.”
    and write the permutation g as (143)

    But isn’t it:
    1 goes to 3, (The content of slot 1 goes to slot 3)
    3 goes to 4, (the content of slot 3 goes to slot 4)
    4 goes to 1 ? (the content of slot 4 goes to slot 1).

    In other words, does the notation (143) refer to
    the slots or the contents of the slots?

    Comment by Edgardo | March 25, 2007 | Reply

  9. All the numbers refer to slots. The first notation means that whatever’s in a slot on the top row goes into the corresponding slot on the bottom row. 1 is above 4, so whatever’s in slot 1 goes into slot 4. It sounds like you may be reading the two-row version from bottom to top, rather than from top to bottom.

    Comment by John Armstrong | March 25, 2007 | Reply

  10. Thanks for the answer.
    I see now, I’ve been confused by the notation.
    Let me ask again just to make sure I’ve understood it correctly.

    Consider the four letters A,B,C,D.
    Applying (1,4,3) to
    A,B,C,D results in
    C,B,D,A

    In the first notation this would be
    |1 2 3 4|
    |4 2 1 3|
    I’m very interested in this
    because I want to learn how to solve the Rubik’s cube
    blindfolded. There’s a tutorial here:
    http://homepage.ntlworld.com/angela.hayden/cube/blindfold_frontpage.html
    but I didn’t understand the notation here:
    http://homepage.ntlworld.com/angela.hayden/cube/blind2.html

    Thanks for this blog entry.

    Comment by Edgardo | March 25, 2007 | Reply

  11. Yeah, that’s how it works. Really the cycle notation is a lot more important to understand than the two-line version. In fact, I tweak the cycle notation to describe maneuvers on Rubik’s cube. Ms. Hayden also used the cycle notation on her page.

    Good luck with that project. The notation there I find to be less suggestive than my own, but I suppose it’s more conducive to memorizing the move to be performed.

    Comment by John Armstrong | March 25, 2007 | Reply

  12. Hello John, I just found a cool interactive program on permutations here:
    http://nrich.maths.org/public/viewer.php?obj_id=2781&part=index

    Tutorial on how to use the Shuffly Factory Program:
    http://nrich.maths.org/public/viewer.php?obj_id=2789&part=

    Link to the Shuffle Factory Program:
    http://nrich.maths.org/public/viewer.php?obj_id=2741&part=index

    Comment by Edgardo | April 10, 2007 | Reply

  13. [...] is a module over . We just define and extend linearly. But we also have a homomorphism from the symmetric group to the monoid of endomorphisms of . For a permutation we define , shuffling around the factors. [...]

    Pingback by More about hom « The Unapologetic Mathematician | April 24, 2007 | Reply

  14. “Here’s another neat thing: any permutation can be written as a composition of cycles of length 2″

    Uniquely??

    Because I seem to be able to generate bca using either;

    (a c)(a b) or (a b)(b c)

    or am I missing something?

    Comment by Michael Casidy | July 15, 2007 | Reply

  15. Michael, I didn’t say “uniquely” because I didn’t mean to.

    Comment by John Armstrong | July 15, 2007 | Reply

  16. when you say it’s ove. Liana Merete.

    Comment by Liana Merete | September 19, 2007 | Reply

  17. [...] So let’s look for something not quite so obvious. There are various ways of solving the problem, but the one I’m interested in uses the fact that what we’re really looking at is a permutation! [...]

    Pingback by The Airplane Seat solution « The Unapologetic Mathematician | October 26, 2007 | Reply

  18. In the pick 4 lottery how do you calculate 4,320,360 and 270 for numbers of the form 1123,1222 and 1122?

    Comment by michael farley | April 4, 2008 | Reply

  19. michael, that’s really more a question for Isabel than for me.

    Comment by John Armstrong | April 4, 2008 | Reply

  20. [...] of real numbers, we can reorder the list in many ways. In fact, reorderings of numbers form the symmetric group . If we look back at our group theory, we see that we can write any element in this group as a [...]

    Pingback by Commutativity in Series I « The Unapologetic Mathematician | May 8, 2008 | Reply

  21. [...] powers of the standard representation of . Today we’ll look at some representations of the symmetric group and see how they’re [...]

    Pingback by Some Symmetric Group Representations « The Unapologetic Mathematician | December 4, 2008 | Reply

  22. [...] back when I defined permutation groups I talked about a permutation being even or odd. Remember that we showed that permutation can be written out as a composite of transpositions which [...]

    Pingback by The Signum Representation « The Unapologetic Mathematician | December 18, 2008 | Reply

  23. [...] and Antisymmetrizer Today we’ll introduce two elements of the group algebra of the symmetric group which have some interesting properties. Each one, given a representation of the symmetric group, [...]

    Pingback by The Symmetrizer and Antisymmetrizer « The Unapologetic Mathematician | December 19, 2008 | Reply

  24. [...] when I defined permutation groups, I gave a quick argument about how to count their orders. That is, how many elements are in the [...]

    Pingback by Permutations and Combinations « The Unapologetic Mathematician | December 29, 2008 | Reply

  25. Hi, still not clear with the product mappings. for example fg or gf.

    if i start with 1 2 3 4 = X , then mapping for
    f is 1 2 3 4 -> 2 1 4 3, does this mean f(X) is 2 1 4 3 ?

    now to get g(f(x)) , the g mapping is 4 2 1 3 , so does this mean 2 1 4 3 = f(x) -> 4 1 3 2 = g(f(x))
    if i use the 4 2 1 3 mapping ?

    im confused , please can you do the steps of computation for fg or gh

    Comment by FatTail | January 2, 2009 | Reply

  26. I say very explicitly in the text above that \left[fg\right](x)=f(g(x)). Apply the factors from right to left.

    Comment by John Armstrong | January 2, 2009 | Reply

  27. Ok, if X = 1 2 3 4, then g(X) is ,where -> means maps

    1->4
    2->2
    3->1
    4->3

    so g(x) is 3 2 4 1

    now i apply f to g(x)

    f has mapping
    1->2
    2->1
    3->4
    4->3

    so using f on g(x) should give

    2 3 1 4

    what is incorrect about these steps ?

    Comment by FatTail | January 2, 2009 | Reply

  28. You’re still doing it in the wrong order.

    1-g->4-f->3
    2-g->2-f->1
    3-g->1-f->2
    4-g->3-f->4

    Comment by John Armstrong | January 2, 2009 | Reply

  29. i get it now.
    nothing to do with my order just the way i was doing it :)
    i think the slot thing confused me. for example for fg
    i was doing 1 goes to slot 4, then 4 is moved to slot 3.
    whereas it should be 1 becomes 4, then 4 becomes 3, then 3 goes to slot 1.
    thanks for replying

    Comment by FatTail | January 2, 2009 | Reply

  30. [...] columns (or, equivalently, rows) are and . The swaps generate a subgroup of isomorphic to the symmetric group . In fact, these are the image of the usual generators of under the permutation representation. [...]

    Pingback by Elementary Matrices « The Unapologetic Mathematician | August 26, 2009 | Reply

  31. [...] see this, remember that symmetrizing the whole term involves a sum over the symmetric group , while symmetrizing over the beginning involves a sum over the subgroup consisting of those [...]

    Pingback by Tensor and Symmetric Algebras « The Unapologetic Mathematician | October 26, 2009 | Reply

  32. i have presentation about gorup of permutation with thier exampel in geomatry it main thier exampl would be in geomatry i do not know how i find this can you guide me from where i can find this please

    Comment by zohal | December 27, 2009 | Reply

  33. [...] there are only finitely many vectors (say of them) in to begin with, so must act as some sort of permutation of the vectors in . But every permutation in has an order that divides . That is, applying [...]

    Pingback by A Lemma on Reflections « The Unapologetic Mathematician | January 19, 2010 | Reply

  34. [...] we can also realize as a subgroup of the group of permutations on the vectors in . Indeed, by definition each sends each vector in back to another vector in , [...]

    Pingback by The Weyl Group of a Root System « The Unapologetic Mathematician | January 21, 2010 | Reply

  35. [...] of a given vector. That is, the Weyl group of the system is naturally isomorphic to the symmetric group . Possibly related posts: (automatically generated)Coxeter Graphs and Dynkin DiagramsOrthogonal [...]

    Pingback by Construction of A-Series Root Systems « The Unapologetic Mathematician | March 2, 2010 | Reply

  36. [...] go in a completely different direction! I want to talk about the representation theory of permutation groups. Now at least on the surface you might not think there’s a lot to say, but it’s a [...]

    Pingback by New Topic: The Representation Theory of the Symmetric Group « The Unapologetic Mathematician | September 7, 2010 | Reply

  37. [...] talking about symmetric groups, which are, of course, groups. We have various ways of writing down an element of , including the [...]

    Pingback by Some Review « The Unapologetic Mathematician | September 8, 2010 | Reply

  38. [...] one we’ve seen is the signum representation of a permutation group, which sends even permutations to and odd permutations to [...]

    Pingback by Some Sample Representations « The Unapologetic Mathematician | September 13, 2010 | Reply

  39. [...] a lot about the general theory of finite group representations. But our goal is to talk about symmetric groups in particular. Now, we’ve seen that the character table of a finite group is square, meaning [...]

    Pingback by The Road Forward « The Unapologetic Mathematician | December 7, 2010 | Reply

  40. It’s been crystal clear until you mentioned the right-left permutation. From “We can even use this notation for compositions, reading the permutations from right to left. —> See if you can get this result” What does this refer to? If fg and gf (i prefer to call them gof and fog like l->r functions but no worries) respectively =
    (1234) (1234)
    (3124) (2431)
    I don’t quite see how either becomes (12)(34)(143) as you pointed out in right to left reading :s. How does this work and what’s the difference in l-r from r-l.

    Comment by Shamel | December 20, 2010 | Reply

  41. Ok i’m getting something. when you mention the fg or gf you’re actually referring to the “functions” individually say f(abc) then g(abc) or vice versa…

    Comment by Shamel | December 20, 2010 | Reply

  42. This was great!! Now my last and final problem is breaking long cycles into swaps… Not making sense yet will write some stuff and see what i can make sense of. If anyone understands that please be so kind as to share :). Thanks–

    Comment by Shamel | December 20, 2010 | Reply

    • To break a long cycle down, swap the elements one at a time with the first element.

      Comment by John Armstrong | December 21, 2010 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 366 other followers

%d bloggers like this: