The Analogical Engine

Transitive Permutation Groups

This post is a follow on from the previous post on permutation groups. We need a few definitions.

A permutation group $\textstyle (G, \Omega)$ is said to be transitive if for any $\textstyle \alpha, \beta \in \Omega$ there exist $\textstyle g \in G$ such that $\textstyle \alpha^g = \beta$

All the permutation groups we have considered so far have been transitive.

If $\textstyle (G, \Omega)$ is a permutation group and $\textstyle \alpha \in \Omega$ then the orbit of $\textstyle \alpha$ under the action of $\textstyle G$ is:

$\alpha^G = \{ \alpha^x : x \in G \}$

For a transitive permutation group $\textstyle \alpha^G = \Omega$ . Otherwise $\textstyle \Omega$ maybe be partitioned into orbits $\textstyle \Omega = \coprod_{i = 1..n} \Omega_i$ such that for each $\textstyle i$ , the permutation group $\textstyle (G,{\Omega_i})$ is transitive.

For an example of a non-transitive permutation group, consider the way a group acts on itself by conjugation.

$x^g = g^{-1} x g$
The orbits of this action are the conjugacy classes of the group. Now for some more definitions:

Let $\textstyle (G, \Omega)$ be a transitive permutation group, and let $\textstyle \alpha$ be any point of $\textstyle \Omega$ . The point stabilizer of $\textstyle \alpha$ is:

$G_\alpha = \{ x \in G : \alpha^x = \alpha \}$

In the example of a group acting on itself by conjugation, the stabilizer of a point $\textstyle g$ is precisely those $\textstyle x$ which commute with $\textstyle g$ .

The following fact is crucial:

$\boxed{ G_{\alpha^g} = g^{-1} G_{\alpha} g \qquad \text{ for any } g \in G}$

To see what this is true, suppose that $\textstyle x \in G$ is such that:

$(\alpha^g)^x = \alpha^g$
It follows that $\textstyle \alpha^{gxg^{-1}} = \alpha$ and so $\textstyle gxg^{-1} \in G_\alpha$ . That is:

$x \in g^{-1}G_\alpha g$
Conversely, suppose that $\textstyle x \in g^{-1}G_\alpha g$ . Then $\textstyle gxg^{-1} \in G_\alpha$ and so $\textstyle \alpha^{gxg^{-1}} = \alpha$ . That is $\textstyle \alpha^{gx} = \alpha$ , so $\textstyle x \in G_{\alpha^g}$ .

From here it is relatively straightforeward to see that every transitive permutation group is permutation equivalent to one of the form $\textstyle G$ acting on the cosets of some subgroup $\textstyle H$ .

Let $\textstyle (G,\Omega)$ be a transitive permutation group and $\textstyle \alpha$ is some point of $\textstyle \Omega$ . Let $\textstyle \cos_G(G_\alpha)$ denote the set of right cosets of the point stabilizer $\textstyle G_{\alpha}$ For each $\textstyle \beta \in G$ Consider:

$S_\beta = \{ x \in G : \alpha^x = \beta \}$
If $\textstyle \beta = \alpha^g$ then it’s not hard to see that $\textstyle S_{\beta}$ is a right coset of $\textstyle G_{\alpha}$ :

$S_{\beta} = G_{\alpha} g$
Define $\textstyle \eta : \Omega \to \cos_G(G_\alpha)$ by $\textstyle \eta(\beta) = S_\beta$ and take $\textstyle \varphi : G \to G$ to be the identity. We have that, for any $\textstyle \beta \in \Omega$ and any $\textstyle x \in G$ , if $\textstyle \beta = \alpha^g$ then:

$ \begin{align*} \eta(\beta^x) & = S_{\beta^x} \\ & = S_{\alpha^{gx}} \\ & = G_\alpha gx \\ & = G_\alpha g^{\varphi(x)} \\ & = \eta(\alpha^g)^{\varphi(x)} \\ & = \eta(\beta)^{\varphi(x)} \end{align*} $

Thus $\textstyle \eta$ and $\textstyle \varphi$ establish the desired permutation equivalence.

As a consequence of this, we have that for any $\textstyle g \in G$ the size of the conjugacy class of $\textstyle g$ in $\textstyle G$ is given by the size of the group divided by the number of elements in $\textstyle G$ which commute with $\textstyle g$ .

pdf version

This entry was posted on Sunday, November 22nd, 2009 at 1:21 pm and is filed under Robin. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Subscribe: Entries | Comments
Search for:
Recent Posts
Math
Meta
Calendar

September 2010

M T W T F S S

« Aug

1 2 3 4 5

6 7 8 9 10 11 12

13 14 15 16 17 18 19

20 21 22 23 24 25 26

27 28 29 30

September 2010
M	T	W	T	F	S	S
« Aug
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30

Transitive Permutation Groups

Leave a Reply

Recent Posts

Math

Meta

Calendar