2
$\begingroup$

Related to this question and this answer (to a different question) is the following, from Dummit & Foote $\S$ 3.5 # 3.

Prove that $S_n$ is generated by $\left \{ (i \ \ \ i+ 1)| 1 \leq i \leq n - 1 \right \}$ [Consider conjugates, viz. $(2 \ \ 3)(1 \ \ 2)(2 \ \ 3)^{-1}$ ]

The book claims that any permutation is a product of transpositions (without proof, but I can find that through the linked pages), and I think I am supposed to use that, but the hint is confusing me. Isn't $(2 \ \ 3)^{-1}$ just equal to $(2 \ \ 3)$ itself? Here is the proof linked to in the answer above:

Since, for $1 \leq j < k < n$ we have $(j \ \ k + 1) = (k \ \ k+1)(j \ \ k)(k \ \ k+1)$, ...
($S_n = $ the group generated y transposing adjacent points)

Is this sufficient? Don't we need to explicitly look at $\sigma \in S_n$?

  • 0
    @Sri: Please feel free to make this (or a beefed-up version of this) an answer. Thanks!2011-09-21

1 Answers 1

3

A transposition is just a $2$-cycle in $S_n$, i.e, $(j \ \ k)$ for some $1 \leq j < k \leq n$. The transpositions $\{ (i \ \ i+1) \}$ are also sometimes called simple transpositions. It's a standard theorem that the set $T$ of transpositions generate the whole group $S_n$. This exercise asks you to show that $S_n$ is also generated by the simple transpositions (which is a strict subset of $T$).

Indeed it seems that one has to show that every $\sigma \in S_n$ can be written as a product of simple transpositions. However, one need not worry about all $\sigma \in S_n$ explicitly. Noting that $T$ generates the group, it is sufficient to establish the result for every $\sigma \in T$. And, that's how the solution proceeds as well.

Tidbit. The bubble sort algorithm can be viewed as basically writing a given permutation as a product of simple transpositions, even if it is not usually phrased this way. You may think of it as a constructive proof of this result.


As for the notation $(2 \ \ 3)^{-1}$ instead of $(2\ \ 3)$ in the hint, I just think the author wants to convey the fact that $(2 \ \ 3) (1 \ \ 2) (2 \ \ 3)^{-1}$ is a conjugate of $(1\ \ 2)$. Why the notion of "conjugate" is useful for the problem is a different question; I do not want to reveal that here since I don't want to spoil the fun for the OP :-).

  • 0
    Ok. I will accept an answer later, but possibly before I receive my *Masters of Transpositions* degree! :)2011-09-21