Introduction to Groups

All of this course will be focused on concepts related to groups, one of the most important unifying ideas in mathematics. The group concept was implicit in mathematics for a long time — arguably from the introduction of negative numbers. It was a French teenager, Evariste Galois (1831), who first defined a group and gave it a name, writing up the sum total of his ideas in a long letter the night before he died in a duel to defend the honor of a sex worker. As you’ll soon see, the definition of a group is fairly simple. I think of groups as sitting fairly low down within the structure of mathematics. This means they are foundational — knowing more about groups tells you about all the objects that build upon them.

Group theory today is often described as the theory of symmetry. Some of the largest discoveries in science have been due to framing symmetries in nature in terms of groups. Noether’s theorem says that, in a precise sense, all conservation laws within a physical theory come from symmetries of that theory. For example, one way to phrase the development of special relativity is that physicists identified the correct symmetry group of spacetime — the Lorentz group. Group theory predicted the existence of many elementary particles before they were found experimentally. Several of the most important problems in physics and computer science can be phrased similarly.

The point of this first chapter is not to master every example. The point is to see the shape of the subject early: examples, calculations, subgroups, generators, homomorphisms, isomorphisms, and actions. Later chapters return to all of these ideas in much more detail.

Definitions and first examples

A group consists of two pieces of data: a set $G$, and an associative binary operation $\ast$ with some properties. Before the formal definition, let’s give two examples:

Example

The pair $(\mathbb{Z},+)$ is a group. $\mathbb{Z}=\{\dots ,-2,-1,0,1,2,\dots \}$ is a set and the associative operation is addition. Note that there is a special element $0\in \mathbb{Z}$ that has a special property:

$$a+0=0+a=a\text{for all }a\in \mathbb{Z}.$$

This is called the identity element. Every element $a\in \mathbb{Z}$ has an additive inverse:

$$a+(-a)=(-a)+a=0.$$

Example

Let $\mathbb{Q}-\{0\}$ be the set of nonzero rational numbers. The pair $(\mathbb{Q}-\{0\},\cdot )$ is a group: the set is $\mathbb{Q}-\{0\}$ and the associative operation is multiplication. Again we see the same two nice properties: There is a special element $1\in \mathbb{Q}-\{0\}$ such that

$$a\cdot 1=1\cdot a=a.$$

This is the identity element. For any rational number $x\in \mathbb{Q}-\{0\}$, there is an inverse $1/x$ such that

$$x\cdot x^{-1}=x^{-1}\cdot x=1.$$

Definition

A group is a pair $(G,\ast )$ consisting of a set of elements $G$, and a binary operation $\ast$ on $G$, such that:

• $G$ has an identity element $e$ with the property that $e\ast g=g\ast e=g$ for all $g\in G$.
• The operation $\ast$ is associative, meaning that $(a\ast b)\ast c=a\ast (b\ast c)$ for all $a,b,c\in G$.
• Every element $g\in G$ has an inverse $g^{-1}$, meaning that $g\ast g^{-1}=g^{-1}\ast g=e$.

We’ll denote the size of the group by $|G|$, sometimes called the order of the group. If $|G|$ is finite, we say $G$ is a finite group.

Note that we’ll often refer to the group only by the underlying set $G$ itself, leaving you to infer the operation $\ast$ from context.

Unimportant pedantic point

Some authors like to add a “closure axiom”, i.e. to explicitly say that $g\ast h\in G$. This is implied already by the fact that $\ast$ is a binary operation on $G$.

Example

$\mathbb{Z},\mathbb{Q},\mathbb{R}$ and $\mathbb{C}$ are all groups under addition with $e=0$ and $a^{-1}=-a$, for all $a$.

Example

$\mathbb{Q}-\{0\}$, $\mathbb{R}-\{0\}$, $\mathbb{C}-\{0\}$, ${\mathbb{Q}}^{+}$ and ${\mathbb{R}}^{+}$ are all groups under multiplication with $e=1$ and $a^{-1}=1/a$, for all $a$.

Invertible matrices

Consider the set of all invertible $n\times n$ matrices with real entries, denoted by ${\mathrm{GL}}_n(\mathbb{R})$. This set forms a group under matrix multiplication, known as the general linear group. The identity element is the identity matrix, and the inverse of a matrix $A$ is its inverse $A^{-1}$, which also has real entries. The group operation is associative because matrix multiplication is associative. But wait, is it closed under multiplication? Yes! The product of two invertible matrices is also invertible, and the inverse of the product is given by $(AB{)}^{-1}=B^{-1}{A}^{-1}$, which is also an invertible matrix. Therefore, ${\mathrm{GL}}_n(\mathbb{R})$ satisfies all the group axioms and is indeed a group.

Non-examples of groups

• $\mathbb{Z}-\{0\}$ is not a group under multiplication, since elements like $2$ do not have multiplicative inverses in $\mathbb{Z}-\{0\}$.
• The pair $(\mathbb{Q},\cdot )$ is not a group. While there is an identity element, the element $0\in \mathbb{Q}$ does not have an inverse.
• The natural numbers $\mathbb{N}$ are not a group under addition. There is an identity element, but $3$ has no additive inverse inside $\mathbb{N}$.
• Let ${\text{Mat}}_{2\times 2}(\mathbb{R})$ be the set of $2\times 2$ real matrices. Even though we have an identity matrix

$$\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right],$$

not every matrix has a multiplicative inverse. For example, the zero matrix does not have a multiplicative inverse. Even if you delete the zero matrix from the set, it is still not a group — any matrix with determinant zero cannot have an inverse.

Basic algebra in a group

In a group we can calculate without knowing what the elements actually are. The symbols $a,b,c$ might be integers, matrices, functions, symmetries, or something stranger, but the same algebraic rules still hold.

Proposition

If $G$ is a group under the operation $\ast$, then

• The identity of $G$ is unique.
• For each $a\in G$, $a^{-1}$ is uniquely determined.

Proof

Suppose $f$ and $g$ were both identities. Then $f\ast g=f$ since $g$ is an identity, and $f\ast g=g$ since $f$ is an identity. Thus $f=g$.

Suppose $b$ and $c$ were both inverses of $a$. Then $a\ast b=e$ and $a\ast c=e$. Thus

$$b=b\ast e=b\ast (a\ast c)=(b\ast a)\ast c=e\ast c=c.$$

Therefore we can refer to the identity of $G$ and the inverse of $g$ without ambiguity.

From now on, when the operation is clear, we usually omit the symbol $\ast$ and write $ab$ instead of $a\ast b$. This is called multiplicative notation. When the group operation is addition, we use additive notation: the identity is written $0$, the inverse of $a$ is written $-a$, and the product $a^n$ is written $na$.

Proposition

Let $G$ be a group and let $x,y,a\in G$. Show that the following properties hold:

1. If $ax=ay$, then $x=y$.
2. If $xa=ya$, then $x=y$.
3. $(x^{-1}{)}^{-1}=x$.
4. $(x\ast y{)}^{-1}=(y^{-1})\ast (x^{-1})$.

Proof

Let $e$ be the identity element of $G$.

1. If $ax=ay$, then multiplying on the left by $a^{-1}$ gives $a^{-1}ax=a^{-1}ay$, so $ex=ey$, hence $x=y$.
2. If $xa=ya$, then multiplying on the right by $a^{-1}$ gives $xa{a}^{-1}=ya{a}^{-1}$, so $xe=ye$, hence $x=y$.
3. Since $x^{-1}x=e$ and $x{x}^{-1}=e$, the element $x$ is the inverse of $x^{-1}$. Thus $(x^{-1}{)}^{-1}=x$.
4. We have

$$(x\ast y)\ast (y^{-1}\ast x^{-1})=x\ast (y\ast y^{-1})\ast x^{-1}=x\ast e\ast x^{-1}=e$$

and similarly

$$(y^{-1}\ast x^{-1})\ast (x\ast y)=y^{-1}\ast (x^{-1}\ast x)\ast y=y^{-1}\ast e\ast y=e.$$

Hence $y^{-1}\ast x^{-1}$ is the inverse of $x\ast y$, so $(x\ast y{)}^{-1}=y^{-1}\ast x^{-1}$.

Some notation: if $x\in G$ and $n>0$, we write $x^n$ to denote the element obtained by multiplying $x$ with itself $n$ times:

$$x^n=\underset{n\text{ times}}{\underbrace{x\ast x\ast \cdots \ast x}}.$$

We also set $x^0=e$ and $x^{-n}=(x^{-1}{)}^n$ for $n>0$.

Exercise

Let $G$ be a group and let $x,y\in G$. Show that the following properties hold:

1. $(x^{-1}{)}^n=(x^n{)}^{-1}$.
2. $(x^{-1}yx{)}^n=x^{-1}{y}^{n}x$ for any integer $n\ge 1$.

Exercise

Suppose $G$ is a finite group. For $a\in G$, prove that the functions

$$L_a:G\to G,L_a(x)=ax$$

and

$$R_a:G\to G,R_a(x)=xa$$

are bijections.

Deduce that each row and each column of the multiplication table of $G$ contains every element of $G$ exactly once.

Exercise

We have seen that a group element has a unique inverse. However, group elements need not have a unique square root. By a square root of an element $g$ in a group $G$, we mean an element $h$ such that $h^2=g$.

1. Give an example of an element $g$ in a group $G$ that has no square roots.
2. Give an example of an element $g$ in a group $G$ which has more than one square root.
3. Give an example of an element $g$ in a group $G$ which has infinitely many square roots.
4. Give an example of an element $g$ in a group $G$ which has a unique square root.

Most of the examples so far have had the special property that $a\ast b=b\ast a$ for all $a,b\in G$. This is called commutativity, and it is not a requirement for a group. Groups that do have this property are called abelian groups, after the Norwegian mathematician Niels Henrik Abel.

Definition

A group $G$ is abelian if $\ast$ is commutative, i.e. for all $a,b\in G$ we have $a\ast b=b\ast a$.

Example

The groups $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$, and $\mathbb{C}$ under addition are abelian. The groups ${\mathbb{Q}}^{\times }$, ${\mathbb{R}}^{\times }$, ${\mathbb{C}}^{\times }$, ${\mathbb{Q}}^{+}$, and ${\mathbb{R}}^{+}$ under multiplication are also abelian.

Example

So far, the only example we’ve given of a nonabelian group is ${\mathrm{GL}}_n(\mathbb{R})$. For instance, in ${\mathrm{GL}}_2(\mathbb{R})$,

$$\left[\begin{array}{cc}1& 1\\ 0& 1\end{array}\right]\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]=\left[\begin{array}{cc}2& 1\\ 1& 1\end{array}\right],$$

while

$$\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]\left[\begin{array}{cc}1& 1\\ 0& 1\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 1& 2\end{array}\right].$$

These products are different, so matrix multiplication is not commutative.

Exercise

Prove that if $x^2=1$ for all $x\in G$ then $G$ is abelian.

A first gallery of examples

The next examples will come up a lot. The goal here is exposure: you should know these groups exist and have a rough sense of how they behave. We will return to most of them later.

Addition mod $n$

Here is an example from number theory: Let $n>1$ be an integer, and consider the residues (remainders) modulo $n$. That is, we partition the integers into $n$ equivalence classes:

$$\begin{array}{rl}\overline{0}& =\{a\in \mathbb{Z}|a\equiv 0\mathrm{mod}n\}=\{0,n,-n,2n,-2n,\dots \}\\ \overline{1}& =\{a\in \mathbb{Z}|a\equiv 1\mathrm{mod}n\}=\{1,n+1,-n+1,2n+1,-2n+1,\dots \}\\ & ⋮\\ \overline{n-1}& =\{a\in \mathbb{Z}|a\equiv n-1\mathrm{mod}n\}=\{n-1,2n-1,-1,3n-1,-2n-1,\dots \}.\end{array}$$

These form a group under addition. We call this the cyclic group of order $n$, and denote it as $\mathbb{Z}/n\mathbb{Z}$ with elements $\overline{0},\overline{1},\dots ,\overline{n-1}$. The identity is $\overline{0}$.

Multiplication mod $n$

For $n\in \mathbb{N}$, the set $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ of equivalence classes $\overline{a}$ which have multiplicative inverses mod $n$ is a group under multiplication of classes. The identity element is the element $\overline{1}$ and by definition, each element has a multiplicative inverse. In general, we will use the notation $G^{\times }$ to mean the group of invertible elements of a set.

Sometimes we organize the information of a group into a group table. For example, consider $(\mathbb{Z}/5\mathbb{Z}-\{\overline{0}\},\cdot )=(\mathbb{Z}/5\mathbb{Z}{)}^{\times }$. The group table is as follows:

$$\begin{array}{ccccc}\cdot & \overline{1}& \overline{2}& \overline{3}& \overline{4}\\ \overline{1}& \overline{1}& \overline{2}& \overline{3}& \overline{4}\\ \overline{2}& \overline{2}& \overline{4}& \overline{1}& \overline{3}\\ \overline{3}& \overline{3}& \overline{1}& \overline{4}& \overline{2}\\ \overline{4}& \overline{4}& \overline{3}& \overline{2}& \overline{1}\end{array}$$

You can check this is a group: the identity is $\overline{1}$, every element has an inverse (for example, ${\overline{2}}^{-1}=\overline{3}$), and the operation is associative because multiplication of integers is associative. This, in a sense, contains all information about the group. However, it won’t be a very useful way to organize the information for large groups.

Just for fun, let’s start reasoning through all groups of small order.

1. The only group of order $1$ is the trivial group $\{e\}$, where $e$ is the identity element. That is, up to renaming the group elements, there is only one group of order $1$.

2. The only group of order $2$ is

$$\begin{array}{ccc}\cdot & e& a\\ e& e& a\\ a& a& e\end{array}$$

where $a$ is the non-identity element. The assignments are forced upon you. So up to renaming your group elements, there is only one group of order $2$. Since we already know that $\mathbb{Z}/2\mathbb{Z}$ is a group of order $2$, we can conclude that $\mathbb{Z}/2\mathbb{Z}$ is the only group of order $2$.

3. The only group of order $3$ is

$$\begin{array}{cccc}\cdot & e& a& b\\ e& e& a& b\\ a& a& b& e\\ b& b& e& a\end{array}$$

where $a$ and $b$ are the non-identity elements. The assignments are forced upon you. So up to renaming your group elements, there is only one group of order $3$. Since we already know that $\mathbb{Z}/3\mathbb{Z}$ is a group of order $3$, we can conclude that $\mathbb{Z}/3\mathbb{Z}$ is the only group of order $3$.

4. There are two options for the group of order $4$. The first is the cyclic group $\mathbb{Z}/4\mathbb{Z}$:

$$\begin{array}{ccccc}\cdot & \overline{0}& \overline{1}& \overline{2}& \overline{3}\\ \overline{0}& \overline{0}& \overline{1}& \overline{2}& \overline{3}\\ \overline{1}& \overline{1}& \overline{2}& \overline{3}& \overline{0}\\ \overline{2}& \overline{2}& \overline{3}& \overline{0}& \overline{1}\\ \overline{3}& \overline{3}& \overline{0}& \overline{1}& \overline{2}\end{array}$$

The second is the Klein four group $\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2\mathbb{Z}$:

$$\begin{array}{ccccc}\cdot & e& a& b& c\\ e& e& a& b& c\\ a& a& e& c& b\\ b& b& c& e& a\\ c& c& b& a& e\end{array}$$

So there are two groups of order $4$ up to renaming the group elements: $\mathbb{Z}/4\mathbb{Z}$ and $\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2\mathbb{Z}$.

5. The only group of order $5$ is $\mathbb{Z}/5\mathbb{Z}$.

6. There are two groups of order $6$ up to renaming the group elements: $\mathbb{Z}/6\mathbb{Z}$ and $S_3$, the symmetric group of order $6$. The first is abelian, while the second is not. This is the first non-abelian group.

We will define what it means for groups to be “the same up to renaming” soon, but much of early group theory is about classifying all groups in this way.

Product groups

Let $(G,\ast )$ and $(H,\cdot )$ be groups. The product group $G\times H$ is the set of pairs $(g,h)$ with $g\in G$ and $h\in H$, with the operation defined by

$$(g_1,h_1)(g_2,h_2)=(g_1\ast g_2,h_1\cdot h_2).$$

The identity element is $(e_G,e_H)$, where $e_G$ and $e_H$ are the identity elements of $G$ and $H$, respectively. The inverse of an element $(g,h)$ is given by $(g^{-1},h^{-1})$. The operation is associative because both $\ast$ and $\cdot$ are associative. Therefore, $G\times H$ satisfies all the group axioms and is indeed a group.

Example

Let $S^1$ be the set of complex numbers $z$ with absolute value one; that is

$$S^1:=\{z\in \mathbb{C}||z|=1\}.$$

Then $(S^1,\times )$ is a group because

• The complex number $1\in S^1$ serves as the identity, and
• Each complex number $z\in S^1$ has an inverse $1/z$ which is also in $S^1$, since $|z^{-1}|=|z{|}^{-1}=1$.
• You should also check that $z_1\times z_2$ actually still lives in $S^1$. This follows from the fact that $|z_1{z}_2|=|z_1||z_2|=1$.

Example

Let $S{L}_n(\mathbb{R})$ denote the set of $n\times n$ matrices whose determinant is $1$. This is a subgroup (more on this soon) of ${\mathrm{GL}}_n(\mathbb{R})$, and is called the special linear group. The identity element is the identity matrix, and the inverse of a matrix $A$ in $S{L}_n(\mathbb{R})$ is its inverse $A^{-1}$, which also has determinant $1$. The group operation is associative because matrix multiplication is associative. Therefore, $S{L}_n(\mathbb{R})$ satisfies all the group axioms and is indeed a group.

Dihedral group

Consider a regular $n$-sided polygon. The symmetries of this polygon form a group under composition, known as the dihedral group $D_n$. What does the word symmetric mean here? We apply the label “symmetric” to anything that is invariant under some transformations. In this case, the elements of $D_n$ include rotations and reflections that preserve the shape of the polygon. The identity element is the rotation by $0$ degrees, and each symmetry has an inverse that undoes its effect. The group operation is associative because composition of functions is associative. Therefore, $D_n$ satisfies all the group axioms and is indeed a group.

If $r$ denotes rotation by $2\pi /n$ and $s$ denotes a reflection, then every element of $D_n$ can be written as either $r^i$ or $r^{i}s$ for some $0\le i<n$. The relations

$$r^n=e,s^2=e,srs=r^{-1}$$

explain most computations in this group. We will study these groups carefully later.

The next example is actually the original motivation for the definition of a group. That is, when Galois defined a group, he was thinking about the following example.

Symmetric group

The symmetric group $S_n$ is the group of all permutations of $\{1,\dots ,n\}$. By viewing these permutations as functions from $\{1,\dots ,n\}$ to itself, we can consider compositions $\circ$ of permutations. The pair $(S_n,\circ )$ is a group. There is an identity element: the permutation that leaves all elements fixed. Each permutation has an inverse, which is the permutation that undoes its effect.

A huge theorem of Cayley, which we will later show, says that every group is isomorphic to a subgroup of some symmetric group. This means that, in a sense, the symmetric groups are the most general groups. So maybe Galois was right to focus on them!

Quaternions

The quaternion group $Q_8$ is the group with elements

$$\{1,-1,i,-i,j,-j,k,-k\}$$

and multiplication defined by the following rules:

$$\begin{array}{rl}{i}^2=j^2=k^2& =-1,\\ ij=k,ji& =-k,\\ jk=i,kj& =-i,\\ ki=j,ik& =-j.\end{array}$$

This group is not abelian, since $ij=k$ but $ji=-k$.

Exercise

Let $G=\{a+b\sqrt{2}\in \mathbb{R}\mid a,b\in \mathbb{Q}\}$. Prove that $G$ is a group under addition, and prove that the nonzero elements of $G$ are a group under multiplication.

Exercise

This exercise gives a first glimpse of a Lie algebra. Let $M_2(\mathbb{C})$ be the vector space of all $2\times 2$ complex matrices. For $A,B\in M_2(\mathbb{C})$, define

$$[A,B]=AB-BA.$$

This operation is called the commutator bracket. In Lie theory, this is the basic example of a Lie bracket.

1. Compute $[A,B]$ for

$$A=\left[\begin{array}{cc}1& 0\\ 0& -1\end{array}\right],B=\left[\begin{array}{cc}0& 1\\ 0& 0\end{array}\right].$$

2. Prove that $[A,B]=-[B,A]$ for all $A,B\in M_2(\mathbb{C})$. In particular, $[A,A]=0$.
3. Prove that $[A,B]=0$ if and only if $A$ and $B$ commute.
4. Let

$${\mathfrak{sl}}_2(\mathbb{C})=\{A\in M_2(\mathbb{C})\mid \mathrm{Tr}(A)=0\}.$$

Prove that if $A,B\in {\mathfrak{sl}}_2(\mathbb{C})$, then $[A,B]\in {\mathfrak{sl}}_2(\mathbb{C})$.

Subgroups: first pass

Every time we define an algebraic object, we should ask which subsets inherit the same structure. For groups, these inherited objects are called subgroups. Often the best way to understand a group is to find smaller groups inside it.

Definition

A subgroup of a group $(G,\ast )$ is a group $(H,\ast )$ such that $H\subseteq G$ and the operation on $H$ is the operation on $G$ restricted to $H$. We write $H\le G$ to mean that $H$ is a subgroup of $G$.

The words “under the operation of $G$” are important. We are not allowed to put a new operation on $H$ and then call it a subgroup. A subgroup has to use the same multiplication law as the ambient group.

Example

Every group $G$ has two trivial subgroups: the group itself, and the subgroup $\{e\}$ consisting of just the identity element. For the groups $\mathbb{Z}/2\mathbb{Z}$ and $\mathbb{Z}/3\mathbb{Z}$, these are the only subgroups.

Example

Under addition, we have the chain of subgroups $\mathbf{Z}\le \mathbf{Q}\le \mathbf{R}\le \mathbf{C}$.

Example

For any integer $n$, the set

$$n\mathbb{Z}=\{nk\mid k\in \mathbb{Z}\}$$

is a subgroup of $\mathbb{Z}$ under addition. For instance, $3\mathbb{Z}\subset \mathbb{Z}$ is the subgroup of all multiples of $3$.

In practice, we usually do not want to check every group axiom from scratch.

Subgroup test

Let $G$ be a group and let $H$ be a nonempty subset of $G$. Then $H$ is a subgroup of $G$ if and only if

$$a{b}^{-1}\in H$$

for all $a,b\in H$. Equivalently, $H$ is a subgroup if and only if $H$ is nonempty and closed under the group operation and taking inverses.

Proof

If $H$ is a subgroup, then $b^{-1}\in H$, so $a{b}^{-1}\in H$.

Conversely, suppose $H$ is nonempty and $a{b}^{-1}\in H$ for all $a,b\in H$. Choose some $h\in H$. Taking $a=b=h$ gives $e=h{h}^{-1}\in H$. Taking $a=e$ and $b=h$ gives $h^{-1}\in H$. Finally, if $a,b\in H$, then $b^{-1}\in H$, so taking $a$ and $b^{-1}$ in the test gives $a(b^{-1}{)}^{-1}=ab\in H$. Thus $H$ has the identity, inverses, and is closed under the group operation. Associativity comes from $G$, so $H$ is a subgroup.

Example

$S{L}_n(\mathbb{R})\le {\mathrm{GL}}_n(\mathbb{R})$. Indeed, if $A,B\in S{L}_n(\mathbb{R})$, then

$$\det (A{B}^{-1})=\det (A)\det (B{)}^{-1}=1\cdot 1^{-1}=1,$$

so $A{B}^{-1}\in S{L}_n(\mathbb{R})$.

Example

If $g\in G$, then

$$⟨g⟩=\{\dots ,g^{-2},g^{-1},e,g,g^2,\dots \}$$

is a subgroup of $G$, called the cyclic subgroup generated by $g$.

Definition

The order $|g|$ of an element $g\in G$ is the size of the cyclic subgroup $⟨g⟩$ generated by $g$. That is, it is the least positive integer $n$ such that $g^n=e$, or $\infty$ if no such $n$ exists.

Exercise

If $x$ and $g$ are elements of the group $G$, prove that $|x|=|g^{-1}xg|$. Deduce that $|xy|=|yx|$ for all $x,y\in G$.

Example

In $S_n$, the set of permutations fixing $1$ is a subgroup:

$$\{\sigma \in S_n\mid \sigma (1)=1\}\le S_n.$$

This is called the stabilizer of $1$ in $S_n$.

In $D_n$, the rotations form a subgroup

$$\{e,r,r^2,\dots ,r^{n-1}\}\le D_n.$$

Also, for any reflection $s$, the two-element set $\{e,s\}$ is a subgroup of $D_n$.

Exercise

In a nonabelian group, two elements need not commute. On the other hand, they might commute. If $h\in G$, the centralizer of $h$ in $G$ is

$$C_G(h)=\{g\in G\mid gh=hg\}.$$

1. Prove that $C_G(h)$ is a subgroup of $G$.
2. Let $G$ be the symmetric group on $4$ letters and let $h$ be the permutation $(12)(34)$. What is the centralizer $C_G(h)$?

Exercise

Let $G$ be a group. The center of $G$ is

$$Z(G)=\{z\in G\mid zg=gz\text{ for all }g\in G\}.$$

1. Prove that $Z(G)$ is a subgroup of $G$.
2. Prove that

$$Z(G)=\bigcap _{h\in G}{C}_G(h).$$

3. Compute $Z(S_3)$ and $Z(D_4)$.

Exercise

Let $G$ be a finite group. The commuting graph of $G$ is the graph whose vertices are the elements of $G$, with an edge between distinct vertices $x$ and $y$ exactly when $xy=yx$.

1. Draw the commuting graph of $S_3$.
2. Explain how the degree of the vertex $x$ is related to the size of the centralizer $C_G(x)$.

Symmetric Groups

Permutation groups or symmetric groups are among the most important examples of groups. They are concrete enough that you can compute with them by hand, but also flexible enough that many abstract questions about groups can be reduced to questions about permutations. Furthermore, this was how Galois thought of groups and were what people meant for a long time when they said “group”.

Definition

A permutation of a set $X$ is a bijection $\sigma :X\to X$. When $X=\{1,2,\dots ,n\}$, the set of all permutations of $X$ is denoted $S_n$ and is called the symmetric group on $n$ letters.

The group operation on $S_n$ is composition of functions. Thus if $\sigma ,\tau \in S_n$, then $\sigma \tau$ means “first do $\tau$, then do $\sigma$.” This convention is annoying for approximately one week and then becomes second nature.

Proposition

The set $S_n$ forms a group under composition, and $|S_n|=n!$.

Proof

The composition of two bijections is again a bijection, composition of functions is associative, the identity map is the identity element, and every bijection has an inverse bijection. Hence $S_n$ is a group.

To count its elements, note that there are $n$ choices for $\sigma (1)$, then $n-1$ choices for $\sigma (2)$, and so on. Therefore

$$|S_n|=n(n-1)\cdots 2\cdot 1=n!.$$

Example

The group $S_3$ has six elements. One of them is the identity permutation, and the other five are the nontrivial rearrangements of $\{1,2,3\}$. Since $|S_3|=6$, this is the smallest symmetric group that is not abelian.

There are several ways to write permutations. The most literal is two-line notation:

$$\sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 1& 4& 2\end{array}\right)$$

means that $\sigma (1)=3$, $\sigma (2)=1$, $\sigma (3)=4$, and $\sigma (4)=2$.

The same permutation can be pictured by drawing arrows from each input to its output:

Two-line notation is fine for small examples, but it quickly becomes clunky. A better notation records how a permutation cycles elements around.

Definition

A cycle is a permutation of the form

$$(a_1{a}_2\dots a_k),$$

which sends $a_1$ to $a_2$, $a_2$ to $a_3$, …, $a_{k-1}$ to $a_k$, $a_k$ to $a_1$, and fixes every other element.

A cycle of length $2$ is called a transposition.

Example

In $S_5$, the cycle $(142)$ sends $1\mapsto 4$, $4\mapsto 2$, $2\mapsto 1$, and fixes $3$ and $5$. The permutation

$$(142)(35)$$

sends $1\mapsto 4$, $4\mapsto 2$, $2\mapsto 1$, $3\mapsto 5$, and $5\mapsto 3$. The two disjoint cycles show up as two separate directed components:

Definition

Two cycles are called disjoint if they move disjoint sets of elements.

Proposition

Disjoint cycles commute.

Proof

Suppose $\sigma$ and $\tau$ are disjoint cycles. If $x$ is moved by $\sigma$, then $\tau (x)=x$, so

$$(\sigma \tau )(x)=\sigma (x)=(\tau \sigma )(x).$$

The same argument works if $x$ is moved by $\tau$, and if $x$ is moved by neither cycle then both compositions fix $x$. Therefore $\sigma \tau =\tau \sigma$.

Theorem

Every permutation in $S_n$ can be written as a product of disjoint cycles. Aside from the order in which the disjoint cycles are written, this decomposition is unique if we ignore $1$-cycles.

Proof

Let $\sigma \in S_n$. Pick some element $a\in \{1,\dots ,n\}$. Repeatedly apply $\sigma$:

$$a,\sigma (a),{\sigma }^2(a),{\sigma }^3(a),\dots$$

Since there are only finitely many elements, eventually this sequence repeats. Because $\sigma$ is invertible, the first repeated element must be $a$, so these elements form a cycle

$$(a\sigma (a){\sigma }^2(a)\dots {\sigma }^{k-1}(a)).$$

If this cycle does not already involve every element of $\{1,\dots ,n\}$, pick an element not yet used and repeat the process. Continuing in this way produces disjoint cycles whose product is exactly $\sigma$.

For uniqueness, observe that the cycle containing a given element $a$ is completely determined by the orbit

$$a,\sigma (a),{\sigma }^2(a),\dots$$

so there is no freedom except to reorder the disjoint cycles and omit fixed points.

Example

Consider the permutation $\sigma \in S_7$ given by

$$\sigma (1)=3,\sigma (3)=5,\sigma (5)=1,\sigma (2)=4,\sigma (4)=2,\sigma (6)=6,\sigma (7)=7.$$

Then

$$\sigma =(135)(24).$$

We usually suppress the fixed points $6$ and $7$ rather than writing $(6)(7)$.

Exercise

Show that

$$(a_1{a}_2\cdots a_n)=(a_1{a}_n)(a_1{a}_{n-1})\cdots (a_1{a}_3)(a_1{a}_2)$$

for any $n>1$.

Cycle notation makes inverses very easy to compute:

$$(a_1{a}_2\dots a_k{)}^{-1}=(a_k{a}_{k-1}\dots a_2{a}_1).$$

It also makes the order of a permutation easier to see. For example, $(123)$ has order $3$, while $(12)(34)$ has order $2$.

Proposition

Every permutation is a product of transpositions.

Proof

It is enough to show that every cycle is a product of transpositions. But

$$(a_1{a}_2\dots a_k)=(a_1{a}_k)(a_1{a}_{k-1})\cdots (a_1{a}_2).$$

Since every permutation is a product of cycles, it follows that every permutation is a product of transpositions.

Corollary

The symmetric group $S_n$ is generated by the transpositions.

In fact, one can say more: $S_n$ is generated by the adjacent transpositions

$$(12),(23),\dots ,(n-1n).$$

This fact lies behind the idea that any rearrangement can be built by repeatedly swapping neighboring entries.

Exercise

Prove that the order of an element in $S_n$ is the least common multiple of the lengths of the cycles in its cycle decomposition.

We will see later that Cayley’s theorem says that every group is isomorphic to a subgroup of some symmetric group. Thus, in a sense, the symmetric groups are the most fundamental groups.

Exercise

A reduced word for a permutation is a way to write the permutation as a product of the smallest possible number of adjacent transpositions. Look up the Rothe diagram or pipe dream of a permutation and compute one for $(1423)\in S_4$.

Exercise

Find all numbers $n$ such that $S_5$ contains an element of order $n$.

Dihedral Groups

Fix an integer $n\ge 3$, and let $P_n$ be a regular $n$-gon centered at the origin in the plane. Label its vertices

$$V_0,V_1,\dots ,V_{n-1}$$

in counterclockwise order. Throughout this subsection, vertex subscripts are read modulo $n$.

Definition

An isometry of the plane is a function $f:{\mathbb{R}}^2\to {\mathbb{R}}^2$ preserving Euclidean distance:

$$d(f(A),f(B))=d(A,B)$$

for all points $A,B\in {\mathbb{R}}^2$.

A symmetry of $P_n$ is an isometry $f:{\mathbb{R}}^2\to {\mathbb{R}}^2$ such that $f(P_n)=P_n$ as a set. This does not mean that $f$ fixes every point of $P_n$; it means that $f$ moves the polygon onto itself.

Definition

The dihedral group $D_n$ is the set of symmetries of the regular $n$-gon $P_n$, with group operation given by composition.

Remark

There are two common conventions for the notation. In these notes, $D_n$ means the symmetry group of the regular $n$-gon, so $|D_n|=2n$. Some authors call this group $D_{2n}$ instead, emphasizing its order rather than the polygon.

Proposition

The set $D_n$ is a group under composition.

Proof

The composition of two isometries is again an isometry. If $f(P_n)=P_n$ and $g(P_n)=P_n$, then

$$(f\circ g)(P_n)=f(g(P_n))=f(P_n)=P_n,$$

so $f\circ g\in D_n$. Composition of functions is associative. The identity map is a symmetry of $P_n$, and the inverse of a symmetry is again a symmetry. Therefore $D_n$ is a group.

There are two basic kinds of symmetries.

Definition

Let $r\in D_n$ be counterclockwise rotation by $2\pi /n$. Thus

$$r(V_i)=V_{i+1}.$$

The rotations in $D_n$ are

$$e,r,r^2,\dots ,r^{n-1}.$$

Definition

A reflection in $D_n$ is reflection across a line of symmetry of $P_n$. If $n$ is odd, each reflection line passes through one vertex and the midpoint of the opposite side. If $n$ is even, there are two kinds of reflection lines: those passing through two opposite vertices, and those passing through the midpoints of two opposite sides.

There are $n$ rotations and $n$ reflections. To name the reflections efficiently, fix the reflection $s$ across the line through the origin and $V_0$. With our labeling,

$$s(V_i)=V_{-i}.$$

For example, when $n=6$, the chosen generators look like this:

Theorem

The dihedral group $D_n$ has $2n$ elements.

Proof

First we show that there are at most $2n$ symmetries. Any symmetry sends vertices to vertices and sends adjacent vertices to adjacent vertices. The image of $V_0$ can be any one of the $n$ vertices. Once $f(V_0)$ is chosen, the image of $V_1$ must be one of the two vertices adjacent to $f(V_0)$.

Every symmetry fixes the center of $P_n$, and a plane isometry is determined by the images of three non-collinear points. Thus the images of the center, $V_0$, and $V_1$ determine the whole symmetry. Therefore $|D_n|\le 2n$.

Now we exhibit $2n$ distinct symmetries:

$$e,r,r^2,\dots ,r^{n-1},s,rs,r^{2}s,\dots ,r^{n-1}s.$$

The rotations $r^i$ are distinct because $r^i(V_0)=V_i$. The elements $r^{i}s$ are distinct for the same reason, since $r^{i}s(V_0)=V_i$. Finally, $r^i$ and $r^{i}s$ are different because

$$r^i(V_1)=V_{i+1}\text{but}{r}^{i}s(V_1)=r^i(V_{-1})=V_{i-1},$$

and $V_{i+1}\ne V_{i-1}$ since $n\ge 3$.

Hence $D_n$ has at least $2n$ elements and at most $2n$ elements, so $|D_n|=2n$.

Remark

The rotations preserve the counterclockwise order of the vertices. The reflections reverse that order. This is often the quickest way to tell the two types of symmetries apart.

The two symmetries $r$ and $s$ generate the whole group. Their most important relations are

$$r^n=e,s^2=e,sr{s}^{-1}=r^{-1}.$$

Since $s^2=e$, the last relation is often written as $srs=r^{-1}$.

Lemma

In $D_n$, we have $sr{s}^{-1}=r^{-1}$.

Proof

Since $s^{-1}=s$, it is enough to compare $srs$ and $r^{-1}$ on the vertices. For every $i$,

$$srs(V_i)=sr(V_{-i})=s(V_{1-i})=V_{i-1}.$$

But $r^{-1}(V_i)=V_{i-1}$ as well. A symmetry of $P_n$ is determined by what it does to the vertices, so $srs=r^{-1}$.

Corollary

For every integer $i$, we have

$$s{r}^i{s}^{-1}=r^{-i}.$$

Proof

This follows by applying Lemma dihedral conjugates rotation repeatedly. Equivalently, conjugating by $s$ turns the basic rotation $r$ into its inverse, so it turns $r^i$ into $r^{-i}$.

Normal form in $D_n$

Every element of $D_n$ can be written uniquely in one of the forms

$$r^i\text{or}{r}^{i}s,$$

where $0\le i<n$.

Proof

The previous counting argument already exhibited the $2n$ distinct elements

$$e,r,r^2,\dots ,r^{n-1},s,rs,r^{2}s,\dots ,r^{n-1}s.$$

Since $D_n$ has exactly $2n$ elements, this list contains every element of $D_n$, and no element occurs twice.

Example

The group $D_4$, the symmetry group of the square, has $8$ elements:

$$e,r,r^2,r^3,s,rs,r^{2}s,r^{3}s.$$

Here $r$ is rotation by $90^{\circ }$, $r^2$ is rotation by $180^{\circ }$, and $r^3$ is rotation by $270^{\circ }$. The other four elements are reflections.

Exercise

The groups $D_4$ and $Q_8$ both have $8$ elements, and both are nonabelian. Prove that they are not isomorphic.

Hint: compare the numbers of elements satisfying $x^2=e$ in the two groups.

Example

The group $D_n$ is not abelian for $n\ge 3$. Indeed, the relation $sr{s}^{-1}=r^{-1}$ gives

$$sr=r^{-1}s.$$

If $sr=rs$, then $r^{-1}s=rs$, so $r^{-1}=r$ by cancellation. This would imply $r^2=e$, contradicting the fact that $r$ has order $n\ge 3$.

Informally, we summarize everything above by writing the presentation

$$D_n=⟨r,s\mid r^n=e,s^2=e,sr{s}^{-1}=r^{-1}⟩.$$

The symbols $r$ and $s$ generate the group, and the listed relations are enough to reduce any word in $r$ and $s$ to the normal form $r^i$ or $r^{i}s$.

For example, since $s{r}^j=r^{-j}s$, multiplication in normal form is governed by

$$\begin{array}{rlrl}{r}^i{r}^j& =r^{i+j},& r^i(r^{j}s)& =r^{i+j}s,\\ (r^{i}s)r^j& =r^{i-j}s,& (r^{i}s)(r^{j}s)& =r^{i-j},\end{array}$$

where the exponents are read modulo $n$.

Exercise

In $D_5$, simplify each expression to the form $r^i$ or $r^{i}s$ with $0\le i<5$:

$$s{r}^{2}s,r^{3}s{r}^4,s{r}^{3}sr.$$

Homomorphisms and isomorphisms: first pass

In this section we make precise the notion of when two groups “look the same”.

Definition

Let $G_1$, $G_2$ be groups. A homomorphism from $G_1$ to $G_2$ is a function $\phi :G_1\to G_2$ such that

$$\phi (g_1{g}_2)=\phi (g_1)\phi (g_2)$$

for all $g_1,g_2\in G_1$. An isomorphism is a homomorphism which is also a bijection. In this case, we’ll write $G\cong H$.

It’s the same as a map on sets, but it needs to respect the group structure of the domain and codomain. Two groups $G$ and $H$ are isomorphic if we can obtain $H$ from $G$ by just renaming elements. Very often we care about groups only up to isomorphism. For instance, the group ${\mathbb{Z}}^{\times }=\{1,-1\}$ is isomorphic to $\mathbb{Z}/2\mathbb{Z}$ by $f(1)=\overline{0}$ and $f(-1)=\overline{1}$. We could loosely say that ${\mathbb{Z}}^{\times }$ and $\mathbb{Z}/2\mathbb{Z}$ are the same group, even though they are written differently.

Example

The determinant gives a homomorphism

$$\det :{\mathrm{GL}}_n(\mathbb{R})\to {\mathbb{R}}^{\times },$$

since $\det (AB)=\det (A)\det (B)$ for all $A,B\in {\mathrm{GL}}_n(\mathbb{R})$. However, $\det$ is not an isomorphism, since it is not injective. It is surjective though, since the determinant of a diagonal matrix can be any nonzero real number.

Example

The exponential map $\exp :\mathbb{R}\to {\mathbb{R}}^{+}$ defined by $\exp (x)=e^x$ is an isomorphism from $(\mathbb{R},+)$ to $({\mathbb{R}}^{+},\cdot )$, since $\exp (x+y)=\exp (x)\exp (y)$ for all $x,y\in \mathbb{R}$, and $\exp$ is a bijection (it has inverse $\ln$).

Example

The inclusion $\iota :{\mathrm{GL}}_n(\mathbb{Z})\hookrightarrow {\mathrm{GL}}_n(\mathbb{R})$ is a homomorphism: when you multiply two integral matrices you get the same answer whether you think of the integers as integers or as real numbers! Note that this homomorphism is injective. That is, ${\mathrm{GL}}_n(\mathbb{Z})$ is a subgroup of ${\mathrm{GL}}_n(\mathbb{R})$.

Example

We have $S_n\cong S_m$ if and only if $n=m$ since $|S_n|=n!$ and $|S_m|=m!$, and the order of a group is preserved by isomorphism.

Example

Since $\mathbb{Z}/6\mathbb{Z}$ is abelian and $S_3$ is not abelian, we conclude that $\mathbb{Z}/6\mathbb{Z}\ncong S_3$.

Exercise

Prove that the multiplicative groups $\mathbb{R}\setminus \{0\}$ and $\mathbb{C}\setminus \{0\}$ are not isomorphic.

Example

The reduction map

$${\pi }_n:\mathbb{Z}\to \mathbb{Z}/n\mathbb{Z},{\pi }_n(a)=\overline{a},$$

is a homomorphism from $(\mathbb{Z},+)$ to $(\mathbb{Z}/n\mathbb{Z},+)$, because

$${\pi }_n(a+b)=\overline{a+b}=\overline{a}+\overline{b}={\pi }_n(a)+{\pi }_n(b).$$

Example

Homomorphisms out of cyclic groups are completely determined by one element. If $G=⟨g⟩$ and $f:G\to H$ is a homomorphism, then

$$f(g^m)=f(g{)}^m.$$

Thus once you know $f(g)$, you know $f$ on every element of $G$. In particular, a homomorphism $\mathbb{Z}\to H$ is determined by the image of $1$.

Group homomorphisms preserve the group structure. In particular, group homomorphisms preserve the identity element and all inverses:

Lemma

Let $f:G\to H$ be a group homomorphism. Then $f(e_G)=e_H$. Moreover, for every $g\in G$, we have $f(g^{-1})=f(g{)}^{-1}$.

Proof

We have

$$f(e_G)=f(e_G{e}_G)=f(e_G)f(e_G),$$

so $f(e_G)$ is an idempotent element of $H$. The only idempotent element of a group is the identity, so $f(e_G)=e_H$.

For the second part, we have

$$e_H=f(e_G)=f(g{g}^{-1})=f(g)f(g^{-1}),$$

so $f(g^{-1})$ is a right inverse of $f(g)$. Similarly, we can show that $f(g^{-1})$ is a left inverse of $f(g)$, and thus $f(g^{-1})=f(g{)}^{-1}$.

Remark

Given a group $G$ generated by a set $S$, any homomorphism $G\to H$ is completely determined by the images of the generators in $S$. In particular, if we want to construct a homomorphism from $G$ to $H$, it suffices to specify the images of the generators in $S$ and check that the relations in $G$ are satisfied in $H$.

Definition

The image of a homomorphism $f:G\to H$ is the set $\{f(g)|g\in G\}$. The kernel of $f$ is the set $\{g\in G|f(g)=e_H\}$.

Exercise

Prove that the image of a homomorphism is a subgroup of $H$ and the kernel of a homomorphism is a subgroup of $G$.

Remark

Given any group homomorphism $f:G\to H$, we must have $e_G\in \ker f$ since $f(e_G)=e_H$.

When the kernel is as small as possible, meaning $\ker (f)=\{e\}$, then we say that the kernel is trivial. A homomorphism is injective if and only if its kernel is trivial, and a homomorphism is surjective if and only if its image is all of $H$.

Lemma

A group homomorphism $f:G\to H$ is injective if and only if $\ker f=\{e_G\}$.

Proof

If $f$ is injective, then the only element of $G$ that maps to $e_H$ is $e_G$, so $\ker f=\{e_G\}$. Conversely, if $\ker f=\{e_G\}$ and $f(g_1)=f(g_2)$, then

$$e_H=f(g_1)f(g_2{)}^{-1}=f(g_1{g}_2^{-1}),$$

so $g_1{g}_2^{-1}\in \ker f$. Since $\ker f=\{e_G\}$, we have $g_1{g}_2^{-1}=e_G$, so $g_1=g_2$. Therefore, $f$ is injective.

The easiest way to show that two groups are not isomorphic is to find a property that one group has but the other does not. For example, $S_3$ is not isomorphic to $\mathbb{Z}/6\mathbb{Z}$ because $S_3$ is not abelian while $\mathbb{Z}/6\mathbb{Z}$ is abelian.

Exercise

An isomorphism $G\to G$ is called an automorphism of $G$. Prove that the set of automorphisms of a group $G$ forms a group under composition, called the automorphism group of $G$ and denoted $\mathrm{Aut}(G)$.

Exercise

Let $G$ be any group. Prove that the map from $G$ to itself defined by $g\mapsto g^{-1}$ is an automorphism if and only if $G$ is abelian.

Group actions: first pass

Group actions provide the perspective under which groups describe “symmetries”. The confusing thing about the word “symmetries” is that it is being used in a technical sense. You can think of a group action as a way for a group to act on a set, moving its elements around in a way that respects the group structure.

Definition

Let $G$ be a group and let $X$ be a set. A left action of $G$ on $X$ is a rule that assigns to each $g\in G$ and each $x\in X$ an element $g\cdot x\in X$ (so a map $G\times X\to X$) such that

• $e\cdot x=x$ for every $x\in X$.
• $(gh)\cdot x=g\cdot (h\cdot x)$ for every $g,h\in G$ and every $x\in X$.

Example

The dihedral group $D_n$ acts on the set of vertices of a regular $n$-gon. A rotation or reflection sends each vertex to another vertex, and composing symmetries agrees with the group operation in $D_n$.

Example

The symmetric group $S_n$ acts on $\{1,\dots ,n\}$ by $\sigma \cdot i=\sigma (i)$. This is the most basic example of a permutation group acting on a set.

Note that we’ve already been thinking about $D_n$ and $S_n$ using group actions. Rather than thinking about them as being made up of abstract elements, we’ve been thinking of them as symmetries of some set. Symmetry here means: a bijection from the set to itself.

For each fixed $g\in G$, we get a map ${\sigma }_g:X\to X$ defined by ${\sigma }_g(x)=g\cdot x$.

Proposition

Let $G$ act on a set $X$. For each $g\in G$, the map ${\sigma }_g:X\to X$ is a bijection. Moreover, the assignment

$$\rho :G\to \mathrm{Sym}(X),\rho (g)={\sigma }_g$$

is a group homomorphism.

Proof

The map ${\sigma }_{g^{-1}}$ provides the inverse of ${\sigma }_g$:

$$({\sigma }_{g^{-1}}\circ {\sigma }_g)(x)=g^{-1}\cdot (g\cdot x)=(g^{-1}g)\cdot x=e\cdot x=x,$$

and similarly $({\sigma }_g\circ {\sigma }_{g^{-1}})(x)=x$. Thus ${\sigma }_g$ is a bijection.

To check that $\rho$ is a homomorphism, let $g,h\in G$. For every $x\in X$,

$$\rho (gh)(x)=(gh)\cdot x=g\cdot (h\cdot x)=(\rho (g)\circ \rho (h))(x).$$

Hence $\rho (gh)=\rho (g)\circ \rho (h)$.

The homomorphism $\rho :G\to \mathrm{Sym}(X)$ is called the permutation representation associated to the action. Conversely, any homomorphism $\rho :G\to \mathrm{Sym}(X)$ gives an action of $G$ on $X$ by the rule

$$g\cdot x=\rho (g)(x).$$

Thus a group action is the same thing as a way to represent elements of $G$ as permutations of a set.

Example

The action of $D_n$ on the vertices of a regular $n$-gon gives a permutation representation

$$\rho :D_n\to \mathrm{Sym}(\{V_0,\dots ,V_{n-1}\})\cong S_n.$$

If $r$ is the rotation with $r(V_i)=V_{i+1}$, then $\rho (r)$ is the cycle

$$(V_0{V}_1\cdots V_{n-1}).$$

If $s$ is the reflection with $s(V_i)=V_{-i}$, then $\rho (s)$ is the permutation of the vertices determined by $V_i\mapsto V_{-i}$. So the abstract relation $srs=r^{-1}$ can be seen directly as a relation among permutations of the vertices.

Example

Every group $G$ acts on itself by left multiplication:

$$g\cdot x=gx.$$

The associated permutation representation is

$$\lambda :G\to \mathrm{Sym}(G),\lambda (g)(x)=gx.$$

This homomorphism is injective: if $\lambda (g)$ is the identity permutation of $G$, then it fixes $e$, so

$$g=ge=\lambda (g)(e)=e.$$

Thus $G$ is isomorphic to the subgroup $\lambda (G)\le \mathrm{Sym}(G)$.

Cayley's theorem

Every finite group is isomorphic to a subgroup of $S_n$.

Proof

Let $G$ be a finite group with $|G|=n$. By the previous example, $G$ is isomorphic to a subgroup of $\mathrm{Sym}(G)$. Since $G$ has $n$ elements, choosing a labeling of the elements of $G$ identifies $\mathrm{Sym}(G)$ with $S_n$.

From a practical perspective, this is a nearly useless theorem. It is, however, a beautiful fact.

Exercise

Matrix groups also act naturally on vector spaces. For example, let

$$C_4=⟨r\mid r^4=e⟩$$

be the cyclic group of order $4$, and let

$$R=\left[\begin{array}{cc}0& -1\\ 1& 0\end{array}\right].$$

Show that there is a group action $C_4$ on ${\mathrm{GL}}_2(\mathbb{R})$ given by $r^k\cdot v=R^{k}v$ for $v\in {\mathbb{R}}^2$. This is a small example of a representation: instead of representing group elements as permutations of a set, we represent them as invertible matrices acting on a vector space.

Example

Every group $G$ also acts on itself by conjugation:

$$g\cdot x=gx{g}^{-1}.$$

This action measures how far a group is from being abelian. If $G$ is abelian, conjugation does nothing, since $gx{g}^{-1}=x$ for all $g,x\in G$.

Later we will attach two important pieces of information to an action: the orbit of a point, which records where the point can move, and the stabilizer of a point, which records which group elements fix it.