55
$\begingroup$

I didn't find any good explanation how to perform multiplication on permutation group written in cyclic notation. For example, if $$ a=(1\,3\,5\,2),\quad b=(2\,5\,6),\quad c=(1\,6\,3\,4), $$ then why does $ab=(1\,3\,5\,6)$ and $ac=(1\,6\,5\,2)(3\,4)$?

$\endgroup$
2
  • 2
    $\begingroup$ In what order do you compose permutations? $\endgroup$
    – lhf
    Apr 8, 2011 at 16:31
  • $\begingroup$ This question may be of help, if it is not a duplicate in some sense already =) $\endgroup$ Apr 8, 2011 at 16:41

4 Answers 4

108
$\begingroup$

You are thinking of the permutations as functions, so when you write "$ab$", you mean that you perform the permutation $b$ first, and the permutation $a$ second.

Here's one way to do it: write the disjoint cycle expressions for both $a$ and $b$, in the given order: $$(1,3,5,2)(2,5,6)$$ Now, moving from right to left, see what happens to each number in each cycle.

For instance, start with $1$, so we write $1$ down: $$(1,$$ The first cycle, $(2,5,6)$, does nothing to $1$, so it stays $1$. Then the next cycle, $(1,3,5,2)$, sends $1$ to $3$. So, in total, $1$ is sent to $3$. We write $$(1,3,$$ Now consider $3$. The first cycle, $(2,5,6)$, does nothing to $3$. The second maps $3$ to $5$. So the product maps $3$ to $5$. So now we have $$(1,3,5,$$ Now $5$. The first cycle, $(2,5,6)$, sends $5$ to $6$; the second cycle does nothing to $6$, so in total, $5$ is sent to $6$. So for the product we now have $$(1,3,5,6,$$ Next, what happens to $6$? The first cycle sends $6$ to $2$; and then the next cycle sends $2$ to $1$. So $6$ is sent to $1$, and because we started out with $1$, this now closes the cycle we have; thus, we also close the bracket. So the product so far is $$(1,3,5,6)$$ Now we consider the "next" number that hasn't been described yet, $2$. The first cycle, $(2,5,6)$, sends $2$ to $5$; then we check what the next cycle does to $5$, which is that it sends it back to $2$. So $2$ maps to $2$, and since we started out with $2$, it again closes the cycle. So now we have $$(1,3,5,6)(2)$$ Finally we check what happens $4$, as it's the remaining number: $(2,5,6)$ fixes $4$ (it doesn't do anything to it – it remains as it is), as does $(1,3,5,2)$, so $4$ is overall fixed. So now finally we have: $$ab = (1,3,5,2)(2,5,6)=(1,3,5,6)(2)(4) = (1,3,5,6)$$ $$\therefore (1,3,5,2)(2,5,6)=(1,3,5,6)$$

It's similar with $ac$. Here we have: $$(1,3,5,2)(1,6,3,4).$$ First consider $1$: the first cycle maps it to $6$, the second cycle fixes $6$. So $1\mapsto 6$. Then $6$ is sent to $3$ by the first cycle, and $3$ to $5$ by the second cycle (reading right to left, remember), so $6\mapsto 5$. Then $5$ is fixed by the first cycle and sent to $2$ by the second cycle, so $5\mapsto 2$. Then $2$ is fixed by the first cycle and sent to $1$ by the second, which means $2\mapsto 1$, closing the cycle: we have $(1,6,5,2)$. The next number not already covered is $3$; $3$ is mapped to $4$ by the first cycle (by $b$), and $4$ is fixed by $a$, so $3\mapsto 4$. Then $4$ is sent to $1$ by the first cycle, and $1$ is sent to $3$ by the second cycle, so this closes this second cycle as $(3,4)$. Putting the two together we get $$(1,3,5,2)(1,6,3,4) = (1,6,5,2)(3,4)$$ as given.

$\endgroup$
3
  • $\begingroup$ Good explanation. $\endgroup$
    – Ken Ingram
    Dec 30, 2018 at 8:12
  • $\begingroup$ @math.stackexchange.com/users/742/arturo-magidin Since 1 is sent to 3, why are you writing (1,3,..)? Shouldn't it be just (3,...)? $\endgroup$ Sep 24, 2023 at 13:28
  • $\begingroup$ @AninditaSarkar I'm using cycle notation, not one-line representation. So, no. It shouldn't be that. If you do not know cycle notation, you shouldn't even be reading this. $\endgroup$ Sep 24, 2023 at 17:37
24
$\begingroup$

The method I use for multiplying permutations like this is to think of each cycle as a set of mappings. a (in your example) maps 1 to 3, 3 to 5, 5 to 2, and 2 to 1. Also, remember that ab means "apply b, then apply a." So, here, we want to see where ab maps each number 1-6.

Start with 1: b fixes 1 (maps it to itself) and a maps 1 to 3. So we can begin writing ab = (13...

Now do 3: b fixes 3, and a maps 3 to 5. Put a 5 in: ab = (135...

Now 5: b maps 5 to 6 and a fixes 6, so ab = (1356...

Now 6: b maps 6 to 2 and a maps 2 to 1, so ab = (13561... = (1356).

Notice that ab fixes 4 since both a and b fix 4, but ab actually also fixes 2. This is because b maps 2 to 5, and a maps 5 right back to 2.

Hopefully you can use this method to check the other products.

$\endgroup$
0
5
$\begingroup$

There is a small example on this page . Basically multiplication of permutation groups is applying permutations from right to left on an unaltered sequence.

$\endgroup$
1
  • 2
    $\begingroup$ Thanks. The blog isn’t exactly clear either but gave me the hints that Fraleigh was too lazy to spell out in 9.10. $\endgroup$
    – Alper
    Jan 14, 2023 at 8:41
2
$\begingroup$

I didn't find this method written as an answer here, so I am just adding it.

You might convert these cyclic notations to Cauchy's two-line notations. Carefully observing your $a$ and $b$, the permutation groups can be written in the following form: $$a= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 3 & 1 & 5 & 4 & 2 & 6 \end{pmatrix} \\ b= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 1 & 5 & 3 & 4 & 6 & 2 \end{pmatrix} $$

Now, under the multiplication operation, we will have: $$a\cdot b= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 3 & 1 & 5 & 4 & 2 & 6 \end{pmatrix} \cdot \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 1 & 5 & 3 & 4 & 6 & 2 \end{pmatrix} $$

As @Arturo explained in his answer, "you perform the permutation in $b$ first and then in $a$".

So, in $b$, $1\to1$ and then in $a$, $1\to3$. Thus, in $a\cdot b$, $1\to3$.

Similarly, in $b$, $2\to5$ and then in $a$, $5\to2$. Thus, in $a\cdot b$, $2\to2$ itself. Continuing in a similar process, you'll find that $$a\cdot b= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 3 & 2 & 5 & 4 & 6 & 1 \end{pmatrix}$$

Now convert this final form to the cyclic form. Note that we have, in $a\cdot b$, $1\to3$. Thus $$(1,3$$

Again, $3\to5$. Thus $$(1,3,5$$

Note again that $5\to6$ and $6\to1$, making our cyclic notation as $$\left(1,3,5,6\right)$$

Also, note that the rest of the elements in the group map to themselves. Thus we can ignore their presence in our cyclic notation. This makes $$a\cdot b=\left(1,3,5,6\right)$$

Now can you similarly proceed for $a\cdot c$ also?

$\endgroup$
2
  • 1
    $\begingroup$ This is very clear. Thank you. $\endgroup$
    – Alper
    Jan 14, 2023 at 8:43
  • $\begingroup$ wonderful answer for newbies. $\endgroup$
    – zzzgoo
    Aug 9, 2023 at 6:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .