Can someone explain the algorithm for composition of cycles?

Question

Let $\sigma=(1\ 3),\ \tau=(2\ 4\ 5),\ \pi=(2\ 3\ 4) \in S_{5}$. Find $\pi\circ\tau\circ\sigma$.

I know the solution is $(1\ 4\ 5\ 3)$.

What i'm doing now is writing the permutations in the "expanded" form,

for example $\tau=\begin{pmatrix} 1\ 2\ 3\ 4\ 5\\ 1\ 5\ 3\ 2\ 4 \end{pmatrix}$,

and then "follow the numbers" over the composition. This way, i find $(1\ 3\ 5\ 2)$, which is incorrect. What am i doing wrong?

Answer 1

When you read a composition of functions written in the usual notation for permutations, you must remember to read them from right to left. Thus, when you try to compute the composition you must start by looking successively at what does each permutation in the composition do to each integer from $1$ to $5$ (in this case), but from right to left.

So you can start by writing $$\pi \circ \tau \circ \sigma = \begin{pmatrix} 2 &3 &4 \end{pmatrix} \circ \begin{pmatrix} 2 &4 &5 \end{pmatrix} \circ \begin{pmatrix} 1 &3 \end{pmatrix}$$

So you start with $1$. The rightmost permutation sends $1 \mapsto 3 $ and then the middle permutation sends $3 \mapsto 3$ and finally the leftmost permutation sends $3 \mapsto 4$. So in the end the total result is that the composition of the three of them sends $1 \mapsto 4$. In the same way you'll proceed for the other integers and in the end you'll get the answer

$$ \pi \circ \tau \circ \sigma = \begin{pmatrix} 1 &2 &3 &4 &5 \\ 4 &2 &1 &5 &3 \end{pmatrix}$$ or in cycle notation $\pi \circ \tau \circ \sigma = \begin{pmatrix} 1 &4 &5 &3\end{pmatrix}$.

I checked doing the computation from left to right and the "answer" I got from doing that was $\pi \circ \tau \circ \sigma = \begin{pmatrix} 1 &3 &5 &2\end{pmatrix}$ which is what you originally had as your answer.

Answer 2

You're probably composing from the left to the right, instead of from the right to the left.

Answer 3

Starting with your original problem:

$$\pi\circ\tau\circ\sigma = (234)\circ(13)\circ(245)$$

Note that the first two cycles (on the left) share only one element: 3. By looking at the action that cycles of this sort have on the set $\\{1,2,3,4,5\\}$, you can prove the first composition (on the left) can be reduced to:

$$(234)\circ(13) = (423)\circ(31) = (4231) = (1423)$$

Substituting this back:

$$\pi\circ\tau\circ\sigma = (1423)\circ(245)$$

By examining the action of the cycles on the set, you can show that the inverse of this is just the reverse operation:

$$(1423) = (3142) = (314)\circ(42)$$

and

$$(245) = (24)\circ(45)$$

Substituting:

$$\pi\circ\tau\circ\sigma = (314)\circ(42)\circ(24)\circ(45)$$

Cycles of length 2 are self-adjoint, so $(42)\circ(24) = ()$. Substituting:

$$\pi\circ\tau\circ\sigma = (314)\circ(45)$$

These are two cycles that share a single element (4), so they can be combined:

$$(314)\circ(45) = (3145) = (1453)$$

Substituting this back:

$$\pi\circ\tau\circ\sigma = (1453)$$

which is your result.