1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Permutation mapping

  1. Jan 2, 2009 #1
    hi
    if P and Q are 2 permutations of X, their product, P.Q, is the permutation of X (X=1,2,3,4,5), obtained by following the mapping Q with the mapping P. if Q=2 3 4 1 5, and P is 1 2 5 3 4, then how do i find P.Q and Q.P ?

    i have tried a few mappings but can never get the same answer as in the book :)

    answer for P.Q is 2 5 3 1 4
    answer for Q.P is 2 3 5 4 1

    please can anyone explain the steps.
    thanks
     
  2. jcsd
  3. Jan 2, 2009 #2
    "Q=2 3 4 1 5" means that this mapping happens:

    [tex]
    \begin{tabular}{ | c | c | c | c | c | }
    \hline
    1 & 2 & 3 & 4 & 5 \\
    \Downarrow & \Downarrow & \Downarrow & \Downarrow & \Downarrow \\
    2 & 3 & 4 & 1 & 5 \\ \hline
    \end{tabular}
    [/tex]

    In other words:

    1 gets mapped to 2,
    2 gets mapped to 3,

    And so on.

    Similarly, "P=1 2 5 3 4" means this happens:

    [tex]
    \begin{tabular}{ | c | c | c | c | c | }
    \hline
    1 & 2 & 3 & 4 & 5 \\
    \Downarrow & \Downarrow & \Downarrow & \Downarrow & \Downarrow \\
    1 & 2 & 5 & 3 & 4 \\ \hline
    \end{tabular}
    [/tex]

    That is,

    1 gets mapped to 1,
    2 gets mapped to 2,
    3 gets mapped to 5,

    and so on.

    So to find the product P.Q, you want to build a table like the ones above by "following the arrows". So first you need to find out what 1 gets mapped to under the product P.Q. Whenever you have a product of permutations, you work from right to the left. So you start with Q. You know that Q maps 1 to 2. And then P maps 2 to 2. So the first entry of the table is 2.

    [tex]
    \begin{tabular}{ | c | c | c | c | c | }
    \hline
    1 & 2 & 3 & 4 & 5 \\
    \Downarrow & \Downarrow & \Downarrow & \Downarrow & \Downarrow \\
    2 & ? & ? & ? & ? \\ \hline
    \end{tabular}
    [/tex]

    Next, you want to find out what 2 gets mapped to. Q maps 2 to 3, and P maps 3 to 5. So the second entry is a 5.

    [tex]
    \begin{tabular}{ | c | c | c | c | c | }
    \hline
    1 & 2 & 3 & 4 & 5 \\
    \Downarrow & \Downarrow & \Downarrow & \Downarrow & \Downarrow \\
    2 & 5 & ? & ? & ? \\ \hline
    \end{tabular}
    [/tex]

    And so on.

    To find Q.P, perform the same process, but start with P.
     
  4. Jan 2, 2009 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Q= 2 3 4 1 5, if I understand your notation, would also be written
    [tex]\left(\begin{array}{ccccc}1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 1 & 5\end{array}\right)[/tex]
    and means that 1 is changed into 2, 2 is changed into 3, 3 is changed into 4, 4 is changed into 1, and 5 is changed into itself (remains the same). P= 1 2 5 3 4 is
    [tex]\left(\begin{array}{ccccc}1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 5 & 3 & 4\end{array}\right)[/tex]
    and means that 1 and 2 remain the same, 3 is changed into 5, 4 is changed into 3, and 5 is changed into 4. The standard convention is that Q.P means that P is applied first, then Q (but check with your teacher or text- that varies). So P leaves 1 along and then Q changes 1 to 2: together, 1 changes to 2. P leaves 2 alone and then Q changes 2 to 3: together, 2 changes to 3. P changes 3 to 5 and then Q leaves 5 alone: together, 3 changes to 5. P changes 4 to 3 and then Q changes 3 to 4: together 4 remains the same. P changes 5 to 4 and then Q changes 4 to 1: together 5 changes to 1. That is the permutation
    [tex]\left(\begin{array}{ccccc}1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 5 & 4 & 1\end{array}\right)[/tex]
    In your notation I think that would be 2 3 5 4 1.

    Similarly, P.Q means that we apply Q first. Q changes 1 to 2 and then P leaves 2 alone: together 1 changes to 2. Q changes 2 to 3 and then P changes 3 to 5: together 2 changes to 5. Q changes 3 to 4 and then P changes 4 to 3: together 3 stays the same. Q changes 4 to 1 and then P leaves one alone: together 4 changes to 1. Q leaves 5 alone and then P changes 5 to 4: together 5 changes to 4. That is
    [tex]\left(\begin{array}{ccccc}1 & 2 & 3 & 4 & 5 \\2 & 5 & 3 & 1 & 4\end{array}\right)[/tex]
    or, in your notation 2 5 3 1 4.

    Again check your text's convention on order. If what your text has reverses those two answer, it is using the other convention.
     
  5. Jan 2, 2009 #4

    radou

    User Avatar
    Homework Helper

    To add, a permutation is a function, and the term "product" of permutations is actually a composition of functions, i.e. if P and Q are permutations of X, then the product PQ is defined as P(Q(x)), where x is an element of X.
     
  6. Jan 2, 2009 #5
    thanks guys. i get it now :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Permutation mapping
  1. Multiplying permutations (Replies: 10)

  2. Permutation Group (Replies: 29)

Loading...