15
$\begingroup$

I'd like to know how people prefer to write permutations, or elements of the symmetric group $S_n$ for $n\ge0$.

The most natural way to define a permutation in $S_n$ is as a bijection on the set $\{1,2,....,n\}$. Then the set of permutations (bijections) becomes a group under composition of maps. If $f,g\in S_n$ then there are two ways to define the composition $f\circ g$ depending on whether our functions act from the left or the right: $$(x)(f\circ g) = ((x)f)g\quad\text{and}\quad (f\circ g)(x)=f(g(x)).$$ I think that the latter is by far the most common these days. Of course, in the first case I could just define $(f\circ g)(x)=g(f(x))$ but it really is a right action so it should be written this way.

In terms of multiplying permutations using cycle notation the two ways of writing composition correspond, respectively, to whether we read the cycles left-to-right or right-to-left. For example: $$(1,2)(2,3) = \begin{cases} (3,2,1), &\text{using the $(x)f$ convention},\\ (1,2,3), &\text{using the $f(x)$ convention}. \end{cases}$$

To me it has always seemed more natural to read permutations from left-to-right, as in the first case, but this implicitly uses the less common convention for composition of maps.

So the question: do you prefer to read products of permutations, written as cycles, from left-to-right or right-to-left?

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ I prefer the second. The trick is to write a map from the right to left so instead of writing $f\colon A\to B$ I write $f\colon B\leftarrow A$ or even $B\leftarrow A:f$ (actually I put the $f$ on the arrow), then the composition gets easy. $\endgroup$
    – Marcel Bischoff
    Commented Dec 9, 2013 at 11:09
  • 3
    $\begingroup$ Questions that are opinion polls must, according to MO culture, be wikified, which I have done. $\endgroup$
    – Todd Trimble
    Commented Dec 9, 2013 at 11:57
  • 2
    $\begingroup$ I know this is not exactly what you were asking, but combinatorialists tend to use one-line notation when writing permutations. $\endgroup$
    – Sam Hopkins
    Commented Dec 9, 2013 at 15:36
  • 2
    $\begingroup$ This has been the subject of a long discussion on sage-devel lately ( groups.google.com/forum/#!msg/sage-devel/tAAb42Edh9o/… ) -- or is that where you're coming from, Andrew? In my humble opinion, the worst notation is unclarified notation, so whatever you are publishing, please be explicit about what notation you are using! $\endgroup$
    – darij grinberg
    Commented Dec 9, 2013 at 19:17
  • 1
    $\begingroup$ I would have thought (x)(fog) = g((x)f) would be written (x)(fog) = ((x)f)g. ??? $\endgroup$
    – roy smith
    Commented Dec 9, 2013 at 22:52

5 Answers 5

Reset to default
9
$\begingroup$

The GAP convention is to multiply permutations from the left to the right, i.e. $(1,2) \cdot (1,3) = (1,2,3)$, to write down each cycle with the smallest moved point first and to sort cycles in ascending order w.r.t. their smallest moved points. I think meanwhile this convention is a somewhat widely used standard.

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ "widely used standard." No doubt that is true for group theorists, not sure about the rest of us. $\endgroup$
    – Chris Wuthrich
    Commented Dec 9, 2013 at 13:55
  • 1
    $\begingroup$ Even group theorists would like to kick someone's butt sometimes for introducing this stupid convention into GAP. I've literally spend weeks to find unnecessary errors in my GAP code because of this. This is one of the more serious design flaws in the GAP system in my opinion. $\endgroup$
    – Johannes Hahn
    Commented Dec 9, 2013 at 16:02
  • 2
    $\begingroup$ @JohannesHahn: Really? -- That's interesting ... . To me, multiplying permutations from the left to the right seems and always seemed to be the most natural thing, since one also reads from the left to the right, and not the other way round. I don't remember seeing many complaints on this to GAP Support or on the GAP Forum. $\endgroup$
    – Stefan Kohl ♦
    Commented Dec 9, 2013 at 16:53
  • 2
    $\begingroup$ @Johannes Hahn: Also magma uses this convention. As the actual notation (in gap and magma) for applying the permutation $g$ to the element $a$ is $a\hat{}g$, there is no way to confuse this with a left action. There is a serious source of confusion in sage though: Internally they use a right action, but the notation is $g(a)$. So in general $g(h(a))\ne (g*h)(a)$. $\endgroup$
    – Peter Mueller
    Commented Dec 9, 2013 at 17:21
  • 4
    $\begingroup$ I love the words "somewhat widely used standard". $\endgroup$
    – darij grinberg
    Commented Dec 9, 2013 at 19:25
8
$\begingroup$

enter image description hereI draw permutations in TikZ. Compose permutations by drawing the permutation pictures beside each other: enter image description here. Invert by reversing the arrows. Of course there is more data in these pictures than just a permutation, but students understand the pictures immediately.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ Your pictures actually look like a visualization of the Artin braid group. $\endgroup$
    – Peter Mueller
    Commented Dec 10, 2013 at 10:28
5
$\begingroup$

For a topologist considering representations of the fundamental group of a space to a symmetric group, it is very helpful to multiply permutations from left to right, since it is natural to interpret path concatenation, which defines the group operation in the fundamental group, by first doing the left-hand loop and then the right hand loop.

Improve this answer
$\endgroup$
3
$\begingroup$

I asked a well-known veteran of finite permutation group theory what specialists in that field did. The answer was that "almost everyone" does it left to right. That is, if $g,h$ are permutations, then $gh$ means "do $g$ then do $h$". Actions are usually written using exponential notation: $x^g$ is the image of $x$ under $g$. The left-to-right convention means that $(x^g)^h=x^{gh}$. As to why the convention is like it is, the widespread influence of Wielandt's book Finite Permutation Groups was proposed as one reason.

Improve this answer
$\endgroup$
1
$\begingroup$

This is something that greatly annoys me, so I tend to use the following rule:

Does this make sense if permutations are replaced by permutation matrices?

Thus, I follow the convention of matrix multiplication, where I almost always act on vectors on the left side.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ +1, yet does “act on vectors on the left” mean the matrix or vector is on the left ;-)? (It’s just hopeless.) $\endgroup$
    – Francois Ziegler
    Commented Feb 3, 2020 at 6:59
  • $\begingroup$ I agree in the sense that the two different conventions naturally lead one to look either left actions or right actions. It is partly for this reason that Gordon James' classic Springer book on the representation theory of the symmetric group considers right modules. $\endgroup$
    – Andrew
    Commented Feb 3, 2020 at 9:16

You must log in to answer this question.

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