2

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$?

Community
  • 1
Altar Ego
  • 5,282
  • note: it should read ${(i$ $i+1) | 1\leq i \leq n-1}$ – Deven Ware Sep 21 '11 at 03:19
  • @Srivatsan Narayanan, I'm afraid that the significance of the conjugate in this context is lost on me. What is the immediate result of this? – Altar Ego Sep 21 '11 at 03:23
  • 1
    You have to worry only about transpositions, not all permutations explicitly, because transpositions generate the whole group. So as long as $(j \ k)$ is generated by those elements ${ (i \ i+1) }$ for all $j,k$, you are effectively done. – Srivatsan Sep 21 '11 at 03:28
  • @Sri: Please feel free to make this (or a beefed-up version of this) an answer. Thanks! – Altar Ego Sep 21 '11 at 03:30

1 Answers1

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 :-).

Srivatsan
  • 26,311