# Can someone explain the algorithm for composition of cycles?

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?

• since permutations are generally not commutative, you should be careful about what conventions you follow, in this case its first do \sgima, then \tau and then \pi Dec 27, 2010 at 20:02
• I had to do about a thousand of these in abstract algebra, and the way that worked best for me was to do each digit and think about where it went. So I'd start with 1, and then (for your example) I'd say, "okay, where does sigma take 1...okay, where does tau take that..." and so on. So, if I had something like (12)(13) and I'd want to see what that was, I'd say, "Well, 1 goes to 3 in (13), then 3 goes to itself under (12). So far I have (...13...) as my solution. Then 2 goes to itself in (13) and then to 1 in (12). So I have (...213...) as my solution. But this is it, so it's (213)."
– user2959
Dec 27, 2010 at 22:15

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.

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

• This is easy to check, and in fact turns out to be the case :-) Dec 27, 2010 at 20:06
• no, i'm composing from right to left, sigma, then tau, then pi. EDIT -- nope!, wait, you were right. ahah! thank you:) Dec 27, 2010 at 20:07

$$\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)$$