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.

Prove that $S_n$ is doubly transitive on $\{1, 2,\ldots, n\}$ for all $n \geqslant 2$.

I understand that transitive implies only one orbit, but...

share|improve this question
    
But what? Do you know what doubly transitive means? –  Jonas Meyer Nov 22 '12 at 4:51
add comment

3 Answers

It suffices to prove that $\mbox{Stab}_{S_n}(i)$ is transitive on $\{1,\ldots,n\}\setminus\{i\}$. Since $\mbox{Stab}_{S_n}(i)\cong S_{n-1}$ for any $i$ and symmetric groups are clearly transitive, the assertion follows immediately. Note that we can easily prove that $S_n$ is $n$-transitive in the same way.

share|improve this answer
    
@user50291: In fact, if $\Omega=\{1,2,3,...,n\}$ and $x=(a_1,a_2,...a_n)\in\Omega^n,\; y=(b_1,b_2,...b_n)\in\Omega^n$ then by assuming $$\pi= \left( \begin{array}{ccc} a_1 & a_2 & a_3 & ... & a_n\\ b_1 & b_2 & b_3 & ... & b_n\end{array} \right)$$ we will have $x^{\pi}=y$ snd this shows $S_n$ in $n-$ transitive on $\Omega$ as Alexander noted briefly. –  B. S. Nov 22 '12 at 8:26
1  
@Alexander Gruber: I find this an somewhat complicated way of proving something that is essentially true by definition. –  Derek Holt Nov 22 '12 at 8:56
add comment

In this case, doubly transitive means that $|\{1,\dots,n\}|\ge 2$ and for all $1\le i_1,i_2,j_1,j_2\le n$ with $i_1\ne i_2$ and $j_1\ne j_2$, there is a permutation $\sigma\in S_n$ such that $\sigma(i_1)=j_1$ and $\sigma(i_2)=j_2$. The first condition is just $n\ge 2$. To prove the second condition, we will take five cases.

Case I: $i_1,i_2,j_1,j_2$ are all (pairwise) distinct. Take $\sigma=(i_1j_1i_2j_2)$.

Case II: $i_1=j_2$ and $i_2\ne j_1$. Take $\sigma=(i_1j_1i_2)$.

Case III: $i_1=j_2$ and $i_2=j_1$. Take $\sigma=(i_1j_1)$.

Case IV: $i_1\ne j_1$ and $i_2=j_2$. Take $\sigma=(i_1j_1)$.

Case V: $i_1=j_1$ and $i_2=j_2$. Take $\sigma=\text{id}$.

Any other case would violate the distinctness conditions on $i_1,i_2,j_1,j_2$, so we are done.

share|improve this answer
add comment

In fact, $S_n$ acts $n$-fold transitive on $\{1,\ldots,n\}$ (hence the claim follows from $n\ge 2$), i.e. for $n$ different elements (which could that be?) $i_1,\ldots ,i_n$ you can prescribe any $n$ different elements $j_1,\ldots,j_n$ and dan find (exactly) one element $\sigma\in S_n$ such that $\sigma(i_k)=j_k$ for all $k$.

share|improve this answer
add comment

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.