section-groups-acting-on-sets.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section14.1Groups Acting on Sets

¶

Let $X$ be a set and $G$ be a group. A of $G$ on $X$ is a map $G \times X \rightarrow X$ given by $(g,x) \mapsto gx\text{,}$ where

1. $ex = x$ for all $x \in X\text{;}$

2. $(g_1 g_2)x = g_1(g_2 x)$ for all $x \in X$ and all $g_1, g_2 \in G\text{.}$

Under these considerations $X$ is called a . Notice that we are not requiring $X$ to be related to $G$ in any way. It is true that every group $G$ acts on every set $X$ by the trivial action $(g,x) \mapsto x\text{;}$ however, group actions are more interesting if the set $X$ is somehow related to the group $G\text{.}$

Example14.1

Let $G = GL_2( {\mathbb R} )$ and $X = {\mathbb R}^2\text{.}$ Then $G$ acts on $X$ by left multiplication. If $v \in {\mathbb R}^2$ and $I$ is the identity matrix, then $Iv = v\text{.}$ If $A$ and $B$ are $2 \times 2$ invertible matrices, then $(AB)v = A(Bv)$ since matrix multiplication is associative.

Example14.2

Let $G = D_4$ be the symmetry group of a square. If $X = \{ 1, 2, 3, 4 \}$ is the set of vertices of the square, then we can consider $D_4$ to consist of the following permutations:

$$\begin{equation*} \{ (1), (13), (24), (1432), (1234), (12)(34), (14)(23), (13)(24) \}. \end{equation*}$$

The elements of $D_4$ act on $X$ as functions. The permutation $(13)(24)$ acts on vertex 1 by sending it to vertex 3, on vertex 2 by sending it to vertex 4, and so on. It is easy to see that the axioms of a group action are satisfied.

In general, if $X$ is any set and $G$ is a subgroup of $S_X\text{,}$ the group of all permutations acting on $X\text{,}$ then $X$ is a $G$-set under the group action

$$\begin{equation*} (\sigma, x) \mapsto \sigma(x) \end{equation*}$$

for $\sigma \in G$ and $x \in X\text{.}$

Example14.3

If we let $X = G\text{,}$ then every group $G$ acts on itself by the left regular representation; that is, $(g,x) \mapsto \lambda_g(x) = gx\text{,}$ where $\lambda_g$ is left multiplication:

$$\begin{gather*} e \cdot x = \lambda_e x = ex = x\\ (gh) \cdot x = \lambda_{gh}x = \lambda_g \lambda_h x = \lambda_g(hx) = g \cdot ( h \cdot x). \end{gather*}$$

If $H$ is a subgroup of $G\text{,}$ then $G$ is an $H$-set under left multiplication by elements of $H\text{.}$

Example14.4

Let $G$ be a group and suppose that $X=G\text{.}$ If $H$ is a subgroup of $G\text{,}$ then $G$ is an $H$-set under ; that is, we can define an action of $H$ on $G\text{,}$

$$\begin{equation*} H \times G \rightarrow G, \end{equation*}$$

via

$$\begin{equation*} (h,g) \mapsto hgh^{-1} \end{equation*}$$

for $h \in H$ and $g \in G\text{.}$ Clearly, the first axiom for a group action holds. Observing that

$$\begin{align*} (h_1 h_2, g) & = h_1 h_2 g (h_1 h_2 )^{-1}\\ & = h_1( h_2 g h_2^{-1}) h_1^{-1}\\ & = (h_1, (h_2, g) ), \end{align*}$$

we see that the second condition is also satisfied.

Example14.5

Let $H$ be a subgroup of $G$ and ${\mathcal L}_H$ the set of left cosets of $H\text{.}$ The set ${\mathcal L}_H$ is a $G$-set under the action

$$\begin{equation*} (g, xH) \mapsto gxH. \end{equation*}$$

Again, it is easy to see that the first axiom is true. Since $(g g')xH = g( g'x H)\text{,}$ the second axiom is also true.

If $G$ acts on a set $X$ and $x, y \in X\text{,}$ then $x$ is said to be to $y$ if there exists a $g \in G$ such that $gx =y\text{.}$ We write $x \sim_G y$ or $x \sim y$ if two elements are $G$-equivalent.

Proposition14.6

Let $X$ be a $G$-set. Then $G$-equivalence is an equivalence relation on $X\text{.}$

Proof

The relation $\sim$ is reflexive since $ex = x\text{.}$ Suppose that $x \sim y$ for $x, y \in X\text{.}$ Then there exists a $g$ such that $gx = y\text{.}$ In this case $g^{-1}y=x\text{;}$ hence, $y \sim x\text{.}$ To show that the relation is transitive, suppose that $x \sim y$ and $y \sim z\text{.}$ Then there must exist group elements $g$ and $h$ such that $gx = y$ and $hy= z\text{.}$ So $z = hy = (hg)x\text{,}$ and $x$ is equivalent to $z\text{.}$

If $X$ is a $G$-set, then each partition of $X$ associated with $G$-equivalence is called an of $X$ under $G\text{.}$ We will denote the orbit that contains an element $x$ of $X$ by ${\mathcal O}_x\text{.}$

Example14.7

Let $G$ be the permutation group defined by

$$\begin{equation*} G =\{(1), (1 2 3), (1 3 2), (4 5), (1 2 3)(4 5), (1 3 2)(4 5) \} \end{equation*}$$

and $X = \{ 1, 2, 3, 4, 5\}\text{.}$ Then $X$ is a $G$-set. The orbits are ${\mathcal O}_1 = {\mathcal O}_2 = {\mathcal O}_3 =\{1, 2, 3\}$ and ${\mathcal O}_4 = {\mathcal O}_5 = \{4, 5\}\text{.}$

Now suppose that $G$ is a group acting on a set $X$ and let $g$ be an element of $G\text{.}$ The of $g$ in $X\text{,}$ denoted by $X_g\text{,}$ is the set of all $x \in X$ such that $gx = x\text{.}$ We can also study the group elements $g$ that fix a given $x \in X\text{.}$ This set is more than a subset of $G\text{,}$ it is a subgroup. This subgroup is called the or of $x\text{.}$ We will denote the stabilizer subgroup of $x$ by $G_x\text{.}$

Remark14.8

It is important to remember that $X_g \subset X$ and $G_x \subset G\text{.}$

Example14.9

Let $X = \{1, 2, 3, 4, 5, 6\}$ and suppose that $G$ is the permutation group given by the permutations

$$\begin{equation*} \{ (1), (1 2)(3 4 5 6), (3 5)(4 6), (1 2)( 3 6 5 4) \}. \end{equation*}$$

Then the fixed point sets of $X$ under the action of $G$ are

$$\begin{gather*} X_{(1)} = X,\\ X_{(3 5)(4 6)} = \{1,2\},\\ X_{(1 2)(3 4 5 6)} = X_{(1 2)(3 6 5 4)} = \emptyset, \end{gather*}$$

and the stabilizer subgroups are

$$\begin{gather*} G_1 = G_2 = \{(1), (3 5)(4 6) \},\\ G_3 = G_4 = G_5 = G_6 = \{(1)\}. \end{gather*}$$

It is easily seen that $G_x$ is a subgroup of $G$ for each $x \in X\text{.}$

Proposition14.10

Let $G$ be a group acting on a set $X$ and $x \in X\text{.}$ The stabilizer group of $x\text{,}$ $G_x\text{,}$ is a subgroup of $G\text{.}$

Proof

Clearly, $e \in G_x$ since the identity fixes every element in the set $X\text{.}$ Let $g, h \in G_x\text{.}$ Then $gx = x$ and $hx = x\text{.}$ So $(gh)x = g(hx) = gx = x\text{;}$ hence, the product of two elements in $G_x$ is also in $G_x\text{.}$ Finally, if $g \in G_x\text{,}$ then $x = ex = (g^{-1}g)x = (g^{-1})gx = g^{-1} x\text{.}$ So $g^{-1}$ is in $G_x\text{.}$

We will denote the number of elements in the fixed point set of an element $g \in G$ by $|X_g|$ and denote the number of elements in the orbit of $x \in X$ by $|{\mathcal O}_x|\text{.}$ The next theorem demonstrates the relationship between orbits of an element $x \in X$ and the left cosets of $G_x$ in $G\text{.}$

Theorem14.11

Let $G$ be a finite group and $X$ a finite $G$-set. If $x \in X\text{,}$ then $|{\mathcal O}_x| = [G:G_x]\text{.}$

Proof

We know that $|G|/|G_x|$ is the number of left cosets of $G_x$ in $G$ by Lagrange's Theorem (Theorem 6.10). We will define a bijective map $\phi$ between the orbit ${\mathcal O}_x$ of $X$ and the set of left cosets ${\mathcal L}_{G_x}$ of $G_x$ in $G\text{.}$ Let $y \in {\mathcal O}_x\text{.}$ Then there exists a $g$ in $G$ such that $g x = y\text{.}$ Define $\phi$ by $\phi( y ) = g G_x\text{.}$ To show that $\phi$ is one-to-one, assume that $\phi(y_1) = \phi(y_2)\text{.}$ Then

$$\begin{equation*} \phi(y_1) = g_1 G_x = g_2 G_x = \phi(y_2), \end{equation*}$$

where $g_1 x = y_1$ and $g_2 x = y_2\text{.}$ Since $g_1 G_x = g_2 G_x\text{,}$ there exists a $g \in G_x$ such that $g_2 = g_1 g\text{,}$

$$\begin{equation*} y_2 = g_2 x = g_1 g x = g_1 x = y_1; \end{equation*}$$

consequently, the map $\phi$ is one-to-one. Finally, we must show that the map $\phi$ is onto. Let $g G_x$ be a left coset. If $g x = y\text{,}$ then $\phi(y) = g G_x\text{.}$