MATH 415 Lecture 6

« previous | Thursday, September 12, 2013 | next »

Cayley's Theorem

Let $G$ be a group. Choose element $g\in G$ and consider ${\psi }_g:G\to G$ such that ${\psi }_g(h)=gh$.

Lemma. ${\psi }_g$ is a permutation of $G$.

Proof. ${\psi }_g(h)={\psi }_g(k)$ for some $h,k\in G$. This implies $gh=gk$ and nhus $h=k$. Therefore ${\psi }_g$ is injective.

Given

$h\in G$

,

${\psi }_g(g^{-1}h)=g(g^{-1}h)=(g{g}^{-1})h=h$

. Thus

${\psi }_g$

is surjective.

quod erat demonstrandum

If $f:A\to B$ is a function and $H\subseteq A$, then the "image of $H$ under $f$" is the set

$f\left[H\right]=\{f(h)\mid h\in H\}\subseteq B$

Lemma 8.15

Lemma. Let $G,G^{\prime }$ be two groups and $\varphi :G\to G^{\prime }$ be a group homomorphism which is injective. Then

1. $\varphi [G]$ is a subgroup of $G^{\prime }$, and
2. $\varphi$ gives an isomorphism between $G$ and $\varphi [G]$.

Proof. First: why is $\varphi [G]$ a subgroup? If $x^{\prime },y^{\prime }\in \varphi [G]$, then $x^{\prime }=\varphi (x)$ and $y^{\prime }=\varphi (y)$ for some $x,y\in G$. If we take $x^{\prime }{y}^{\prime }$, then we have $\varphi (x)\varphi (y)=\varphi (x,y)$ because it is a homomorphism. Therefore $x^{\prime }{y}^{\prime }\in \varphi [G]$.

If $x^{\prime }\in \varphi [G]$, then $x^{\prime }=\varphi (x)$ for some $x\in G$. $(x^{\prime }{)}^{-1}=(\varphi (x){)}^{-1}=\varphi (x^{-1})$, so $(x^{\prime }{)}^{-1}\in \varphi [G]$. Therefore $\varphi [G]$ is a subgroup of $G^{\prime }$.

Therefore

$\varphi :G\to \varphi [G]$

is an isomorphism.

quod erat demonstrandum

Theorem 8.16 (Cayley's Theorem)

Theorem. Every group is isomorphic to a group of permutations.

Proof. Let $G$ be a group and consider $S_G$ (all permutations of $G$).

Define $\gamma :G\to S_G$ such that $\gamma (g)={\psi }_g$, where ${\psi }_g(h)=gh$ (from above). According to the first lemma, ${\psi }_g\in S_G$, so $\gamma$ is well-defined.

We claim that $\gamma$ is injective.

If $\gamma (g_1)=\gamma (g_2)$, then ${\psi }_{g_1}={\psi }_{g_2}$. We find ${\psi }_{g_1}(e)={\psi }_{g_2}(e)$, where $e$ is the identity element of $G$. Thus $g_{1}e=g_{2}e$ and $g_1=g_2$. Thus $\gamma$ is injective.

We claim that $\gamma$ is a homomorphism.

$\gamma (g_1{g}_2)={\psi }_{g_1{g}_2}=g_1{g}_{2}h={\psi }_{g_1}\circ {\psi }_{g_2}$ for all $h\in G$. Therefore $\gamma$ is a homomorphism.

By Lemma 8.15,

$G\simeq \gamma [G]\le S_G$

.

quod erat demonstrandum

Section 9: Orbits, Cycles, and Alternating Groups

Orbits

Suppose $\sigma$ is a permutation of a set $A$. $\sigma$ naturally partitions $A$ into equivalence classes. If $a,b\in A$, then

$a\sim B⟺b={\sigma }^n(a)$ for some $n\in \mathbb{\mathbb{Z}}$

We claim that $\sim$ is an equivalence relation:

Proof.:

• It is reflexive since $a={\sigma }^0(a)$.
• It is symmetric since $a={\sigma }^{-n}(b)$ (i.e. $b\sim a$) for all $b={\sigma }^n(a)$ (i.e. $a\sim b$)
• It is transitive since $b={\sigma }^n(a)$ and $c={\sigma }^m(b)$ imply that $c={\sigma }^m(b)={\sigma }^m({\sigma }^n(a))={\sigma }^{n+m}(a)=a\sim c$.
  quod erat demonstrandum

Let $\sigma$ be a permutation of $A$. The equivalence classes of $\sim$ are called orbits of $\sigma$.

For example, let $A=\{1,2,3,4,5,6,7,8\}$. If we take $\sigma =e$ (identity permutation), then the orbits of $\sigma$ are $\left\{1\right\}$, $\left\{2\right\}$, ..., $\left\{8\right\}$.

If we take $\sigma =\left(\begin{array}{cccccccc}1& 2& 3& 4& 5& 6& 7& 8\\ 3& 8& 6& 7& 4& 1& 5& 2\end{array}\right)$, then the orbits of $\sigma$ are $\{1,3,6\},\{2,8\},\{4,5,7\}$.

Cycles

Each orbit may be represented as its own permutation. For example, from above, the orbits can be written as:

$\begin{array}{rl}{\mu }_1& =\left(\begin{array}{cccccccc}1& 2& 3& 4& 5& 6& 7& 8\\ 3& 2& 6& 4& 5& 1& 7& 8\end{array}\right)\\ {\mu }_2& =\left(\begin{array}{cccccccc}1& 2& 3& 4& 5& 6& 7& 8\\ 1& 8& 3& 4& 5& 6& 7& 2\end{array}\right)\\ {\mu }_3& =\left(\begin{array}{cccccccc}1& 2& 3& 4& 5& 6& 7& 8\\ 1& 2& 3& 7& 4& 6& 5& 8\end{array}\right)\end{array}$

Observe that $\sigma ={\mu }_1\circ {\mu }_2\circ {\mu }_3$

A permutation $\sigma \in S_n$ is called a cycle if it has at most one orbit containing more than one element. The length of a cycle is the number of elements in its largest orbit.

Let's find the orbits and lengths of each $\mu$ above:

1. {1,3,6}, {2}, {4}, {5}, {7}, {8} (len = 3)
2. {1}, {2,8}, {3}, {4}, {5}, {6}, {7} (len = 2)
3. {1}, {2}, {3}, {4,7,5}, {6}, {8} (len = 3)

Convenient Notation for Cycles

Instead of writing out a permutation for each $\mu$, we can use the following shortand:

$\begin{array}{rl}{\mu }_1& =(1,3,6)\\ {\mu }_2& =(2,8)\\ {\mu }_3& =(4,7,5)\end{array}$

By this we mean that (in ${\mu }_1$), 1 maps to 3, 3 maps to 6, and 6 maps back to 1. All other elements are understood to be identity-mapped.

Thus $\sigma =(1,3,6)\circ (2,8)\circ (4,7,5)$

Note that we wrote an arbitrary permutation as a product/composition of disjoint cycles, which leads to our next theorem.

Note: Composition of disjoint cycles is commutative. This is not true if they are not disjoint.

$(1,4,5,6)\circ (2,1,5)\ne (2,1,5)\circ (1,4,5,6)$

• On the left, 1 maps to 5 and then 5 maps to 6: 1 → 6
• On the right, 1 maps to 4 and then 4 is id-mapped: 1 → 4

Theorem 9.8

Theorem. Every permutation $\sigma$ of a finite set is a product of disjoint cycles.

Proof. Let $B_1,B_2,\dots ,B_r$ be the orbits of $\sigma$. Define a cycle ${\mu }_i$ as follows:

${\mu }_i(x)=\{\begin{array}{ll}\sigma (x)& x\in B_i\\ x& \text{otherwise}\end{array}$

Then clearly

$\sigma ={\mu }_1\circ {\mu }_2\circ \dots \circ {\mu }_r$

.

quod erat demonstrandum

For example, write $\sigma =\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 6& 5& 2& 4& 3& 1\end{array}\right)$ as a product of disjoint cycles:

$\sigma =(1,6)\circ (2,5,3)$

Transposition

A cycle of length 2 is called a transposition

Observation: $(a_1,a_2,\dots ,a_n)=(a_1,a_n)\circ (a_1,a_{n-1})\circ \dots \circ (a_1,a_2)$

Corollary. Any permutation of a finite set $|A|\ge 2$ is a product of transpositions.

for example, write the $\sigma =(1,6)\circ (2,5,3)$ above as a product of transpositions.

$\sigma =(1,6)\circ (2,3)\circ (2,5)$

Note that this representation is not unique because $(1,6)\circ (2,3)\circ (2,5)\circ (3,4)\circ (4,3)$ is equivalent (we change 4 to 3 and then back to 4).

Theorem 9.15

Theorem. No permutation in $S_n$ can be expressed both as a product of an even number of transpositions and as a product of an odd number of transpositions.

Proof (sketch).

$\det I=1$

, but switching any two rows negates the determinant. We can think of this switch as a transposition. If we assume the negation of the theorem, then we can determine that

$\det \sigma (I)=-1$

and

$\det \sigma (I)=1$

, which is a contradiction.

quod erat demonstrandum

This theorem can be applied to the shifting tiles puzzle. The following board is not solvable since all solutions have an even parity.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	24	23

Alternating Groups

Let $A_n$ be the subset of $S_n$ of all even permutations and $B_n$ be the set of all odd permutations.

Lemma. $|A_n|=|B_n|=\frac{|S_n|}{2}=\frac{n!}{2}$

Proof. Let $\varphi :A_n\to B_n$ by $\varphi (\sigma )=(1,2)\circ \sigma$.

We need to show that $\varphi$ is bijective.

Theorem 9.20

Theorem. If $n\ge 2$ then $A_n$ is a subgroup of order $\frac{n!}{2}$.

Proof. Even + even = even; the set of even numbers is closed under addition

quod erat demonstrandum

$A_n$ is called the alternating group