Group Action
Starting from Rubik’s Cube. Visualization of Rubik’s Cube
Group Action on a Set
Given a group $G$ and a set $X$ with the mapping $G\times X \to X$, denoting the mapping of $(g, x)$ under the mapping as $g\cdot x$. If there exists $e\in G$ so that $e\cdot x = x$, and $g_1\cdot (g_2\cdot x) = (g_1g_2)\cdot x$ for any $g_1,g_2\in G, x\in X$, then the mapping is a (left) group action for group $G$ on the set $X$. The mapping can also be written as $gx$.
Orbit
Given a group action $G$ on the set $X$. Assume an element $x\in X$. $Gx=\{gx\mid g\in G\}$ is the orbit for $x$.
Stablizer
Given the group action for group $G$ over the set $X$. Denote $G_x = \{g\in G \mid gx = x\}$ as the the stablizer for group $G$ at $x$, which is a subgroup of $G$, i.e. $G_x \le G$.
Proof. $G_x = \{g\in G \mid gx = x\}$ is a subset of $G$. Thus, the associativity is satisfied. Still need to prove the closure of the binary operation $\cdot$, the existence of identity and inverse for each element.
- Closure: For any $g_1,g_2 \in G_x$, i.e. $g_1x=g_2x=x$, we have $(g_1\cdot g_2) x = g_1 (g_2 x) = g_1 x = x$, i.e. $g_1\cdot g_2 \in G_x$.
- Identity: The identity $e\in G$ satisfies $e x = x$ , i.e. $e \in G_x$.
- Inverse: For any $g \in G_x$, i.e. $gx = x$, consider its inverse $g^{-1}$ in $G$, then $g^{-1}x = g^{-1} (gx) = (g^{-1} \cdot g) x = e x = x$, i.e. $g^{-1} \in G_x$. Therefore, $G_x$ is a subgroup of $G$.
$\square$
Orbit-Stablizer Theorem
Consider the group action for finite group $G$ over the set $X$. Assume $x\in X$. Then $|Gx| = [G : G_x] = |G| / |G_x|$.
Proof. Actually, there exists a bijective mapping between $Gx \times G_x$ and $G$.
Forward Direction Consider any $y \in Gx, h \in G_x$. By definition, $hx = x$. By definition, there exists possibly multiple $g \in G$ s.t. $gx = y$. For each $y$, select one representative $g_y$. Then, $(g_y \cdot h) x = g_y (hx) = g_y x = y$ for $g_y\cdot h \in G$.
Backward Direction Consider any $g \in G$. Let $y = gx \in Gx$. There exists a representative $g_y \in G$ with $g_y x = y$. Let $h = g_y^{-1} \cdot g \in G$. Then, $(g_y \cdot h) x = [(g_y \cdot g_y^{-1}) \cdot g] x = gx = y$. And, $h x = [(g_y^{-1} \cdot g_y) \cdot h] x = g_y^{-1} [(g_y\cdot h) x] = g_y^{-1} y = (g_y^{-1} \cdot g_y) x = x$, i.e. $h \in G_x$.
Therefore, $|Gx|\times |G_x| = |Gx \times G_x| = |G|$.
$\square$
Stationary Points
Consider the group action for finite group $G$ over the set $X$. For any $g\in G$, $X^g = \{x\in X \mid gx = x\}$ is its corresponding set of stationary points.
Burnside Lemma
Consider the group action for finite group $G$ over the set $X$. The number of orbits equals to the average number of stationary points for all elements $g\in G$. $|X/G| = \frac{1}{|G|} \sum\limits_{g\in G} |X^g|$.
Proof. It is an application of a common trick, switching the sum order.
$|X / G| = \sum\limits_{x \in X} \frac{1}{|Gx|}= \sum\limits_{x \in X} \frac{|G_x|}{|G|} = \sum\limits_{x \in X} \frac{1}{|G|} \sum\limits_{g\in G} \mathbb{I}(gx = x) = \frac{1}{|G|} \sum\limits_{g\in G} \sum\limits_{x \in X} \mathbb{I}(gx = x) = \frac{1}{|G|} \sum\limits_{g\in G} |X^g|$.
$\square$
Polya Counting Principle (Coloring Problem)
…