Symbols and Notations

  1. $S_n$ means Symmetric group.
  2. $[n] = \{1,2,\cdots ,n\}$.
  3. $a^{\sigma}$= $b$, means image of element $a$ under $\sigma$.
  4. $(1 2 3 \cdots n)$ means $(1\mapsto 2, 2\mapsto 3, \cdots, n\mapsto 1)$

Let $S_n$ be a Symmetric group acts on set $[n]$ by a map given below : $$\pi : S_n \times [n]\mapsto [n]$$

Definition $1 :$ A group action $(\pi)$ is transitive if it only posses a single orbit.

Definition $2$ : A group action$(\pi)$ is primitive if it is transitive and it has no nontrivial (size of block is greater than 1 and less than $n$) group blocks

Question $1$ : Is this group action transitive ?

Proof :

Make a graph of $n$ vertices , Now an edge from vertex $a$ to $b$ means $\exists$, $\sigma \in S_n$ such that $a^{\sigma} = b$. So will have a directed graph and if the graph is strongly connected then it means group action of $S_n$ on set $[n]$ is transitive.

I am able to prove the fact that for any two elements $a,b \in [n]$, there is an direct edge from $a$ to $b$ and also from $b$ to $a$. This implies graph is strongly connected.

Is this a complete proof or I am missing something here.

Question 2 : Is this group action primitive ?

Proof :

Let $\Delta = \{1,2,3\}$ ( non-trivial block ) and $\sigma = (3 4 5\cdots n)$ , we can see clearly that $\Delta^{\sigma} \cap \Delta \neq \phi $, so it means group action is not primitive.

Now let $A_n$ be a alternating group acts on set $[n]$ by a map given below : $$\pi_1 : A_n \times [n] \mapsto [n]$$

Question $3$ : Is this group action $(\pi_1)$ transitive (and how to prove it) ?

By doing the same way as above, it seems to me that group action $(\pi_1)$ is transitive.

Question 4 : Is this group action $(\pi_1)$ primitive (and how to prove it) ?

Please note that I have already seen these posts

  1. Action of permutation group on set of numbers is transitive
  2. $S_n$ acting transitively on $\{1, 2, \dots, n\}$
  3. Proving that a given group action is Transitive.
  • 1
    $\begingroup$ The answers to your questions are that $\pi$ is transitive and primitive for all $n$, and $\pi_1$ is transitive and primitive for all $n>2$. There is a theorem that says that any $2$-transitive action is primitive. You can use that for $\pi$ for $n \ge 2$, and for $\pi_1$ for $n \ge 4$. $\endgroup$ – Derek Holt Jul 4 '17 at 13:50
  • $\begingroup$ Thanks but I am looking for proof . Is it similar to what I have as above ? $\endgroup$ – user275490 Jul 4 '17 at 13:54

Let's assume $n\ge3$.

(Q1) There's no need talk about graphs here. Saying "I am able to prove this fact" does not constitute a proof. You must show that given any $i$ and $j$ in $\{1,\cdots,n\}$ there exists a permutation $\sigma$ such that $\sigma(i)=j$. If $i=j$, then $\sigma=\mathrm{id}$ is such a permutation. Otherwise, the transposition $\sigma=(ij)$ is such a permutation.

(Q2) Your "proof" here makes no sense. The task is not to show that $\{1,2,3\}$ is not a block, it is to show there are no nontrivial blocks at all. Given any nontrivial subset $B\subseteq\{1,\cdots,n\}$, it must be proper and not a singleton to be a nontrivial block, so there exist at least two distinct elements $i,j\in B$ and at least one element $k\not\in B$. The permutation $\sigma=(jk)$ tells us that $B\cap B^{\sigma}$ includes the element $i\in B$ but does not include $j\in B$, so $B$ fails to be a block.

(Q3) you will need to do slightly differently from (Q1) because $(ij)$ is not in $A_n$.

(Q4) you will need to do differently as well, since $(jk)$ is not in $A_n$.

| cite | improve this answer | |
  • 1
    $\begingroup$ For Q 3) if $(i j)$ is not in $A_n$ but there will be $\sigma_i$ and $\sigma_j$ such that $\sigma _i$ is like (i k) and $\sigma_j $ is like (k j), so I will take the composition these two elements so done $\endgroup$ – user275490 Aug 19 '17 at 13:50

Your Answer

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