Primitive Permutation

• Let be a transitive group group on . A nonempty subset is a block of primitivity for if, for any , either or . A partition of into distinct blocks of primitivity gives a system of imprimitivity for .

• A transitive group with no nontrivial system of imprimitivity is primitive otherwise it is imprimitive.

• In other words, a primitive group acts transitively and the action preserves only the trivial partitions — or singletons.

• (Godsil 2.5.1) Let be a transitive permutation group on and . Then is primitive if and only if is a maximal subgroup of

• Motivated by Godsil 2.6.1, a non-symmetric orbit is connected if the corresponding digraph, whose vertex set is and arc set based on , is strongly / weakly connected.

  Both strong / weakly connected conditions are equivalent because acts transitively so for any vertex, the indegree equals the outdegree.

• (Godsil 2.6.2) Let be a transitive permutation group on . Then is primitive if and only if each non-diagonal orbit is connected.

• (Godsil e2.12) The only primitive permutation group on that contains a transposition is the symmetric group

  • Proof: Let be a primitive permutation group and be the transposition of two elements .

    is primitive, therefore it is transitive. Thus, there exists a permutation mapping for all . Let be this mapping. Then, gives us another transposition between .

    Since is primitive, acts transitively on . Which means, there must exist such that . This lets us generate the transposition for arbitrary and .

    Since must contain all transpositions, it must also contain all permutations. It is thus

Links §

• Algebraic Graph Theory by Godsil and Royle
• Group Action