# Conjugacy in $S_n$ with composing permutations left to right vs. right to left

I realize there are two conventions for composing permutations.

Left to right: $$(1\ 2)(1\ 3) = (1\ 2\ 3)$$

Right to left: $$(1\ 2)(1\ 3) = (1\ 3\ 2)$$

Among others, Dummit and Foote and Contemporary Abstract Algebra (Gallian) use the right to left convention, while Handbook of Computational Group Theory (Holt), Sage, and GAP use the left to right convention.

Now, given permutations $$\sigma, \tau \in S_n$$, where $$\sigma = (\sigma_1\ \sigma_2 \ldots\ \sigma_n) \ldots$$ (in cycle notation), in the right to left convention we have the convenient fact that $$\tau \sigma \tau^{-1} = (\tau(\sigma_1)\ \tau(\sigma_2)\ \ldots\ \tau(\sigma_n) ) \ldots$$.

Proof: Observe that if $$\sigma(i) = j$$, then $$\tau \sigma \tau^{-1} (\tau(i)) = \tau(j)$$. Therefore if the ordered pair $$i, j$$ appears in the cycle decomposition of $$\sigma$$, then the ordered pair $$\tau(i), \tau(j)$$ appears in the cycle decomposition of $$\tau \sigma \tau^{-1}$$.

Now if you believe that, you can use a similar proof to obtain the ugly fact that in the left to right notation $$\tau \sigma \tau^{-1} = (\tau^{-1}(\sigma_1)\ \tau^{-1}(\sigma_2) \ldots\ \tau^{-1}(\sigma_n))\ldots$$

To me this makes the left to right convention inferior, because conjugation follows a less natural rule. Am I missing something? Are there other reasons to compose permutations from left to right that result in simpler algebraic laws? And if not, I am curious why we don't exclusively use right to left notation.

• Notationally I understand why both conventions exist, as you explain. However, algebraically are there reasons for left to right composition? I just showed an algebraic reason to prefer right to left. – Bryce Sandlund Aug 12 '15 at 13:32

Left-to-right is basically a by-product of western languages being scanned this way. The convention has groups acting (group actions are the raison-d-être for group theory) on the right, and the permutation product is a consequence.

If you have a group $$G$$ acting on a set $$\Omega$$, then $$\omega^{gh}=(\omega^g)^h$$ in left-to-right action, while when acting on the left we have at best that $$(gh)(\omega)=g(h(\omega))$$ (or in some convention even the perverse $$h(g(\omega))$$). For many group theorists (the use seems to differ between group theory and other areas) the first version is easier to write down, especially if the product gets longer.

A free bonus is that right action corresponds to row vectors, which are easier to typeset than column vectors.

In my (biased) view the main reasons for the right-to-left convention are the historical use in calculus (one writes $$\sin(a)$$, not $$a^{\sin}$$, even though the second use would be on many pocket calculators nowadays), as well as in Linear Algebra textbooks that tend to write equation systems universally as $$Ax=b$$, not $$xA=b$$.

• Appreciate the insight. It makes sense when you use group actions to have $\omega^{gh} = (\omega^{g})^h$. – Bryce Sandlund Aug 12 '15 at 19:15

The "ugly" formula $\tau \sigma \tau^{-1} = (\tau^{-1}(\sigma_1)\ \tau^{-1}(\sigma_2) \ldots\ \tau^{-1}(\sigma_n))$ can be easily rewritten in the form $\tau^{-1} \sigma \tau = (\tau(\sigma_1)\ \tau(\sigma_2) \ldots\ \tau(\sigma_n))$, using the bijection $\tau^{-1}\mapsto \tau$. So I would not say that the left to right convention is "inferior". Each of the conventions has certain advantages which depend on the context. In an abstract group $G$ the words are usually given by $w=a_1^{e_1}\cdots a_r^{e_r}$ from left to right, but if the elements are maps, it seems sometimes better to use the right to left convention in order to have $(fg)(x)=f(g(x))$.

• Thanks for the comment. The problem I noticed is that $\tau^{-1} \sigma \tau$ is not $\sigma$ conjugated by $\tau$, whereas $\tau \sigma \tau^{-1}$ is. I do agree that both notations have advantages at times though. – Bryce Sandlund Aug 12 '15 at 19:14
• I do not think so. $\sigma$ is conjugated by $\tau$ either means $\tau^{-1}\sigma\tau$, or $\tau\sigma\tau^{-1}$, depending on the conventions "right to left", or "left to right". Both things are equivalent, of course. – Dietrich Burde Aug 12 '15 at 19:22
• You're right. My understanding was false. – Bryce Sandlund Jan 29 '16 at 1:47