6  Generators

In Theorem 5.1 we saw that every cycle and hence every permutation can be written as a product of adjacent swaps: $(12),(23),(34),\dots ,(n-1,n)$. Here we will identify some relations that hold among these generating elements.

Let us call ${\tau }_i=(i,i+1)$ the swap of $i$ and $i+1$.

6.1 Squaring relation

We have ${\tau }_i^2=1$ where $1$ represents the identity permutation (no shuffling). This says that if we swap $i$ and $i+1$ and then swap again, we get back to a sorted list.

6.2 Commutating

From Exercise 4.1, we saw that in general ${\pi }_1{\pi }_2\ne {\pi }_2{\pi }_1$. Nonetheless, if we are swapping disjoint sets of pairs like $(12)$ followed by $(34)$ then there is no interaction between the swaps. So the order doesn’t matter: $(12)(34)=(34)(12)$. Specifically, ${\tau }_i$ and ${\tau }_j$ commute (${\tau }_i{\tau }_j={\tau }_j{\tau }_i$) provided $i$ and $j$ are at least $2$ apart.

B.<a,b,c> = BraidGroup(4)
plot(a * c)

a * c == c * a

True

6.3 ABA = BAB

At the top of Section 5.2 we saw that $(12)(23)(12)=(13)$. We also have $(23)(12)(23)=(13)$. Compare the following pictures.

B.<a,b> = BraidGroup(3)
plot(a * b * a)
plot(b * a * b)

We can see visually that the middle green strand is sliding from one side of the blue/red crossing to the other.

6.4 Other relations?

It turns out, every way to simplify or manipulate products of transpositions can be reduced to exactly these three rules:

1. ${\tau }_i^2=1$
2. ${\tau }_i{\tau }_j={\tau }_j{\tau }_i$ for $|i-j|\ge 2$ (at least two apart)
3. ${\tau }_i{\tau }_{i+1}{\tau }_i={\tau }_{i+1}{\tau }_i{\tau }_{i+1}$

The proof of this has two stages. One which we have already seen. First, you show that every permutation can be written as a product of transpositions of adjacent elements (Theorem 5.1). This shows that you can use ${\tau }_1,\dots ,{\tau }_n$ and these rules to write every element of $S_n$. I.e. the number of objects generated by these rules is at least $n!$.

The second step is showing that the number of objects generated by these rules is no more than $n!$ so that it is exactly the same as $S_n$. This requires more tools than we have available to us (i.e. group theory). A proof for those in-the-know may be found here for instance.

We will take it as a fact that these rules describe $S_n$ exactly.