I'm working on the following question, and honestly have no idea how to begin. Any hints would be greatly appreciated!

Let $H$ be a subgroup of $S_n$, the symmetry group of the set $\{1,2,\dots, n\}$. Show that if $H$ is transitive and if $H$ is generated by some set of transpositions, then $H=S_n$.


This might not be at the appropriate level for you, but I think this is a cute argument.

Suppose we wanted to transpose $1$ and $n$ in the list $1,\cdots,n$ but we were only allowed to swap adjacent numbers each step, how would we do it? Well, we could use adjacent transpositions to move $1$ all the way to the right, which would shift the numbers $2,\cdots,n$ each one left. Then we could move $n$ to the left with adjacent transpositions until we get the list $n,2,\cdots,n-1,1$.

In other words, we have

$$ (12)(23)\cdots(n-2\,n-1)\cdot(n\,n-1)\cdots(32)(21)=(n1). \tag{$\ast$} $$

(Remember, the rightmost permutations are applied to an input first. Interpret $(u\,v)$ as "swap the numbers that are $u$th and $v$th in the list.") We can use this...

Form a graph as follows: given a generating set $S$ of $H$ consisting of transpositions, let $\{1,\cdots,n\}$ be the vertex set and form an edge $(i,j)$ for every transposition $(ij)\in S$. The hypotheses that $H$ acts transitively and is generated by $S$ is equivalent to saying this graph is connected, so between any two values $a,b\in\{1,\cdots,n\}$ there is some sequence of transpositions

$$ (a_1\,a_2),(a_2\,a_3),\cdots,(a_{k-1}\,a_k)\in S $$

where $a_1=a$ and $a_k=b$. Then we can reuse the $(\ast)$ trick:

$$ (a_1\,a_2)(a_2\,a_3)\cdots(a_{k-2}\,a_{k-1})\cdot(a_k\,a_{k-1})\cdots(a_3\,a_2)(a_2\,a_1)=(a_k\,a_1)=(ab)\in H.$$

That is, $H$ contains every transposition $(ab)$, so it must be $S_n$.

  • $\begingroup$ I honestly don't follow. $\endgroup$ – mathgenesis22813 Nov 1 '16 at 2:27
  • 2
    $\begingroup$ @m2271r As I stated at the very beginning of my answer, I wasn't sure if this was written well for you specifically (it uses graph theory for instance). But if you're interested in engaging the argument, "I don't follow" is pretty much a useless comment since you don't specify any of the many things I said that you don't follow. If you're interested in engaging the argument, you might as well start by saying what is the very first part that you don't follow. Perhaps I can rephrase the argument later too. $\endgroup$ – arctic tern Nov 1 '16 at 2:39

Proof by induction on $n$. Case $n\le 2$ is trivial.

Let $X$ be the set of transpositions in $H$, $X_1$ the set of transpositions in $X$ fixing 1 and $K$ the subgroup generated by $X_1$.

We have to prove that $K$ is transitive on $\{2,\dots,n\}$. If true, induction hypothesis implies $K$ is the full symmetry group on $\{2,\dots,n\}$, and since $H$ properly contains $K$ which is a maximal subgroup in $S_n$, it's immediate to conclude.

So let's prove this transitivity claim on $K$. Otherwise $K$ has at least two orbits $I,J$ in $\{2,\dots,n\}$. Since $H$ does not stabilize $I$ and is generated by transpositions, it contains a transposition $t=(u,v)$ with $u\notin I$ and $v\in I$. If $u\neq 1$, we deduce that $t\in X_1\subset K$ and deduce that $u$ is in the same $K$-orbit as $v$, a contradiction. So $u=1$ and $H$ contains the transposition $(1,v)$, $v\in I$. Similarly, $H$ contains a transposition $(1,w)$ with $w\in J$. Hence $H$ contains $(1,v)(1,w)(1,v)=(v,w)$. This is again a contradiction since this transposition would have to belong to $K$ and contradict that $v,w$ are in distinct $K$-orbits. So $K$ is transitive on $\{2,\dots,n\}$. This finishes the proof.

  • $\begingroup$ If K is transitive on {2,…,n}, wouldn't induction hypothesis implies K is the full symmetry group on {2,…,n}? $\endgroup$ – Samantha Wyler Jun 3 '20 at 22:21
  • $\begingroup$ @SamanthaWyler yes! $n-1$ was a typo, I fixed it. $\endgroup$ – YCor Jun 3 '20 at 22:49

So I am convinced that I am miss understanding the question and its probably due to the fact that I am miss understanding the definition of $H$ being a transitive subgroup of $S_n$

Since $H$ is a transitive subgroup of $S_n$ I believe that means for any $\sigma, \tau \in S_n$ there exists an $h \in H$ such that $\sigma h = \tau$.

If this definition is correct then we can consider an arbitrary $\sigma \in S_n$. Let $h_1 \in H$ since $H$ is a subgroup of $S_n$ we have $h_1 \in S_n$ and so since $H$ is a transitive subgroup of $S_n$ we get that there is an $h_2 \in H$ such that $h_2h_1 = \sigma$ but since $H$ is a group and hence closed under multiplication we have $\sigma = h_2h_1 \in H$ and since $\sigma \in S_n$ was arbitrary $S_n = H$

I am definitly not understanding something about this question because otherwise this problem was to easy and the fact that $H$ is generated by some set of transpositions was completely irrelevant information.


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.