Orbits and Stabilizers

Back to Algebra Page

On this page:

• Introduction
• Orbits and Stabilizers 101
• Application: Lagrange’s Theorem
• Orbit-Stabilizer Theorem
• Examples of Orbits and Stabilizers
• Application: Cycle Decomposition Theorem
• Worked Exercises

Introduction

Many group actions “get stuck” in a certain part of the sets they act on (similar to the idea of invariant subspaces in linear algebra) and we will later call these “certain parts” the orbits of the action. As we will see, this allows us to make some pretty powerful counting statements about finite groups.

Orbits and Stabilizers 101

[theorem] [thmtitle]Proposition (Relation induced by orbits).[/thmtitle]

If $A$ is a $G$-set, then the the relation

is an equivalence relation. [/theorem]

[proof] (Reflexivity) $a = 1a$ for each $a \in A$, giving $a \sim a$.

(Symmetry) If $a = gb$, then $g^{-1}a = b$. Thus, $b \sim a$ whenever $a \sim b$.

(Transitivity) If $b = hc$ and $a = gb$, then $a = ghc$ by associativity of group actions. Thus, $a \sim c$ whenever $a\sim b$ and $b\sim c$. [/proof]

The equivalence classes of this relation are so important that they have a name:

[definition] [deftitle]Definition (Orbits).[/deftitle]

Let $A$ be a $G$-set. Then the equivalence classes

are called orbits of the action of $G$ on the set $A$. If there is only one orbit, then the $G$-action is transitive. [/definition]

Another concept that is useful in group theory is to study the elements of the group that keep a particular subset fixed. These have a strong relationship with orbits because the orbit $Ga$ is significantly acted upon by $G$ by elements that don’t fix $a$. So we can get rid of them by modding $G$ out by the elements that fix $a$. This observation is so remarkable that it has a name: the Orbit-Stabilizer Theorem.

[definition] [deftitle]Definition (Stabilizers).[/deftitle]

Let $A$ be a $G$-set. If $a \in A$, the stabilizer of $a$ in $G$ is the set

[/definition]

[theorem] [thmtitle]Proposition ($\Stab_G(a)$ is a subgroup of $G$).[/thmtitle]

Let $A$ be a $G$-set and $a\in A$. Then $\Stab_G(a)$ is a subgroup of $G$. [/theorem]

[proof] Note that $\Stab_G(a)$ is necessarily nonempty because the identity of $G$ fixes all elements of $a$ by definition. Now let $g, h \in \Stab_G(a)$. Then

where the last equality follows from the fact that

Thus, $h^{-1}g \in \Stab_G(a)$ and we are done. [/proof]

Application: Lagrange’s Theorem

While not totally necessary, orbits give a particular perspective on how to prove the classical result that every subgroup has order that is a factor of the parent group (given that said parent is a finite group).

[theorem] [thmtitle]Theorem (Lagrange’s Theorem).[/thmtitle]

Let $G$ be a finite group and $H$ a subgroup of $G$. Then

[/theorem]

[proof] Let $H$ (right-)act on $G$ by right multiplication. Then, the orbits are precisely the left cosets of $H$ in $G$ by definition. Since the orbits form a partition of $G$, we have

where the union is indexed over representers corresponding to distinct left cosets. Each $xH$ is in bijection with $H$ (surjectivity is immediate and injectivity is by cancellation in $G$). Thus,

where the summation is indexed over the same set as the disjoint union above. The last equality follows from the bijectivity remark and the fact that $[G:H]$ is the number of left cosets of $H$ in $G$. [/proof]

[example] [extitle]Remark.[/extitle]

While all of my pages primarily focus on left actions, the results can be reproduced for right actions which is why we use them without justification in the proof. Notice that this shows that Lagrange’s theorem is a special case of enumeration of $H$-sets. [/example]

Orbit-Stabilizer Theorem

And, now, we finally formalize the interaction between orbits and stabilizers.

[theorem] [thmtitle]Theorem (Orbit-Stabilizer Theorem).[/thmtitle]

Let $G$ be a group acting on the set $A$ and $a \in A$. Then the orbit $Ga$ is in 1-1 correspondence with $G/\Stab_G(a)$. In particular, if $G$ is finite, then

[/theorem]

[proof] Let $f:Ga \to G/\Stab_G(a)$ be given by $f(ga) = g\Stab_G(a)$.

(Injectivity) Suppose that $g\Stab_G(a) = h\Stab_G(a)$. Then $h^{-1}g \in \Stab_G(a)$. Then

Thus, $f$ is injective as desired.

(Surjectivity) For any given $g\Stab_G(a) \in G/\Stab(a)$, we see that $f(ga) = g\Stab_G(a)$. Thus, $f$ is surjective.

For the final claim, we apply Lagrange’s theorem and replace $[G:\Stab_G(a)]$ with $|Ga|$ and we are done. [/proof]

Examples of Orbits and Stabilizers

[example] [extitle]Trivial action.[/extitle]

Let $G$ be a group acting trivially on the set $A$. In this case, the orbits are trivial as $Ga$ is the singleton $\{a\}$. The action is transitive if and only if $A$ consists of a single element. The stabilizer of any given $a \in A$ is just $G$ itself. [/example]

[example] [extitle]Left regular action.[/extitle] The regular action of $G$ on itself is transitive so the stabilizer of any $g \in G$ is trivial. [/example]

[example] [extitle]Natural $\Sym_A$-action.[/extitle]

The symmetric group $\Sym_A$ acts transitively on $A$ in its usual way (obvious by definition) and so there is a single orbit. The stabilizer of a given $a \in A$ are the permutations that fix $a$. [/example]

[example] [extitle]Natural $\Sym_n$-action.[/extitle]

A special case of the above example is when $A = [n]$. Here, we can use the Orbit-Stabilizer theorem to measure the sizes of the orbits. Since $\Stab(i)$ has $(n - 1)!$ elements (where $i\in [n]$), the orbit of $i$ consists of exactly $n$ elements. [/example]

[example] [extitle]Dihedral groups.[/extitle]

The group $D_{2n}$ acts transitively on the vertices of the regular $n$-gon. The stabilizer of any vertex is a subgroup of order $2$ generated by the reflection about the line of symmetry passing through that vertex. The Orbit-Stabilizer theorem tells us that the corresponding orbit consists of $n$ elements (which makes sense because there are $n$ places for a vertex to be). [/example]

Application: Cycle Decomposition Theorem

Given a particular $\sigma \in \Sym_n$, we can characterize $\sigma$ by investigating how a particular $i\in [n]$ cycles through the powers of $\sigma$. In orbit-theoretic language, we are characterizing $\sigma$ via the orbits of the group generated by the powers of $\sigma$.

[theorem] [thmtitle]Theorem (Cycle Decomposition Theorem).[/thmtitle]

Every $\sigma \in \Sym_n$ has a unique decomposition into a product of disjoint cycles up to reording of the cycles and cyclical equivalence. [/theorem]

[proof] Let $\sigma \in \Sym_n$ and define $G = \generator{\sigma}$. Then $G$ acts on $[n]$ in the natural way and, therefore, partitions $[n]$ into a unique set of disjoint orbits.

(Existence) For a given orbit $\mathcal{O}$, pick a representor $x \in \mathcal{O}$. Now, since $G$ is cyclic, it is abelian and so $G/\Stab_G(x)$ is a group of order $d$ where $d$ is the smallest positive integer such that $\sigma^d \in \Stab_G(x)$. This tells us that the unique cosets of $\Stab_G(x)$ are

The Orbit-Stabilizer theorem implies there is bijection between $\mathcal{O}$ and $G/\Stab_G(x)$. In particular, that map is given by $\sigma^i(x) \leftrightarrow \sigma^i \Stab_G(x)$. Thus, the elements of the orbit are given by

Thus, the cycle corresponding to $\mathcal{O}$ consists of the above. Rince and repeat for the remaining orbits. Furthermore, the disjointness of the orbits implies that the cycles are disjoint. Thus, we have existence of a cycle decomposition.

(Uniqueness) The disjointness of the cycles implies that we can reorder the cycles however we want. For cyclical equivalence, we can pick out $\sigma^i(x)$ to be the representor rather than $x$ for the orbit $\mathcal{O}$ and we are done. [/proof]

Worked Exercises

[example] [extitle]Dummit and Foote Problem 3.2.9 (McKay’s proof of Cauchy’s Theorem).[/extitle]

Let $G$ be a finite group and $p$ be a prime that divides $|G|$. Then $G$ contains an element of order $p$. [/example]

[proof] Define $\mathcal{S}$ to be the set of $p$-tuples of elements of $G$ the product of whose coordinates is $1$, i.e.

First, we show that $\mathcal{S}$ has $|G|^{p-1}$ elements. It is clear that we may choose $x_1, \ldots, x_{p-1}$ freely which forces $x_p$ to be the inverse of their product. Thus, $\mathcal{S}$ consists of $|G|^{p-1}$ elements and so $p$ divides the cardinality of $\mathcal{S}$.

Now let the cyclic group $C_p$ act on $\mathcal{S}$ by cyclic permutation:

where the indices are taken modulo $p$. We claim that the orbits either contain a single element, or exactly $p$ elements. By the orbit stabilizer theorem,

As $p$ is prime, the orbit has cardinality either $1$ or $p$ as desired. Thus,

where $k$ is the number of orbits of size $1$ and $d$ is the number of orbits of size $p$. Now, since

we know that $k$ is a multiple of $p$. Furthermore, $k$ cannot be zero since the orbit $(1, \ldots, 1)$ is one of these $k$ orbits. Thus, $G$ must have element of order $p$ and we are done. [/proof]

[example] [extitle]Dummit and Foote Problem 3.2.16 (Fermat’s Little Theorem).[/extitle]

If $p$ is a prime, then

for all $a\in \ZZ$. [/example]

[proof] The case where $a = 0$ is trivial so we proceed to the case $a \neq 0$. Then we know that $\overline{a} \in (\ZZ/p\ZZ)^\times$ where $\overline{a}$ is the coset containing $a$ in $(\ZZ/p\ZZ)^\times$. By Lagrange’s theorem, the order of $\overline{a}$ must divide $p - 1$. So this implies that

Multiplying both sides by $\overline{a}$, noting that $\overline{a}^p = \overline{a^p}$, and translating back to modular arithmetic gives us the desired result. [/proof]

[example] [extitle]Dummit and Foote Problem 3.2.22.[/extitle]

$\QQ$ has no proper subgroup of finite index. Furthermore, $\QQ/\ZZ$ has no proper subgroups of finite index. [/example]

[proof]

(First claim) Suppose that $H$ is a subgroup of $\QQ$ with finite index. Since $\QQ$ is abelian, $H$ is also normal in $\QQ$ and $\QQ/H$ is a finite group. Say $d = \QQ/H$.

Let $f:\QQ \to \QQ/H$ be the canonical projection. Since $\QQ/H$ has order $d$, it follows that

for all $r \in \QQ$. But this means that $r \in H$ for all $r\in \QQ$ or that $H = \QQ$. So $\QQ$ has no proper subgroups and we are done.

(Second claim) If $\QQ/\ZZ$ did have such a subgroup, then it is of the form $\overline{H}=H/\ZZ$ where $H$ is a subgroup of $\QQ$ containing $\ZZ$ by the correspondence theorem. Since $\overline{H}$ has finite index, and $\QQ/\ZZ$ is abelian, the group

must be finite. But this means that $H$ has finite index in $\QQ$ which contradicts the first claim. The isomorphism above is by the Third Isomorphism Theorem. [/proof]