A transposition is a permutation of the form $\tau = (i\thinspace j) \in S_n$.

Let $\{ \tau_1, \dots, \tau_k \}$ be a set of distinct transpositions of $S_n$.

Will this set necessarily generate a group isomorphic to $S_k$?

  • 4
    $\begingroup$ Think as the transpositions as labelling some edges in a complete graph. They correspond to a subgraph of the complete graph. If this subgraph is connected, then the group is an $S_k$, and conversely. $\endgroup$ – Lord Shark the Unknown Mar 8 '18 at 12:35
  • $\begingroup$ Ok, so you are saying that the subgroups generated by transpositions are in fact direct products of (smaller) symmetric groups? $\endgroup$ – user353673 Mar 8 '18 at 12:37
  • 1
    $\begingroup$ Yes, they are such products. $\endgroup$ – Lord Shark the Unknown Mar 8 '18 at 12:38

Consider $(12)$ and $(34)$ in $S_4$. They two together generate a group isomorphic to the Klein $4$-group which is not isomorphic to $S_n$ for any $n$.

  • $\begingroup$ Excellent, thank you! $\endgroup$ – user353673 Mar 8 '18 at 12:22
  • $\begingroup$ You are welcome. $\endgroup$ – Levent Mar 8 '18 at 12:22

No, in general you need special transpositions to work. For example, the $k-1$ tranpositions $$ (12),(13),\ldots ,(1k) $$ generate $S_k$, as do the $k-1$ transpositions $$ (12),(23),\ldots ,(k-1,k). $$

  • $\begingroup$ I see, thanks. Perhaps a separate question, but can any subgroup of $S_n$ be generated by a set of transpositions? $\endgroup$ – user353673 Mar 8 '18 at 12:29
  • 2
    $\begingroup$ No, if a subgroup is generated by transpositions, then it must have even order. But for example $S_3$ has a subgroup of order $3$. $\endgroup$ – Levent Mar 8 '18 at 12:29
  • $\begingroup$ What about $(12),(13),(34)$ in $S_4$? They generate $S_4$, right? $\endgroup$ – Levent Mar 8 '18 at 12:31
  • $\begingroup$ @ user353673 All subgroups generated by transpositions are isomorphic to a product of symmetric groups. So your question boils to whether there are subgroups that aren't isomorphic to a product of symmetric groups. And the answer is "yes". For instance, the kth cyclic group is a subgroup for k<=n, and if k > 2, this in not isomorphic to a product of symmetric groups. $\endgroup$ – Acccumulation Mar 8 '18 at 16:44
  • $\begingroup$ @Levent Yes, those aren't the only types of generating sets. But your set is actually equivalent to the second type of generating set that Dietrich Burde presented. Suppose I take your proposed transpositions and swap out 1 for 2, and vice versa. That is, I'm going to rewrite your transpositions, putting a 1 wherever I see a 2 in your transpositions, and a 2 wherever I see a 1. This results in (21), (23), (34), which is the same as (12), (23), (34). Since the labels are arbitrary, relabeling shouldn't change whether they generate the group. $\endgroup$ – Acccumulation Mar 8 '18 at 16:51

There are k(k-1)/2 transpositions in Sk, and therefore (k-1)(k-2)/2 transpositions in Sk-1. So it's possible to choose k transpositions from Sk-1. Since those transpositions are restricted to k-1 elements, there's no way they can generate a group on k elements (if k>3).

If all of this is too abstract, consider the digits (so n = 10). If we take a subset of five digits, there will be 10 transpositions of those digits:

01 02 03 04 12 13 14 23 24 34

It should be quite obvious that if we take k of these transpositions, they will generate a (possibly improper) subgroup of S5. So if k is, say, 6, then we have 6 transpositions that all lie in S5. There are only 5 elements that these 6 transpositions act on, so there's no way they can generate something isomorphic to S6.

It's possible to generate Sk with only k-1 transpositions. I believe that a necessary and sufficient condition for k-1 transpositions to generate Sk is that the transpositions be such that they can be ordered in such a way that each transposition other than the first one involves an element involved in a previous transposition and an element not involved in a previous transposition. For instance, for k = 6:

(01) first transposition can be anything we want

(12) 1 was used in a previous transposition, 2 was not

(23) 2 was previously used, 3 was not

(04) 0 was previously used, 4 was not

(15) 1 was previously used, 5 was not

Thus the transpositions (01),(12),(23),(04),(15) generate all permutations of {0,1,2,3,4,5}.

  • $\begingroup$ Another necessary and sufficient condition for the set of transpositions to generate $S_n$ is that for any partition of the set of objects being transposed into two non-empty sets $A$ and $B$, there must be at least one transposition in the set that exchanges a member of $A$ with a member of $B$. $\endgroup$ – Paul Sinclair Mar 8 '18 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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