Subgroups of Even Permutations Orbits, Stabilizers etc...

Mike

2021-06-11 (Last Modified: 2021-11-06)

Subgroups of Even Permutations Orbits, Stabilizers etc...

Page content

When we left off in the previous entry Applying Permutations to Group Theory, we were about to prove that a finite group with $ 2(2k + 1) $ elements always has a normal subgroup of idex 2. Now we continue in that direction.

In the entry, More Math of Permutations, we showed that a finite permutation is composed of finite disjoint cycles. We now take that a little bit further and show that every permutation can be factored into the product of disjoint cycles. We’re also going to re-define what it means for a permutation to be cyclic. Our reformulation won’t rely on notation as much as what we did before. It will also tie in better with our ongoing discussion of groups. Before we do that, though, we’re going to introduce some definitions.

Definition (orbit)

Let $ S $ be a set of permutations (not necessarily a group) of a set $X$. The orbit of $x$, where $ x \in X$, is $$ \begin{align} &Orb_{S}(x) := \\ &\{ y \in X | \exists \sigma \in S \text{, where } \sigma(x) = y \} \\ \end{align} $$

Definition (stabilizer)

Let $S$ be a set of permutations (not necessarily a group) of a set $X$. The stabilizer of $x$, where $x \in X$, is

$$ \begin{align} &Stab_{S}(x) := \\ &\{ \sigma \in S | \sigma(x) = x \} \\ \end{align} $$

Definition (fix)

Let $\sigma$ be a permutation of $X$. Then

$$ \begin{align} &fix(\sigma) := \\ &\{ x \in X | \sigma(x) = x \} \\ \end{align} $$

We can rephrase our definition of a cyclic permutation, now, using some of the definitions and concepts we’ve introduced in the entries since we last considered them.

Lemma (subgroup intersections)

Let $ \{H_i\}_{i \in I} $ be subgroups of a group, $G$, then $ \bigcap_{i \in I} H_i $ is also a subgroup of $G$. I.e. the intersection of arbitrarily many subgroups of a group is itself a subgroup.

Proof

This is straight-forward. Let $x $, $y \in$ $ \bigcap_{i \in I} H_i $, then since each $ H_i $ is a subgroup, $ y^{-1} \in H_i $, for every $H_i$, and likewise since each one is closed under the binary operation of $G$, $ x \cdot y^{-1} \in H_i $, for every $H_i$. That means that $ x \cdot y^{-1} \in \bigcap_{i \in I} H_i $. Thus it is a subgroup of $G$.

QED

Notice there’s a very similar proof, which we’ll leave to you, that the intersection of normal subgroups is a normal subgroup.

Lemma (normal subgroup intersections)

Let $ \{N_i\}_{i \in I}$ be normal subgroups of a group of $G$, then $ \bigcap_{i \in I} N_i $ is a normal subgroup of $G$.

Definition (subgroup generated by a set)

Let $ X \leq G $ be a subset of elements of a group, $G$, then $ < X > := \bigcap\limits_{ X \subseteq H \leq G} {H} $. That is, it is the intersection of all of the subgroups of $G$ which contain all of $X$. By the above lemma, it is a subgroup and by definition, it contains all of $X$.

If $X = {x_1, x_2, … } $, sometimes $ < X > $ is written as $ <x_1, x_2, … > $. We especially use that notation when $X$ has only a few elements.

Definition (cycle)

A cycle of a permutation, $\pi$ on a set $X$ is an orbit, $ Orb_{<\pi>}(x) $, of some $x \in X$, under the action of the group of permutations $ <\pi> $.

Notice that $ < \pi > $ is just equal to all of the positive and negative “powers” of $ \pi $. That is, it is equal to $ \{ \pi^k \}_{i = -\infty}^{i=\infty}$. Also notice that if $ \pi^k = \iota $, and $k$ is the least non-negative integer where that happens, then $ \{ \pi^k \}_{i = -\infty}^{i = \infty} $ $ = \{ \iota, \pi, \pi^2, … \pi^{k-1} \}$. We’ll sometimes refer to the orbits generated by the subgroup $ <\pi> $ as $\pi$-orbits.

Definition (cyclic permutation)

A permutation $\pi \in S_{X} $ is cyclic if and only if $ \forall x, y \in (X \setminus fix(\pi)$, $ Orb_{<\pi>}(x) = Orb_{<\pi>}(y) $.

What this says in words is that any two elements of $X$ which aren’t fixed by $ \pi $ are in the same $\pi$-orbit, so there is only one non-trivial $\pi$-orbit.

Notice that the identity permutation, $ \iota $, is trivially cyclic. This is because $ \iota(x) = x $ for all $ x \in X$, so $ fix(\iota) = X$, which means that $ X \setminus fix(\pi) = \emptyset $.

The benefit of using this definition is that it doesn’t depend on notation, and it still works even if the cycle isn’t finite.

Also notice, as we showed before in More Math of Permutations, that for any given $x \not\in fix(\pi) $, where $ \pi $ is a cycle, that, by definition, every other element that isn’t fixed is equal to $ \pi^{l}(x) $ for some $ l $.

Also keep in mind that even if $\pi$ is cyclic, there can be many (even an infinite amount of) orbits. It just means that there’s at most one non-trivial orbit (i.e. at most one orbit has more than one element in it). For example, consider the set $X = \mathbb{N} $ of natural numbers. As we mentioned earlier $\iota$, the identity permutation is cyclic, but each $n \in \mathbb{N} $ belongs to its own orbit, so there’s an infinite number of them. On the other hand, the permutation $ \text{+1}(x) := x + 1$ is also cyclic, and has only one orbit, all of $\mathbb{N}$.

The next theorem we prove is going to be similar to, but more generic than some theorems/lemmas we’ve already proved. The proof should be fairly familiar by now.

Theorem (disjoint orbits)

Let $G$ be a group of permutations on the set $X$. Then for any two $x$ and $y$ in $X$, we have either $Orb_{G}(x) = Orb_{G}(y) $, or $Orb_{G}(x) \cap Orb_{G}(y) = \emptyset $.

Proof

Suppose $a \in Orb_{G}(x) \cap$ $Orb_{G}(y) $. Then $ a = g_1(x) $ and $ a = g_2(y) $, for some $g_1$, $g_2 \in G$. This means that $ x = g_1^{-1}(a)$, and thus $ x = g_1^{-1}( g_2(y) ) $. Now let $z$ be any element of $Orb_{G}(x) $, then $ z = g_3(x) $, for some $g_3 \in G$. Combining all of this gives us \[ z = g_3 ( g_1^{-1} ( g_2 (y) ) ) \]

This means that $z \in Orb_{G}(y) $. Thus $ Orb_{G}(x) \subseteq Orb_{G}(y) $. A similar argument shows that $ Orb_{G}(x) \supseteq Orb_{G}(y) $, so they are equal.

QED

Notice that we needed the set of permutations to be a group to guarantee that inverses and function composition worked.

So, for any permutation, we have shown that it’s cycles are the orbits under the group generated by itself. This reaffirms what we showed earlier that a permutation’s cycles were disjoint or equal. Now we see that this is still the case, even if the cycles aren’t finite. The result also doesn’t depend on notation.

We also see that every permutation is composed of disjoint cycles. The means that each permutation $\pi$ can be decomposed as the composition of disjoint cyclic permutations. I.e. $ \pi = … \circ \sigma_n \circ … \circ \sigma_2 \circ \sigma_1 $, where each $\sigma_i $ is cyclic. We can do this by setting $ \sigma_i(x) = \pi(x) $, if $ x $ is in $X$’s $i^{th} $ orbit, and $\sigma_i(x) = x$ otherwise. Notice also that for all $i$, $j$, we have $ \sigma_i \circ \sigma_j = \sigma_j \circ \sigma_i $, because they act non-trivially in non-overlapping subsets of $X$.

Breaking a permutation down into disjoint cycles can be helpful in calculating $Sign(\pi) $, since, as we showed in More Math of Permutations, a cyclic permutation whose cycle has length $k$ has $Sign = (-1)^{k-1}$. We’ll use this fact near the end of this entry.

Lemma (stabilizer is a subgroup)

Let $G$ be a group of permutations on the set $X$. Then for any $x \in X$, $Stab_{G}(x) \leq G$.

This means that if the set of permutations is a group, then the stabilizer of any element of $X$ is a subgroup of $G$.

Proof

Let $ a $, and $b$ be two elements of $Stab_{G}(x)$. Recall that the stabilizer of an element of $X$ is a subset of permutations, so $a$ and $b$ are elements of $G$. Then $a(x) = x$, and $b(x) = x$, so we also have $ b^{-1}(x) = x$, and then finally, $a (b^{-1}(x)) = x$, so $a \cdot b^{-1} \in Stab_G(x) $, thus it is a subgroup.

QED

Theorem (orbit stabilizer)

Let $G$ be a finite group of permutations on the finite set $X$. Let $x \in X$ be any element of $X$. Then $ | Orb_{G}(x) | \cdot | Stab_{G}(x) | = | G | $.

Proof

Let’s represent the set of permutations in $G$ as the disjoint union of the cosets of $Stab_G(x) $. I.e.

$$ \begin{align} G = &\{ \iota Stab_G(x), g_2 Stab_G(x), \\ &… g_n Stab_G(x) \} \\ \end{align} $$

Where, $ \iota $ is the identity permutation, and the $g_i$’s are different coset representatives. It’s clear that by the definition of $Stab_G(x) $, each coset sends $x$ to the same element (i.e. every permutation in the coset $g_i Stab_G(x) $ sends $x$ to $ g_i(x) $). Now what’s left is to show that no two cosets send $x$ to the same element.

Suppose, that there are two cosets that send $x$ to the same element, say, $y$. Then $ g_i(x) = g_j(x) = y$, which means that $g_i^{-1}(y) = x $, so $ g_i^{-1}(g_j(x)) = x$, and $ g_i^{-1} \circ g_j \in Stab_G(x) $. This means that $ g_i^{-1} \circ g_j Stab_{G}(x) = Stab_G(x)$, so applying $g_i $ to every element of $Stab_G(x) $ and $ g_i^{-1} \circ g_j Stab_G(x) $ shows us that

\[ g_j Stab_G(x) = g_i Stab_G(x) \]

which means that $g_i$ and $g_j$ didn’t represent two distinct cosets, so $ i = j $. This means that

\[ | Orb_G(x) | = (G : Stab_G(x) ) \]

which gives us our desired result.

QED

Corollary (orbits at most as big as the order of the permutation):

Let $ \pi $ be a permutation of the set $X$, such that $ \pi^k = \iota $, the identity permutation. Then for every $x \in X$, $ |Orb_{<\pi>}(x)| \leq k $. In words, this means that if $ \pi^k $ is the identity permutation, then all of the orbits of $ \pi $ have at most $ k$ elements in them.

Proof

By the orbit stabilizer theorem, the size of the orbit can be at most as large as $ < \pi > $, the group generated by the permutation $ \pi $. That group is no larger than $k$, since $ \pi^k = \iota $.

QED

Now we prove a nice little result.

Corollary (2*odd has normal subgroup)

Let $G$ be a group with $ 2 (2 k + 1) $ elements, then there is a normal subgroup of index $2$.

Proof

In the entry Applying Permutations to Group Theory we showed that we can get the desired result by showing that there is an element $g \in G$, such that $Sign(g) = -1$.

First we show that because $G$ has an even number of elements, there is an element of order $2$, i.e. there is a $e \neq g \in G$, such that $g^2 = e $. Notice that for any $g \in G$, we have $ (g^{-1})^{-1} = g $, which means that all of the elements of $G$ can be uniquely placed in pairs with their inverses. However, some elements are their own inverse – the identity is always its own inverse, for example. So, some of these “pairs” actually only have one element. If no element has order $2$, then all of the pairs except for the identity element must have two distinct elements in them. However, this isn’t possible, since $G$ has an even number of elements, and when we take away the identity element, we have an odd number of elements of $G$ to form pairs with. Thus, whenever $G$ has an even number of elements, there must be an element, which is not the identity which is its own inverse.

Let $e \neq g \in G$ be its own inverse.

We’ve shown that $G$ can be viewed as a subgroup of the group of permutations of its elements (Cayley’s Theorem, also proved in Applying Permutations to Group Theory). So, $g$ as a permutation of the elements of $G$ can be broken down into disjoint cycles. Each cycle has size $ \leq 2$. We want to show that each cycle has exactly two elements in it.

Suppose for a contradiction that $h \in G$ has an orbit of size $1$, then $g \cdot h = h$, but that means that $g = e$, the identity element of $G$ and by our choice of $g$ we made sure that it isn’t the identity element. Thus $g$ as a permutation of the elements of $G$ can be factored into disjoint 2-cycles. Each cycle acting on a distinct pair of elements of $G$. Thus there must be exactly $2 k + 1$ of them.

We showed in More Math of Permutations that every 2-cycle has $Sign = -1$, so since $g$ is the composition of $2 k + 1$ 2-cycles, we have $Sign(g) = (-1)^{2k + 1} = -1 $. This gives us our result.

QED