1

Each permutation in $S_n$ can be written as a product of inversions (not disjoint) $(1 2 3 4 5)=(1 5)(1 4)(1 3)(1 2)$

How do I "read" it? I first start we the right side $(1 2)$?

gbox
  • 12,867
  • Different books do things differently, but typically permutations "act on the left" and the usual function composition convention is followed, so that $(f \circ g)(x) = f(g(x))$. By that convention, here $1 \mapsto 2$, while $2 \mapsto 1 \mapsto 3$, and so on. – pjs36 Aug 19 '15 at 19:05
  • @pjs36 So If I start with $(12)$ it is $1\rightarrow 2$ how to I get to $2\rightarrow 1 \rightarrow 3$? – gbox Aug 19 '15 at 19:10

2 Answers2

2

Because we have that $S_n \cong \text{Aut}(\{1, \dots, n\})$, let $\{1, \dots, n\} = N$ we are basically understanding this group as all bijective functions $f: N \to N$, and multiplication of group elements is just composition of functions.

So you would do $(12)$ first which sends $2 \to 1$, then you do $(13)$ which sends $1 \to 3$ so chaining these together we get $2 \to 1 \to 3$ by composition, and since $3$ does not appear in any of the other cycles, this is it in terms of where this permutation sends $2$.

In general I have always found the following two or three tricks to be all you need to manipulate and multiply symmetric group elements:

  1. Note that $(ab) = (ba)$, or in general that any element is invariant under cyclic permutation: $(n_1n_2\dots n_m) = (n_mn_1n_2 \dots n_{m-1})$ and so on.
  2. If we have a composition $(n_1n_2\dots n_m)(p_1p_2\dots p_i)$ where $p_1 = n_m$ and $n_k \neq p_j$ for $k \neq m, j \neq 1$, then the resulting cycle is just $(n_1n_2\dots n_mp_2\dots p_i)$, this is fairly obvious when you think about the resulting function composition.

We can apply these two tips to reduce the right hand side of your expression to the left:

$(15)(14)(13)(12) = (51)(14)(13)(12) = (514)(13)(12) = (451)(13)(12) = (4513)(12) = (3451)(12) = (34512) = (12345)$

And in general we can break up $(n_1n_2\dots n_m) = (n_1n_2)(n_2n_3)\dots (n_{m-1}n_m)$ with the same rules.

Hope this helps!

Sempliner
  • 2,414
  • I guess your second rule supposes $p_1$ (or $n_m$) is the only element common to the two cycles? – Bernard Aug 19 '15 at 19:33
  • Yes of course, or what I have written does not make much sense. I'll make an edit. – Sempliner Aug 19 '15 at 19:35
  • Though it should be pointed out that by appropriately decomposing a cycle you should be able to multiply all elements with these rules. – Sempliner Aug 19 '15 at 19:39
1

Here's a picture, hopefully one worth a thousand words: enter image description here

Elements that are actually moved by a particular permutation have red lines, while the black vertical lines show an element being fixed by that permutation.

If you just start at the top and trace the path down, you can see where each of $1,2,3,4$ and $5$ get sent. For example, since $(1\ 2)$ acts first with $(1\ 3)$ next, we can see where $2$ gets sent: First $(1\ 2)$ sends $2$ to $1$, and then $(1\ 3)$ sends that $1$ to $3$ so that, overall, $2 \mapsto 3$ since $2 \mapsto 1$ by $(1\ 2)$ and then $1 \mapsto 3$ by $(1\ 3)$. After $(1\ 3)$ acts, the rest of the $2$-cycles leave $3$ alone.

Hopefully this picture will help you see how the composition works.

pjs36
  • 17,979
  • "First (1 2) sends 2 to 1, and then (1 3) sends that 1 to 3" I get it why we start with 2, it is the rightmost, which is 2 goes to 1, now the cycle is over? so we move left to (1 3), why don't we start with 3? – gbox Aug 19 '15 at 19:39
  • 1
    @gbox The cycle isn't over then, I was just illustrating how to figure out where each individual 'point' gets sent. When you start with $3$, you'll see that $$3 \overset{(12)}\mapsto 3 \overset{(13)}\mapsto 1 \overset{(14)}\mapsto 4 \overset{(15)}\mapsto 4,$$ hence $3 \overset{(12)(13)(14)(15)}\longmapsto 4$ overall. But again, you'd still need to fill out "the rest of the cycle" to reduce the product to $(1\ 2\ 3\ 4\ 5)$. – pjs36 Aug 19 '15 at 19:48