11
$\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 fist 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?

$\endgroup$
  • 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 Dec 9 '13 at 11:09
  • 2
    $\begingroup$ Questions that are opinion polls must, according to MO culture, be wikified, which I have done. $\endgroup$ – Todd Trimble Dec 9 '13 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 Dec 9 '13 at 15:36
  • 1
    $\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 Dec 9 '13 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 Dec 9 '13 at 22:52
7
$\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.

$\endgroup$
  • 1
    $\begingroup$ "widely used standard." No doubt that is true for group theorists, not sure about the rest of us. $\endgroup$ – Chris Wuthrich Dec 9 '13 at 13:55
  • 1
    $\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 Dec 9 '13 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 Dec 9 '13 at 17:21
  • 2
    $\begingroup$ I love the words "somewhat widely used standard". $\endgroup$ – darij grinberg Dec 9 '13 at 19:25
  • 1
    $\begingroup$ @StefanKohl I appreciated your comment, not least because I have had referees say that "most people" use the other convention:) As I grew up using gap perhaps this explains my own preference! $\endgroup$ – Andrew Dec 10 '13 at 8:38
5
$\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.

$\endgroup$
  • $\begingroup$ Put a picture please. $\endgroup$ – Patrick I-Z Dec 9 '13 at 19:38
  • $\begingroup$ Your pictures actually look like a visualization of the Artin braid group. $\endgroup$ – Peter Mueller Dec 10 '13 at 10:28
4
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.