Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
note: it should read $\{(i$ $i+1) | 1\leq i \leq n-1\}$ –  Deven Ware Sep 21 '11 at 3:19
    
Thanks @Deven.. –  Altar Ego Sep 21 '11 at 3:22
    
@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 3: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 3:28
    
@Sri: Please feel free to make this (or a beefed-up version of this) an answer. Thanks! –  Altar Ego Sep 21 '11 at 3:30

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
Oh no, I'm definitely confused about the hint itself! Thanks for this. –  Altar Ego Sep 21 '11 at 3:58
    
Ok. I will accept an answer later, but possibly before I receive my Masters of Transpositions degree! :) –  Altar Ego Sep 21 '11 at 4:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.