Notices
Results 1 to 28 of 28

Thread: Permutation

  1. #1 Permutation 
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    I'm given the permutation


    on the set , and the inverse of that permutation,



    I just don't understand how that's the inverse. And actually, I'm not entirely sure of how to interpret the permutation anyway. Could someone explain this to me?


    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  2.  
     

  3. #2  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    There is no really easy way to explain this in words, so I suggest a pencil and paper for this.

    Your first "matrix" (but it isn't one really) says 1 goes to 2, 2 goes to 3 and 3 goes to 1, like in a cycle. The "tips" of the arrows you have drawn is the bottom row of your first "matrix".

    For the inverse, just reverse all arrows, as in (reading R to L) 3 goes to 2, 2 goes to 1 and 1 goes to 3, so the "tips" of your arrows is the bottom row on your second "matrix".

    Mathematics it is not, but a useful intuitional aid , I hope.


    Reply With Quote  
     

  4. #3  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Guitarist
    There is no really easy way to explain this in words, so I suggest a pencil and paper for this.

    Your first "matrix" (but it isn't one really) says 1 goes to 2, 3 goes to 3 and 3 goes to 1, like in a cycle. The "tips" of the arrows you have drawn is the bottom row of your first "matrix".

    For the inverse, just reverse all arrows, as in (reading R to L) 3 goes to 2, 2 goes to 1 and 1 goes to 3, so the "tips" of your arrows is the bottom row on your second "matrix".

    Mathematics it is not, but a useful intuitional aid , I hope.
    The only thing I disagree with is your last sentence. Your explanation is absolutely correct -- and it is indeed mathematics. You simply used the definitions and clearly illustrated their meaning -- that is good mathematics indeed.
    Reply With Quote  
     

  5. #4  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    I understand what you're saying...but I don't. I tried applying this step-wise to



    and it just didn't come out... I guess I need a mini lesson on permutations in general maybe? This is coming from the 'preliminaries' section of some abstract algebra material.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  6. #5  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    Maybe you should tell us what this "material" is, as, for some reason, it doesn't to be helping you very much.

    Mmmm... let's start with the set . The notation you have been using (which is fine for preliminaries, but somewhat cumbersome for routine use - see below) says that the upper row is your starting arrangement, the lower row is the arrangement you get after performing some permutation. So can you give a name to the last permutation you posted?

    Perhaps you have seen and are confused by the more standard succinct notation, say, is a permutation. At this point it may be helpful to distinguish between objects and "slots" (I defy Rocket, even at his most benign, to repeat his flattery here!).

    First notice we do not need to start with {1,2,3} - since sets are agnostic as to order, we can start anywhere, say {1,3,2}. So the notation (123) means that whatever slot is occupied by 2, replace it with 1, whatever slot is occupied by 3 replace it with 2, and whatever slot is occupied by 1, replace it with 3 (this was your above, if I recall).

    Using the Micky Mouse distinction between objects and slots, can you tell me how many permutations there are on 3 unordered objects? To avoid the urge to impose an order on things like 1, 2, and 3, think of coloured balls.

    Here's a hint (!)
    Reply With Quote  
     

  7. #6 Re: Permutation 
    Suspended
    Join Date
    Apr 2008
    Posts
    2,176
    Quote Originally Posted by Chemboy
    I'm given the permutation


    on the set , and the inverse of that permutation,



    I just don't understand how that's the inverse. And actually, I'm not entirely sure of how to interpret the permutation anyway. Could someone explain this to me?

    In my day, there was no exponent -1. In fact there was no negative exponents. If we wanted a negative exponent we would write 110^2 that would equal 0.01 the way I learned it. There was no exponent 1 either in my day, at least where I learned math.

    Sincerely,


    William McCormick
    Reply With Quote  
     

  8. #7  
    Forum Bachelors Degree
    Join Date
    Mar 2009
    Posts
    421
    The way I read these things is:

    "1 gets sent to 2"

    "2 gets sent to 3"

    "3 gets sent to 1"

    So the inverse should send 2 back to 1, 3 back to 2, and 1 back to 3. In other words, the inverse is

    "1 goes to 3"

    "2 goes to 1"

    "3 goes to 2"

    As for the last comment about inverses, all I can say is "?"
    Reply With Quote  
     

  9. #8  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Quote Originally Posted by Chemboy
    I understand what you're saying...but I don't. I tried applying this step-wise to



    and it just didn't come out... I guess I need a mini lesson on permutations in general maybe? This is coming from the 'preliminaries' section of some abstract algebra material.
    I'd also like to point out that this example is the identity permutation on three elements. That is, it just sends each to itself. Once you think about that and the definition of inverse, it becomes fairly obvious that it's its own inverse. So if you were confused by getting the same thing back, don't be. It was the right answer.
    Reply With Quote  
     

  10. #9  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    Oh naughty MagiMaster! That was set as a mini-exercise. Bad boy.

    Anyway, let's continue here for a while, for two reasons: it is an interesting subject in its own right, and it also has many very important applications.

    I will stick with my compact notation, where . Let's call this permutation as .

    Applying this to the set I have

    Applying to this set I have

    Applying to this set I have , which is, of course where we started. This suggests there may be a permutation which will "cancel"

    Then it's easy to figure out: starting at we want . So that the "do nothing", or identity, permutation.

    (note it is customary here to work R to L in composing permutations).

    So we have an object called a permutation, an inverse and an identity. If we can convince ourselves that there is a closed operation on permutations we will have a group. I have already hinted at what that might be......
    Reply With Quote  
     

  11. #10  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    ok, I think I've got it now. I was looking at it in terms of 'slots,' which I now know I shouldn't have been.

    So is it safe to say that

    ,

    or (correct? because it sends , , and ?)
    is the permutation, but is not necessarily the new order of the permuted objects. And also, as long as our is in the same order as it 'wraps around,' isn't there a number of ways we can right the same permutation? Because and both send , , and . Hopefully I have that right. Sorry I took a few days to get back here, got back into school on Monday.

    EDIT: Almost forgot your assignment. Yes, I know that will give the number of permutations on 3 different objects.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  12. #11  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    Quote Originally Posted by Chemboy

    ,

    or (correct? because it sends , , and ?) is the permutation
    Yes, good
    , but is not necessarily the new order of the permuted objects.
    Right, it depends where you start from
    isn't there a number of ways we can right the same permutation? Because and both send , , and .
    Yup, good thinking. In fact
    Yes, I know that will give the number of permutations on 3 different objects.
    Here's a nice way to look at it. Given 3 objects and 3 slots, for object 1 you have 3 choices of slot. Then for each and every such choice, there remain 2 empty slots for object 2. Likewise, for each and every choice for object 1 AND each and every choice for object 2, there remains just 1 vacant slot for object 3. This is just 3 x 2 x 1 = 6 possible arrangements for our objects.

    Here's something for you to ponder. How would you write the permutation ?

    I had toyed with the idea of introducing the groups of permutations (called symmetric groups) but decided against. They are most decidedly NOT the best introduction to group theory. Why? First because the elements of these groups are not "objects" like numbers, say - they are "operations", and second because they are, in general, non-abelian (which means a different order in which we perform the group operation on them determines a different outcome).

    But if you ever do get to group theory (and its applications), you will learn that groups with these properties are by far and away the most important. I fact, Dr. Cayley would probably have told you that the symmetric groups are the ONLY groups we need to know about!
    Reply With Quote  
     

  13. #12  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Quote Originally Posted by Guitarist
    Here's something for you to ponder. How would you write the permutation
    Would that be ?
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  14. #13  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    I have to say, that is a very nice try; it's not quite right, since we must have, inside our parentheses, 2 objects which exchange, So you might perhaps write , but why bother? says it all. Good shot, though.

    Question: is this (or is it not) one of the 6 unique permutations on our 3-element set?

    Supplementary: if so, what are the other 5? (Hint: the "do nothing" permutation is one of them)
    Reply With Quote  
     

  15. #14  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    ok, got it.

    I'll say it is one of the 6 unique permutations.

    One is the identity permutation (how do you write it in form?)

    Hmm... are they identity, , , , , and ?
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  16. #15  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Actually, I think I've seen it written as (12)(3) before. Mathworld agrees with me, but Wikipedia has it Guitarist's way. Personally, I like writing out the extra numbers since it distinguished (12)(3) from (12)(3)(4), which would otherwise just be written (12). Of course, sometimes the difference doesn't matter. Anyway, to answer Chemboy's question, you could write it as (1)(2)(3), or as (), but it's usually written ε.
    Reply With Quote  
     

  17. #16  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    Excellent stuff, well done.

    If you were sufficiently anal you might write the identity as but most people use either or . PS. Just overlapped with MagiMaster. Like my tutor always said "notation is arbitrary", so I shan't argue the point

    Notice the rather obvious fact that applying twice to any arrangement of 3 objects brings you back to where you started. That is . These are called "2-cycles" for this reason.

    Also we saw earlier that by applying thrice to any arrangement brings you back to where you started; the same is easily shown for , so these are called "3-cycles .

    Only fractionally less easy is to figure out is what happens when you apply two dissimilar 2-cycles in succession. See what happens when you reverse the order. Then try it with two dissimilar 3-cycles.

    PS Don't try all 36 pairs!!
    Reply With Quote  
     

  18. #17  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    This isn't coming as easily. Let's see here...

    Applying permutations is noncommutative, right?

    I noticed that (13)(23)=(132)... Maybe in general two 2-cycles can be written as a 3-cycle?

    What am I really supposed to be noticing?
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  19. #18  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    what do you mean by dissimilar 2-cycles Guitarist? I'm only curious, just for the sake of understanding all of this thread better.
    Wise men speak because they have something to say; Fools, because they have to say something.
    -Plato

    Reply With Quote  
     

  20. #19  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    You know what? "Dissimilar" was a stupid word to use; why didn't I just say "different"?

    Anyway, I meant things like (12)(13), (12)(23) etc

    Chemboy: I find your question hard to answer, as I'm not sure where you intended this thread to go. Specifically: are you interested in permutations as permutations, or are you interested in them as elements in a highly important non-abelian group?
    Reply With Quote  
     

  21. #20  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    More the latter. Though really, my original intention was just to understand the notation, which I now do. But I wasn't about to refuse anything you had to offer on the topic.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  22. #21  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    Umm, this doesn't help me a great deal, so here's the plan....
    I will show you the surprising Theorem of Cayley, and then stop boring you all.

    First we need some leg work. Recall first we had a set of permutations on a 3-element set, and found that for any pair of elements in , successive permutations are still a permutation, also that for each element in there is an inverse permutation, and further that there exists an identity permutation.

    This is sufficient to define as a group. It's called a symmetric group

    Sorry about this, but now we need a load of definitions (this will be heavily front-loaded so bear with me.....)

    the order of a group is simply the number of its elements - in the case of we saw the order to be ; this generalizes for any .

    if is an arbitrary group, a subgroup is simply a subset of the elements of where the group axioms hold. Obviously (and importantly in the present context) we require that .

    Suppose are groups, Let's call the result of applying the group operation, whatever it might be (arithmetic sum or multiplication, matrix multiplication, function composition....,) a product, and write for every case.

    The mapping as a mapping of the elements in to elements in (a function on sets) will be called a group homomorphism if products are preserved under this map, or, to put it another way, the image of products = the product of images. Symbolically: .

    A homomorphism is called an isomorphism if it is bijective - roughly speaking, if it has an inverse. Let me now give you sight of our quarry:

    Any arbitrary group of order n is isomorphic to a subgroup of the symmetric group

    This is the theorem of Cayley, but be sure you understand all of this before allowing me to proceed
    Reply With Quote  
     

  23. #22  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    yep, I understand it.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  24. #23  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    So, Cayley.

    Notice the rather obvious fact that, for the order of is grater than . This ensures that an arbitrary group of order cannot, in general, be isomorphic to itself.

    But we have a problem. Given a group , the task of finding all its subgroups is in general highly non-trivial. So let's ignore this difficulty for now, and be as precise as possible about what we mean by a group operation.

    First we require it to be closed. This means that for any . The converse is also true: given I can always find s.t. .

    The following statements are also true; given there is at least one and at most one such that . Likewise, given there is at least one and at most one such that .


    Let's elevate these facts to the status of a Theorem, cast in a way that will be of use to us:

    Let be of order . Then given the sequence all the elements of occur at least once and at most once in the sequence for any .

    Likewise, the elements of occur at least once and at most once in the sequence (these sequences need not be the same!)

    The consequence of this theorem should be clear on close reading, namely.....

    The sequence



    is simply a rearrangement of the sequence

    ,

    and the sequence



    is a rearrangement of the sequence

    ,

    which may be (but usually isn't) the original sequence



    No doubt you can see where this is headed!
    Reply With Quote  
     

  25. #24  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    I'm thinking each will correspond to a permutation, since it produces another within the group . So ultimately, will produce a permutation of the original .
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  26. #25  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    Chemboy: I typed this up last night, but as I was incompletely sober, I send it now, with the necessary corrections

    To your last statement, I cannot tell - either you are using your two indices in subtly different ways, or I have explained myself rather poorly. Let's assume the latter, and try to make amends.

    I introduce the symbol , it being clearly understood that this is an arbitrary element in the sequence

    Then my theorem says that each element of my group appears one and only once in the sequence .

    Anyway, slight change of plan; we are going to a worked example. We will work with groups of order 3. So, since the order of , we need to find a subgroup of order 3. I saud earlier this is not always easy, but in the present case we have already done the arithmetic.

    Recall that a subgroup needs an identity and an inverse. So we know that any 2-cycle is its own inverse, so there will be subgroups like etc. Self-evidently they are of order 2, so forget these babes.

    We also saw that are mutual inverses, so we have the subgroup which is of order 3. This will be our man.

    Select an arbitrary 3-order set, say . This can only be a group if the operation is addition and it is a cyclic group. While there is (obviously) a technical definition, for present purpose we can take this to mean "if the group operation forces you to exit stage right, re-enter stage left" This will become more clear in a mo.

    Let us add 0 to each of these elements. Wow! Nothing happens!

    Now let us add 1 to each. I get that , where by my "dramatic" analogy I must have that 1 +2 = 3 = 0. This is clearly a permutation; let's call it the permutation induced by the action of 1 on our set, and write accordingly.

    Now let's act 2 on our set; and call this permutation as Then using this notation, the action of 0 will be the permutation .

    Now let's write the action of these permutations in terms of a "map on slots". It is easy to see that , equally easy is that .

    Then it is obvious that there is a one-to-one correspondence between say and etc, so these are clearly bijections.

    It only remains to show that these are also homomorphisms, that is as an action on our group as a group operation on .

    But we already know this is true; in our group, 1 +2 = 3 =0, and we know that , so that .

    The demonstration of isomorphism is complete.

    Gosh, what a wind-bag I am......
    Reply With Quote  
     

  27. #26  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Quote Originally Posted by Guitarist
    Now let's write the action of these permutations in terms of a "map on slots". It is easy to see that , equally easy is that .
    Not so easy for me I'm afraid. I know it should make sense, but as it is I'm just not seeing it the right way.

    And this group we're working with, can I call it ?
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  28. #27  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    Well, adding 1 to our set maps the previous occupant of slot 1 onto the previous occupant of slot 2, the previous occupant of slot 2 to the previous occupant of slot 3 and so on.

    Yes, we were working with . Since arithmetic addition is the only group operation defined on the integers (no multiplicative inverses!), the plus sign is redundant.

    This is called a "quotient group"
    Reply With Quote  
     

  29. #28  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Well, adding 1 to our set maps the previous occupant of slot 1 onto the previous occupant of slot 2, the previous occupant of slot 2 to the previous occupant of slot 3 and so on.
    Got it.

    Yes, we were working with . Since arithmetic addition is the only group operation defined on the integers (no multiplicative inverses!), the plus sign is redundant.
    Ah, right. I wasn't thinking of that at the time.

    I understand the demonstration of being isomorphic to a subgroup of . Cool stuff.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •