Exploration 5: Permutation groups

November 16, 2023.

Questions:

TODO

Recall that a permutation of a set is a reordering of elements and is usually written like $(1~4~2~8~5~7)$ . Given an arbitrary set $X$ , the permutations on the set are written $S_X$ .

This notation is called cycle notation; $(1~4~2~8~5~7)$ is a cycle. More complex permutations are composed of cycles: the permutation $(1~4)(2~3)$ maps $1\mapsto 4\mapsto 1$ and $2\mapsto 3\mapsto 2$ . Ordering matters: the rightmost permutation is performed first.

The identity permutation (which does nothing to the set) can be written as a length $1$ cycle, like $(1)$ .

Composing permutations

Consider the permutation $(2~3)(3~1)$ . This first swaps $3$ and $1$ , and then swaps $2$ and $3$ . Since the net effect is the same as the cycle $(1~2~3)$ , we consider them to be the same permutation. That is, the set $\{(2~3)(3~1),(1~2~3)\}$ is a single-element set.

Permutations can be used to represent groups. Here’s how:

Theorem: For

X

a finite set of size

n

, any permutation group

S_X\iso S_n

, the symmetric group.

If $X$ is finite, there is a bijection from $X$ to the set $\{1\ldots n\}$ via renaming.
We can imagine transforming every $\lambda\in S_X$ to be a permutation in $S_n$ . Such a permutation would start from $\{1\ldots n\}$ , go to $X$ via the bijection, apply $\lambda$ , and go back to $\{1\ldots n\}$ via the bijection.
Then $S_X\iso S_n$ .

Cayley’s Theorem: Every finite group

G

is isomorphic to some permutation group.

We need to find an injective homomorphism $\sigma$ $σ$ between a finite group $G$ $G$ and $S_G$ $S_{G}$ . If we can, then $G\iso\theta\sigma(G)$ $G ≅ θ σ (G)$ .
- $\sigma(G)\subseteq S_G$ by injectivity, so $\theta\sigma(G)\subseteq S_n$ , so $\theta\sigma(G)$ is some permutation group, so we are done.
Define $\sigma(a)=g\mapsto ag$ (left-product with $a$ ). Since this map is invertible (by left-product with $a^{-1}$ ), it results in a permutation of elements, i.e. an element of $S_G$ .
$\sigma$ is a homomorphism, since applying left product of $b$ then left product of $a$ is the same as applying left product of $ab$ .
$\sigma$ is obviously one-to-one from its definition, i.e. given two maps $g\mapsto ag$ and $g\mapsto bg$ , if they are equal we must have $a=b$ .
Then $\sigma$ is an injective homomorphism, so we are done.

The implication of Cayley’s theorem is: to study the groups of order $n$ , we need only study the symmetric group $S_n$ .

Motivating example: $\forall g\in C_n\ldotp g^n=1$ . Proof. For every $g^k\in C_n$ , $(g^k)^n=(g^n)^k=1^k=1$ .

This proof is simple but required knowledge of cyclic groups, namely that every $g\in C_n$ can be represented as g^k for some $k$ . But using only the fact that $C_n$ is finite, we can ignore everything about cyclic groups and use Cayley’s theorem to reduce the proof to one about permutation groups.

Proof. Since $C_n$ is finite, by Cayley’s theorem it is isomorphic to a permutation group $S_{C_n}$ . We know that $\forall\sigma\in S_{C_n}\ldotp\sigma^n=e$ . Taking the image of this theorem via the isomorphism gives us $\forall g\in C_n\ldotp g^n=1$ .

What kinds of problems can we reduce to permutation group problems? Any problem involving finite groups! This may not always be a good move, since the permutation group can have up to $|S_n|=n!$ elements (a lot). But in general, we can now use theorems about permutation groups in any problem about finite groups.

In this section, we show how we can use groups to permute sets.

Given a group $G$ and a set $X$ , define the product $G\times X\to X$ as the left action of $G$ on $X$ . It takes an element $g$ and maps an element $x$ of $X$ to another element of $X$ .

The idea behind these group actions is that each element of $g$ permutes the elements of $X$ in some way, so that the product of two permutations (two elements of $g$ ) is like doing one permutation after the other, with $e$ being the identity permutation.

For example, let’s have $S_3$ act on elements of the set $\{1,2,3\}$ . The table might look like this:

          1 2 3
    (1) | 1 2 3
  (1 2) | 2 1 3
  (1 3) | 3 2 1
  (2 3) | 1 3 2
(1 2 3) | 2 3 1
(1 3 2) | 3 1 2

Here I picked an ordering of the elements in the set $\{1,2,3\}$ and arbitrarily named the permutations of $S_3$ .

Every (finite) group action is just a natural group action of permutation groups

In the abstract, where each element actually gets permuted to is immaterial – a group action just needs to behave like a permutation (identity, composition, inverses).

Let’s expand on this. Given an arbitrary group $G$ acting on an arbitrary set $X$ (both finite), we can use the table representation above (with elements of $G$ as rows and elements of $X$ as columns) to show that the action of $G$ on $X$ naturally turns out to be permutations, if successive group actions are to follow the composition and inverse laws.

TODO mention cayley tables somewhere with the following facts

if the cayley table is symmetric about the main diagonal, then the group is abelian
TODO

Example $G=\{e,a,b,c\}\iso K_4$ and $X={e,g,g^2}\iso C_3$ . We can let the action be anything (even trivial, fixing all of X) but let’s explore our choices. Draw the empty Cayley table, knowing that $e$ must be identity:

    e  g  g²
e | e  g  g²
a |
b |
c |

Each row must contain a permutation of $e,g,g^2$ . This is a natural consequence of the inverse law: every permutation must be reversible, so you can’t lose information by dropping one of those elements after a permutation.

In our example, since each element $a,b,c$ in $K_4$ is self-inverse (order $2$ ), we can only treat them as permutations looking like this:

        1 2 3
   () | 1 2 3
(1 2) | 2 1 3
(1 3) | 3 2 1
(2 3) | 1 3 2

after bijectively mapping each element of $X$ to a natural number, and mapping $\{a,b,c\}$ each to one of $(1~2),(1~3),(2~3)$ . (I picked the mapping arbitrarily here.)

We only need to define the action on some set of generators of $G$ , then the other rows can be derived by composition. Thus, the process for defining a group action works in general like this:

Map each element $x\in X$ to a natural number
Map each generating element $g\in G$ to a permutation with the same order as $g$

which falls out naturally because $g$ must follow the composition and inverse laws.

In this section, we visit the properties of group actions.

Recall the natural group action of $S_3$ acting on elements of the set $\{1,2,3\}$ .

          1 2 3
    (1) | 1 2 3
  (1 2) | 2 1 3
  (1 3) | 3 2 1
  (2 3) | 1 3 2
(1 2 3) | 2 3 1
(1 3 2) | 3 1 2

The permutations $\{(1),(2~3)\}$ fix $1$ , the permutations $\{(1),(1~3)\}$ fix $2$ , and {(1),(1~2)} fixes $3$ . Call these sets $G_1$ , $G_2$ , $G_3$ — they are the stabilizers of $1$ , $2$ , $3$ respectively. Concretely, the stabilizer of an element $x\in X$ is all the elements of $g\in G$ that fix $x$ .

The orbit of $x$ (denoted $O_x$ , sometimes $Gx$ ) is the set of all elements $x$ can get mapped to. Here, each of $1$ , $2$ , $3$ is able to reach all of $1$ , $2$ , $3$ , so for all $x$ , the orbit $O_x=X=\{1,2,3\}$ . Since everything in $X$ can reach everything in $X$ , there is only one orbit. When an action can take every element to every element like this, and therefore there is one orbit, we call it transitive.

For a non-transitive example, consider the action of $S_3$ on the power set $P(X)$ of $X=\{1,2,3\}$ :

          {} {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}
    (1) | {} {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}
  (1 2) | {} {2} {1} {3} {1,2} {2,3} {1,3} {1,2,3}
  (1 3) | {} {3} {2} {1} {2,3} {1,3} {1,2} {1,2,3}
  (2 3) | {} {1} {3} {2} {1,3} {1,2} {2,3} {1,2,3}
(1 2 3) | {} {2} {3} {1} {2,3} {1,2} {1,3} {1,2,3}
(1 3 2) | {} {3} {1} {2} {1,3} {2,3} {1,2} {1,2,3}

You can see that $\{1\}$ maps only to $\{\{1\},\{2\},\{3\}\}$ , etc. In this example, the orbits of each element in $P(X)$ consists of all the sets with the same number of elements.

Theorem: Orbits of a group action of

G

X

form equivalence classes in

X

Define the relation $\sim$ on $X$ where $x\sim y$ whenever $x,y$ are in the same orbit. Since it just checks set inclusion, $\sim$ trivially satisfies the properties of an equivalence relation.
Since $\sim$ is an equivalence relation, it partitions $X$ into equivalence classes.

Corollary: Elements of $G$ act on $X$ by permuting each orbit separately.

Theorem: A group action of

G

X

is transitive iff for every

x,y\in X

y=gx

for some

g\in G

When $y=gx$ for every pair $x,y\in X$ , it is the same as saying that every $x$ can reach every $y$ via $G$ , i.e. the action is transitive.

Theorem: For a transitive group action on

X

, the action of a normal subgroup on

X

gives orbits that all have the same cardinality.

Since the group action is transitive, let $y=gx$ for some fixed $x,y\in X$ . Then: $\begin{aligned} &Ny\\ =&Ngx&\text{ because }y=gx\\ =&gNx&\text{ because }N{ is normal}\\ =&g(Nx) \end{aligned}$ shows that left-multiplication by $g$ is a map between arbitrary orbits $Ny$ and $Nx$ . It is a bijection since the inverse is left-multiplication by $g^{-1}$ .
Since there is a bijection between arbitrary orbits $Nx,Ny$ they must all have the same cardinality.

The stabilizer of some $x\in X$ (denoted $G_x$ ) is a subgroup of $G$ composed of every $g$ that permutes that $x$ to itself. Similarly, the normalizer of a subgroup $H\le G$ (denoted $S_x$ ) is the subgroup of $G$ composed of every $g$ that permutes $H$ to itself.

Theorem: For a transitive group action on

X

, a subgroup

H

acts transitively on

X

iff

G=HG_x

for some

x\in X

( $\to$ $\to$ )
- If a subgroup acts transitively on $X$ it means it sends every element of $X$ to every element of $X$ . That is, $X=Hx$ for every $x\in X$ .
- Fix some $x\in X$ and some $g\in G$ , giving us an element $y=gx$ . Since the group action is transitive, we may write $y=hx$ for some $h\in H$ . Since this $h^{-1}gx=x$ we have $h^{-1}g\in G_x$ for arbitrary $h\in H$ , so $g\in H G_x$ . Since this is true for every $g$ , we know that $G=H G_x$ .
( $\from$ $\leftarrow$ )
- To prove $H$ acts transitively on $X$ , we need only prove $X=Hx$ for arbitrary $x\in X$ .
- Since the group action is transitive, $Gx=X$ . But we are given $G=HG_x$ , so $X=H G_x x=Hx$ .

Corollary: Proper subgroups that contain the stabilizer of any element cannot act transitively.

Intuitively this makes sense – if a subgroup contains a stabilizer for $x\in X$ then it fixes $x$ , and therefore doesn’t take $x$ to every other element of $X$ .
Note that $HG_x=H$ when $G_x\subseteq H$ . So if $H$ acts transitively on $X$ but contains any stabilizer $G_x$ for some $x\in X$ , then you can show $G=HG_x=H$ : the only possible $H$ acting transitively on $X$ is $G$ itself.

Orbit-Stabilizer Theorem: Given

x\in X

|O_x|=|G|/|G_x|

Fix some $x\in X$ . To find the size of the orbit $O_x$ , we note that $\begin{aligned} &gx=hx\\ \iff &x=g^{-1}hx\\ \iff &g^{-1}h\in G_x \end{aligned}$
Define an equivalence relation where $g\sim h$ iff $g^{-1}h\in G_x$ . Then $gx=hx$ whenever $g,h$ are in the same equivalence class under $\sim$ . This means each equivalence class corresponds to a distinct element $gx$ that $x$ maps to, i.e. an element of its orbit $O_x$ . Then the number of equivalence classes is the number of elements in the orbit, $|O_x|$ .
This equivalence relation $\sim$ is the same as used in the proof of Lagrange’s theorem, so reusing the same argument in that proof, the equivalence classes all have the same size $|G_x|$ which divides $|G|$ . Therefore the number of equivalence classes is $|G|/|G_x|$ .
Therefore, number of equivalence classes $=|O_x|=|G|/|G_x|$ .

In this section, we study two possible actions of groups on themselves.

Consider a group acting on itself: $(g,h)\mapsto gh$ .

Theorem: The action of a group on itself is transitive.

An action of $G$ on $X$ is transitive iff for every $x,y\in X$ , $y=gx$ for some $g\in G$ . In this case both $x,y\in G$ , so we can let $g=yx^{-1}$ to make the above equation always true.

Theorem: The action of a group on itself has trivial stabilizers.

An element $g$ is in the stabilizer of $x$ iff $gx=x$ .
In this case, $x$ is an element in $G$ , so we right-multiply by the inverse $x^{-1}$ to get $g=e$ .
Then the only stabilizer of any $x\in G$ is the identity element, so all stabilizers are trivial.

Now consider a finite group $G$ acting on itself by conjugation: $(g,h)\mapsto ghg^{-1}$ . This is different from the left-multiplication definition of group action we had earlier. In fact, a group action doesn’t have to be finite or necessarily permute the elements – it just needs to be faithful, meaning there is only one identity in $G$ , and it needs to follow the group laws. An action is faithful if the intersection of all the stabilizers $G_x$ for $x\in X$ is identity $\{e\}$ .

Theorem: The action of a group on itself via conjugation is faithful iff the center is trivial.

For a conjugation group action of $G$ on itself, an element $g$ is in the intersection of all stabilizers iff for every element $h\in G$ , $ghg^{-1}=h$ . In other words, $g$ commutes with every element $h$ .
So if the center is trivial, the intersection of all stabilizers is trivial, so the action is faithful.

Theorem: The orbits of a group acting on itself by conjugation are exactly its conjugacy classes.

The orbits of a conjugation group action of $G$ on itself are, for each element $h\in G$ , all the elements $ghg^{-1}$ for $g\in G$ . But this is exactly the definition of the conjugacy classes of $h$ .

A centralizer of $g$ (denoted $C_G(g)$ ) is the subgroup of $G$ that commutes with $g$ .

Theorem: The stabilizer of

x

in a group acting on itself by conjugation is the centralizer of

x

For a conjugation group action, an element $g$ is in the stabilizer of $x$ iff $gxg^{-1}=x$ , i.e. $g$ commutes with $x$ . But this is exactly the definition of the centralizer of $h$ .

Theorem: The singleton orbits of a group acting on itself by conjugation are exactly the central elements of the group.

( $\to$ ): if $b$ is a conjugate of $a$ then $b=gag^{-1}$ for some $g$ . But if either $a$ or $b$ is in the center (say $ag=ga$ ), then $b=agg^{-1}=a$ . Since $b=a$ when either is in the center, elements in the center end up in singleton conjugacy classes.
( $\from$ ): if $a$ is in a singleton conjugacy class, $gag^{-1}=a$ for all $g$ , which means $ga=ag$ for all $g$ , so $a$ is in the center.

Theorem: The action of a group on itself by conjugation is not transitive, unless the group is trivial.

A group action is transitive if there is only one orbit. But since identity is always central and therefore has a singleton orbit, there are orbits outside the identity orbit, so long as the group is not trivial.

We can define at the class equation of a group action. For a group action of $G$ on $X$ , given each $x_i$ as a representative of each non-singleton orbit $O_{x_i}$ , and $|F|$ the number of fixpoints (singleton orbits), we have $|X|=|F|+\sum_i |G|/|G_{x_i}|$

Here’s how we arrive at the class equation:

If you take the union of all orbits, you get the set $X$ .
Orbits are disjoint, so you can split $X$ into the set of singleton orbits (fixpoints) $F$ and all non-singleton orbits $O_{x_i}$ to get $|X|=|F|+\sum_i |O_{x_i}|$ .
By orbit-stabilizer theorem, we know $|O_x|=|G|/|G_x|$ .
Therefore, $|X|=|F|+\sum_i |G|/|G_{x_i}|$ .

In particular, if the group action in question is the conjugation action of a group on itself, we can recover the original class equation of a group: $|G|=|Z(G)|+\sum_i|G|/|C_G(g_i)|$

misc notes

Class Equation Let G be a finite group and G ~ G by conjugation: y - x := yxy~! » the orbits are the conjugacy classes » the stabilizers are centralizers Gx = {y in G | yxy^-1} = Z_G(x) » the singleton orbits are the elements of the center Z(G)={z in G | zg=gz forall g in G} Class Eqn: If xᵢ are representatives all non-central conjugacy classes in G then |G| = |Z(G)| + ∑ᵢ [G: Z_G(xᵢ)]

Theorem: In

S_n

, conjugating a permutation

\sigma

by another permutation

\tau

is the same as decomposing

\sigma

into cycles and applying

\tau

to each cycle element.

Consider an arbitrary part of a cycle $(\ldots~a~b~\ldots)$ in $\sigma$ — in other words, $\sigma(a)=b$ . But then $\tau\sigma\tau^{-1}(\tau(a))=\tau\sigma(a)=\tau(b)$ shows that the corresponding part of the cycle in $\tau\sigma\tau^{-1}$ is $(\ldots~\tau(a)~\tau(b)~\ldots)$ .

Corollary: Permutations of the same cycle type are in the same conjugacy class. Permutations of different cycle types are in different conjugacy classes.

Theorem: The conjugacy classes of

S_n

may split into

2

conjugacy classes in its subgroup

A_n

Consider the conjugation action on $S_n$ . By the orbit-stabilizer theorem, we have $|O_\sigma|=\frac{|S_n|}{|{S_n}_\sigma|}$ for an arbitrary permutation $\sigma$ in $S_n$ .
The stabilizer ${S_n}_\sigma$ $S_{n}_{σ}$ may or may not contain odd permutations.
- If it contains no odd permutations, then it is completely contained in $A_n$ , and so we have $|O_\sigma|=\frac{|A_n|}{|{A_n}_\sigma|}=\frac{|S_n|/2}{|{S_n}_\sigma|}$ halving the orbit (the conjugacy class) of $\sigma$ .
- If it contains some odd permutation, then note that ${A_n}_\sigma=A_5\cap{S_n}_\sigma$ . Is it the case that this implies ${A_n}_\sigma$ is half of ${S_n}_\sigma$ ? In that case, we have $|O_\sigma|=\frac{|A_n|}{|{A_n}_\sigma|}=\frac{|S_n|/2}{|{S_n}_\sigma|/2}$ , meaning the orbit (the conjugacy class) stays the same.
Therefore, conjugacy classes in $S_n$ may or may not split into $2$ conjugacy classes in $A_n$ .

Theorem:

A_5

is simple.

$A_5$ consists of even permutations (formed by an even number of transpositions.) Such permutations are either a $3$ -cycle $(a~b~c)$ , a $5$ -cycle $(a~b~c~d~e)$ , or a product of two disjoint $2$ -cycles $(a~b)(c~d)$ .
To count the conjugacy classes in $A_5$ $A_{5}$ , we first count these permutations’ conjugacy classes in $S_5$ $S_{5}$ , since in $S_n$ $S_{n}$ permutations of the same cycle type are conjugate to each other.
- $3$ -cycles: two ways to arrange three elements, of which you have ${5\choose 3}$ choices. $2{5\choose 3}=20$
- $5$ -cycles: for each of $5!$ choices of five elements, rotations of the cycle lead to the same cycle, so there are $\frac{5!}{5}=4!=24$
- Cycle type $[2,2,1]$ : There are ${5\choose 2}$ choices for each $2$ -cycle, and order doesn’t matter, so there are $\frac{{5\choose 2}{5\choose 2}}{2}=15$ of these.
- Identity: The identity element is always in its own conjugacy class.
This accounts for all of the $\frac{5!}{2}=60$ permutations of $A_5$ . Now in $A_5$ some conjugacy classes may split into two, because we now lack odd permutations to conjugate by. Let’s assume that the class sizes $20,24,15$ split into $10,10,12,12,15$ . (In reality, the size $20$ class of $3$ -cycles doesn’t split.)
Normal subgroups are unions of conjugacy classes that include the identity permutation. Given that the sizes of the non-identity conjugacy classes are at worst $10,10,12,12,15$ , the possible normal subgroup orders are $1,11,13,16,21,23,25,28,33,36,38,40,45,60$ .
By Lagrange’s theorem, the order of a subgroup must divide the order of the group. Since $|A_5|=\frac{5!}{2}=60$ , the only possible subgroup orders are its divisors $1,2,3,4,5,6,10,12,15,20,30,60$ .
The only common orders of the above two lists are order $1$ (the trivial group) and $60$ ( $A_5$ itself). So they are the only normal subgroups, and thus $A_5$ is simple.

< Back to category Exploration 5: Permutation groups (permalink)
Exploration 4: Homomorphisms Exploration 6: Groups as matrices