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

$\endgroup$
4
  • $\begingroup$ note: it should read $\{(i$ $i+1) | 1\leq i \leq n-1\}$ $\endgroup$
    – Deven Ware
    Commented Sep 21, 2011 at 3:19
  • $\begingroup$ @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? $\endgroup$
    – Altar Ego
    Commented Sep 21, 2011 at 3:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – Srivatsan
    Commented Sep 21, 2011 at 3:28
  • $\begingroup$ @Sri: Please feel free to make this (or a beefed-up version of this) an answer. Thanks! $\endgroup$
    – Altar Ego
    Commented Sep 21, 2011 at 3:30

1 Answer 1

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Oh no, I'm definitely confused about the hint itself! Thanks for this. $\endgroup$
    – Altar Ego
    Commented Sep 21, 2011 at 3:58
  • $\begingroup$ Ok. I will accept an answer later, but possibly before I receive my Masters of Transpositions degree! :) $\endgroup$
    – Altar Ego
    Commented Sep 21, 2011 at 4:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .