View source for Abstract Algebra/Group Theory/Group actions on sets

Interesting in it's own right, group actions are a useful tool in algebra and will permit us to prove the Sylow theorems, which in turn will give us a toolkit to describe certain groups in greater detail.

== Basics ==

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Definition 1.8.1''':

Let <math>X</math> be an ''arbitrary'' set, and let <math>G</math> be a group. A function
:<math>f: G \times X \to X</math>
is called '''group action''' by <math>G</math> on <math>X</math> if and only if (<math>\iota</math> denoting the identity of <math>G</math>)
#<math>\forall x \in X : f(\iota, x) = x</math> and
#<math>\forall \sigma, \tau \in G, x \in X: f(\sigma, f(\tau, x)) = f(\sigma \tau, x)</math>.}}

When a certain group action is given in a context, we follow the prevalent convention to write simply <math>\sigma x</math> for <math>f(\sigma, x)</math>. In this notation, the requirements for a group action translate into
#<math>\forall x \in X : \iota x = x</math> and
#<math>\forall \sigma, \tau \in G, x \in X: \sigma (\tau x) = (\sigma \tau) x</math>.

There is a one-to-one correspondence between group actions of <math>G</math> on <math>X</math> and homomorphisms <math>G \to S_X</math>.

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Definition 1.8.2''':

Let <math>G</math> be a group and <math>X</math> a set. Given a homomorphism <math>\varphi: G \to S_X</math>, we may define a corresponding group action by
:<math>\sigma x := \varphi(\sigma)(x)</math>.
If we are given a group action <math>G \times X \to X</math>, then
:<math>\varphi(\sigma) := x \mapsto \sigma x</math>
is a homomorphism. The thus defined correspondence between homomorphisms <math>G \to S_X</math> and group actions <math>G \times X \to X</math> is a bijective one.}}

'''Proof''':

1.

Indeed, if <math>\varphi: G \to S_X</math> is a homomorphism, then
:<math>\iota x = \varphi(\iota)(x) = \text{Id}(x) = x</math> and
:<math>\sigma (\tau x) = \varphi(\sigma)(\varphi(\tau)(x)) = (\varphi(\sigma) \circ \varphi(\tau)) (x) = (\sigma \tau)(x)</math>.

2.

<math>\varphi(\sigma)</math> is bijective for all <math>\sigma \in G</math>, since
:<math>\varphi(\sigma)(x) = \varphi(\sigma)(y) \Leftrightarrow \sigma x = \sigma y \Leftrightarrow \sigma^{-1} \sigma x = \sigma^{-1} \sigma y</math>.
Let also <math>\tau \in G</math>. Then
:<math>\varphi(\sigma \tau) = x \mapsto (\sigma \tau) x = x \mapsto \sigma(\tau(x)) = (x \mapsto \sigma x) \circ (x \mapsto \tau x) = \varphi(\sigma) \circ \varphi(\tau)</math>.

3.

We note that the constructions treated here are inverse to each other; indeed, if we transform a homomorphism <math>\varphi: G \to S_X</math> to an action via
:<math>\sigma x := \varphi(\sigma)(x)</math>
and then turn this into a homomorphism via
:<math>\psi: G \to S_X, \psi(\sigma) := x \mapsto \sigma x</math>,
we note that <math>\psi = \phi</math> since <math>\psi(\sigma) = x \mapsto \sigma x = x \mapsto \varphi(\sigma)(x) = \varphi(\sigma)</math>.

On the other hand, if we start with a group action <math>G \times X \to X</math>, turn that into a homomorphism
:<math>\varphi(\sigma) := x \mapsto \sigma x</math>
and turn that back into a group action
:<math>\sigma x := \varphi(\sigma)(x)</math>,
then we ended up with the same group action as in the beginning due to <math>\varphi(\sigma)(x) = \sigma x</math>.{{QED}}

'''Examples 1.8.3''':
#<math>S_n</math> acts on <math>\mathbb R^n</math> via <math>\sigma (x_1, \ldots, x_n) = (x_{\sigma(1)}, \ldots, x_{\sigma(n)})</math>.
#<math>GL_n(\mathbb R)</math> acts on <math>\mathbb R^n</math> via matrix multiplication: <math>A x := A x</math>, where the first juxtaposition stands for the group action definition and the second for matrix multiplication.

== Types of actions ==

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Definitions 1.8.4''':

A group action <math>G \times X \to X</math> is called
# '''faithful''' iff <math>(\forall x \in X: \sigma x = \tau x) \Rightarrow \sigma = \tau</math> ('identity on all elements of <math>x</math> enforces identity on <math>G</math>')
# '''free''' iff <math>(\exists x \in X: \sigma x = \tau x) \Rightarrow \sigma = \tau</math> ('different group elements map an <math>x</math> to different elements of <math>X</math>'), and
# '''transitive''' iff for all <math>x, y \in X</math> there exists <math>\sigma \in G</math> such that <math>y = \sigma x</math>.}}

Subtle analogies to real life become apparent if we note that an action is faithful if and only if for two distinct <math>\sigma \neq \tau \in G</math> there exist <math>x \in X</math> such that <math>\sigma x \neq \tau x</math>, and it is free if and only if the elements <math>\sigma x, \sigma \in G</math> are all different for all <math>x \in X</math>.

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Theorem 1.8.5''':

A free operation on a nonempty set is faithful.}}

'''Proof''': <math>(\forall x \in X: \sigma x = \tau x) \Rightarrow (\exists x \in X: \sigma x = \tau x) \Rightarrow \sigma = \tau</math>.{{QED}}

We now attempt to characterise these three definitions; i.e. we try to find conditions equivalent to each.

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Theorem 1.8.6''':

A group action <math>G \times X \to X</math> is faithful if and only if the induced homomorphism <math>\varphi: G \to S_X</math> is injective.}}

'''Proof''':

Let first a faithful action <math>G \times X \to X</math> be given. Assume <math>\varphi(\sigma) = \varphi(\tau)</math>. Then for all <math>x \in X</math> <math>\sigma x = \varphi(\sigma)(x) = \varphi(\tau)(x) = \tau x</math> and hence <math>\sigma = \tau</math>. Let now <math>\varphi</math> be injective. Then <math></math>.

An important consequence is the following

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Corollary 1.8.7 (Cayley)''':

Every group is isomorphic to some subgroup of a symmetric group.}}

'''Proof''':

A group acts on itself faithfully via left multiplication. Hence, by the previous theorem, there is a monomorphism <math>G \to S_G</math>.{{QED}}

For the characterisation of the other two definitions, we need more terminology.

== Orbit and stabilizer ==

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Definitions 1.8.8''':

Let <math>G \times X \to X</math> be a group action, and let <math>x \in X</math>. Then
* <math>G(x) := \{\sigma x|\sigma \in G\}</math> is called the '''orbit of <math>x</math>''' and
* <math>G_x := \{\sigma \in G| \sigma x = x\}</math> is called the '''stabilizer of <math>x</math>'''. More generally, for a subset <math>Y \subseteq X</math> we define <math>G_Y := \{\sigma \in G | \forall y \in Y: \sigma y \in Y\}</math> as the '''stabilizer of <math>Y</math>'''.}}

Using this terminology, we obtain a new characterisation of free operations.

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Theorem 1.8.9''':

An operation <math>G \times X \to X</math> is free if and only if <math>G_x</math> is trivial for each <math>x \in X</math>.}}

'''Proof''': Let the operation be free and let <math>x \in X</math>. Then
:<math>\sigma \in G_x \Leftrightarrow \sigma x = x = \iota x</math>.
Since the operation is free, <math>\sigma = \iota</math>.

Assume that for each <math>x \in X</math>, <math>G_x</math> is trivial, and let <math>y \in X</math> such that <math>\sigma y = \tau y</math>. The latter is equivalent to <math>\tau^{-1} \sigma y = y</math>. Hence <math>\tau^{-1} \sigma \in G_y = \{\iota\}</math>.{{QED}}

We also have a new characterisation of transitive operations using the orbit:

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Theorem 1.8.10''':

An operation <math>G \times X \to X</math> is transitive if and only if for all <math>x \in X</math> <math>G(x) = X</math>.}}

'''Proof''':

Assume for all <math>x \in X</math> <math>G(x) = X</math>, and let <math>y, z \in X</math>. Since <math>G(y) = X \ni z</math> transitivity follows.

Assume transitivity, and let <math>x \in X</math>. Then for all <math>y \in X</math> there exists <math>\sigma \in G</math> with <math>\sigma x = y</math> and hence <math>y \in G(x)</math>.{{QED}}

Regarding the stabilizers we have the following two theorems:

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Theorem 1.8.11''':

Let <math>G \times X \to X</math> be a group action and <math>x \in X</math>. Then <math>G_x \le G</math>.}}

'''Proof''':

First of all, <math>\iota \in G_x</math>. Let <math>\sigma, \tau \in G_x</math>. Then <math>(\sigma \tau)x = \sigma (\tau x) = \sigma x = x</math> and hence <math>\sigma \tau \in G_x</math>. Further <math>\sigma^{-1} x = \sigma^{-1} \sigma x = x</math> and hence <math>\sigma^{-1} \in G_x</math>.{{QED}}

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Theorem 1.8.12''':

Let <math>Y \subseteq X</math>. If we write <math>\sigma Y := \{\sigma y|y\in Y\}</math> for each <math>\sigma \in G</math>, then
:<math>G_{\sigma Y} = \sigma G_Y \sigma^{-1}</math>.}}

'''Proof''':

:<math>\begin{align}
\tau \in G_{\sigma Y} & \Leftrightarrow \tau \sigma Y = \sigma Y \\
& \Leftrightarrow \sigma^{-1} \tau \sigma Y = Y \\
& \Leftrightarrow \sigma^{-1} \tau \sigma Y \in G_Y \\
& \Leftrightarrow \tau \in \sigma G_Y \sigma^{-1}
\end{align}</math>{{QED}}

== Cardinality formulas ==

The following theorem will imply formulas for the cardinalities of <math>G_x</math>, <math>|G|</math>, <math>(G:G_x)</math> or <math>X</math> respectively.

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Theorem 1.8.13''':

Let an action <math>G \times X \to X</math> be given. The relation <math>x \sim y :\Leftrightarrow \exists \sigma \in G : \sigma x = y</math> is an equivalence relation, whose equivalence classes are given by the orbits of the action. Furthermore, for each <math>x \in X</math> the function
:<math>\{\sigma G_x | \sigma \in G\} \to G(x), \sigma G_x \mapsto \sigma x</math>
is a well-defined, bijective function.}}

'''Proof''':

1.

* Reflexiveness: <math>\iota x = \iota</math>
* Symmetry: <math>\sigma x = y \Leftrightarrow x = \sigma^{-1} y</math>
* Transitivity: <math>\sigma x = y \wedge \tau y = z \Rightarrow (\tau \sigma) x = z</math>.

2.

Let <math>[x]</math> be the equivalence class of <math>x</math>. Then
:<math>y \in [x] \Leftrightarrow \exists \sigma \in G: \sigma x = y \Leftrightarrow y \in G(x)</math>.

3.

Let <math>\sigma G_x = \tau G_x</math>. Since <math>G_x \le G</math>, <math>\tau^{-1} \sigma \in G_x</math>. Hence, <math>\tau^{-1} \sigma x = x \Leftrightarrow \tau x = \sigma x</math>. Hence well-definedness. Surjectivity follows from the definition. Let <math>\sigma x = \tau x</math>. Then <math>\tau^{-1} \sigma x = x</math> and thus <math>\tau^{-1} \sigma G_x = G_x</math>. Hence injectivity.{{QED}}

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Corollary 1.8.14 (the orbit-stabilizer theorem)''':

Let an action <math>G \times X \to X</math> be given, and let <math>x \in X</math>. Then
:<math>|G(x)| = (G:G_x)</math>, or equivalently <math>|G(x)| \cdot |G_x|=|G|</math>.}}

'''Proof''': By the previous theorem, the function <math>\{\sigma G_x | \sigma \in G\} \to G(x), \sigma G_x \mapsto \sigma x</math> is a bijection. Hence, <math>(G:g_x) = |G(x)|</math>. Further, by Lagrange's theorem <math>(G:G_x) = \frac{|G|}{|G_x|}</math>.{{QED}}

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Corollary 1.8.15 (the orbit equation)''':

Let an action <math>G \times X \to X</math> be given, and let <math>G(x_1), \ldots, G(x_n)</math> be a complete and unambiguous list of the orbits. Then
:<math>|X| = \sum_{j=1}^n \left|G\left(x_j\right)\right| = \sum_{j=1}^n (G:G_{x_j})</math>.}}

'''Proof''': The first equation follows immediately from the equivalence classes of the relation from theorem 1.8.13 partitioning <math>X</math>, and the second follows from Corollary 1.8.14.{{QED}}

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Corollary 1.8.16''':

Let an action <math>G \times X \to X</math> be given, let <math>Z=\{x\in X | \forall \sigma \in G : \sigma x=x\}</math>, and let <math>G(x_1), \ldots, G(x_m)</math> be a complete and unabiguous list of all nontrivial orbits (where the orbit of <math>x \in X</math> is said to be trivial iff <math>G(x) = \{x\}</math>). Then
:<math>|X| = |Z| + \sum_{j=1}^m \left|G\left(x_j\right)\right|</math>.}}

'''Proof''': This follows from the previous Corollary and the fact that <math>|Z|</math> equals the sum of the cardinalities the trivial orbits.{{QED}}

The following lemma, which is commonly known as ''Burnside's lemma'', is actually due to Cauchy:

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Corollary 1.8.17 (Cauchy's lemma)''':

Let an action <math>G \times X \to X</math> be given, where <math>G, X</math> are finite. For each <math>\sigma \in G</math>, we denote <math></math>.}}

== The class equation ==

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Definition 1.8.18''':

Let a group <math>G</math> act on itself by conjugation, i. e. <math>\sigma x := \sigma x \sigma^{-1}</math> for all <math>\sigma, x \in G</math>. For each <math>x \in G</math>, the '''centraliser''' of <math>x</math> is defined to be the set
:<math>\mathcal C_G(x) := G_x</math>.}}

Using the machinery we developed above, we may now set up a formula for the cardinality of <math>G</math>. In order to do so, we need a preliminary lemma though.

'''Lemma 1.8.19''':

Let <math>G</math> act on itself by conjugation, and let <math>x \in G</math>. Then the orbit of <math>x</math> is trivial if and only if <math>x \in Z(G)</math>.

'''Proof''': <math>x \in Z(G) \Leftrightarrow \forall \sigma \in G : \sigma x \sigma^{-1} = x \Leftrightarrow G(x) = \{x\}</math>.{{QED}}

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Corollary 1.8.20 (the class equation)''':

Let <math>G</math> be a group acting on itself by conjugation, and let <math>G(x_1), \ldots, G(x_m)</math> be a complete and unambiguous list of the non-trivial orbits of that action. Then
:<math>|G| = |Z(G)| + \sum_{j=1}^m (G : \mathcal C_G(x_j))</math>.}}

'''Proof''': This follows from lemma 1.8.19 and Corollary 1.8.16.{{QED}}

== Special topics ==

=== Equivariant functions ===

A set together with a group acting on it is an algebraic structure. Hence, we may define some sort of morphisms for those structures.

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Definition 1.8.21''':

Let a group <math>G</math> act on the sets <math>X</math> and <math>Y</math>. A function <math>f: X \to Y</math> is called '''equivariant''' iff
:<math>\forall \sigma \in G, x \in X: \sigma f(x) = f(\sigma x)</math>.}}

'''Lemma 1.8.22''':

=== p-groups ===

We shall now study the following thing:

{{TextBox| M=0 | W=100% | BG=#FFFFFF |1='''Definition 1.8.24''':

Let <math>p</math> be a prime number. If <math>G</math> is a group such that <math>|G| = p^k</math> for some <math>k \in \mathbb N</math>, then <math>G</math> is called a '''<math>p</math>-group'''.}}

'''Corollary 23:''' Let <math>G</math> be a <math>p</math>-group acting on a set <math>S</math>. Then <math>|S|\equiv |Z|\ \mathrm{mod}\ p</math>.

''Proof'': Since <math>G</math> is a <math>p</math>-group, <math>p</math> divides <math>|G*a|</math> for each <math>a\in A</math> with <math>A</math> defined as in Lemma 21. Thus <math>\sum_{a\in A}|G*a|\equiv 0\ \mathrm{mod}\ p</math>. {{Unicode|∎}}

=== Group Representations ===

Linear group actions on vector spaces are especially interesting. These have a special name and comprise a subfield of group theory on their own, called ''group representation theory''.　We will only touch slightly upon it here.

'''Definition 24:''' Let <math>G</math> be a group and <math>V</math> be a vector space over a field <math>F</math>. Then a ''representation'' of <math>G</math> on <math>V</math> is a map <math>\Phi\,:\, G\times V\rightarrow V</math> such that

:i) <math>\Phi(g)\,:\, V\rightarrow V</math> given by <math>\Psi(g)(v)=\Psi(g,v)</math>, <math>v\in V</math>, is linear in <math>v</math> over <math>F</math>.

:ii) <math>\Phi(e,v)=v</math>

:iii) <math>\Phi\left(g_1,\Phi(g_2,v)\right)=\Phi(g_1g_2,v)</math> for all <math>g_1,g_2\in G</math>, <math>v\in V</math>.

V is called the ''representation space'' and the dimension of <math>V</math>, if it is finite, is called the ''dimension'' or ''degree'' of the representation.

'''Remark 25:''' Equivalently, a representation of <math>G</math> on <math>V</math> is a homomorphism <math>\phi\,:\, G\rightarrow GL(V,F)</math>. A representation can be given by listing <math>V</math> and <math>\phi</math>, <math>(V,\phi)</math>.

As a representation is a special kind of group action, all the concepts we have introduced for actions apply for representations.

'''Definition 26:''' A representation of a group <math>G</math> on a vector space <math>V</math> is called ''faithful'' or ''effective'' if <math>\phi\,:\, G\rightarrow GL(V,F)</math> is injective.

== Exercises ==

{{BookCat}}