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)=g\,h$ .

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

Proof. $\psi _{g}(h)=\psi _{g}(k)$ for some $h,k\in G$ . This implies $g\,h=g\,k$ 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]=\left\{f(h)~\mid ~h\in H\right\}\subseteq B

Lemma 8.15

Lemma. Let $G,G'$ be two groups and $\phi :G\to G'$ be a group homomorphism which is injective. Then

$\phi [G]$ is a subgroup of $G'$ , and
$\phi$ gives an isomorphism between $G$ and $\phi [G]$ .

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

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

Therefore $\phi :G\to \phi [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)=g\,h$ (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]\leq 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\iff b=\sigma ^{n}(a)\,\!

for some

n\in \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=\left\{1,2,3,4,5,6,7,8\right\}$ . 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 ={\begin{pmatrix}1&2&3&4&5&6&7&8\\3&8&6&7&4&1&5&2\end{pmatrix}}$ , 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{aligned}\mu _{1}&={\begin{pmatrix}1&2&3&4&5&6&7&8\\3&2&6&4&5&1&7&8\end{pmatrix}}\\\mu _{2}&={\begin{pmatrix}1&2&3&4&5&6&7&8\\1&8&3&4&5&6&7&2\end{pmatrix}}\\\mu _{3}&={\begin{pmatrix}1&2&3&4&5&6&7&8\\1&2&3&7&4&6&5&8\end{pmatrix}}\end{aligned}}$

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,3,6}, {2}, {4}, {5}, {7}, {8} (len = 3)
{1}, {2,8}, {3}, {4}, {5}, {6}, {7} (len = 2)
{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{aligned}\mu _{1}&=(1,3,6)\\\mu _{2}&=(2,8)\\\mu _{3}&=(4,7,5)\end{aligned}}$

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)\neq (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},\ldots ,B_{r}$ be the orbits of $\sigma$ . Define a cycle $\mu _{i}$ as follows:

\mu _{i}(x)={\begin{cases}\sigma (x)&x\in B_{i}\\x&{\mbox{otherwise}}\end{cases}}\,\!

Then clearly $\sigma =\mu _{1}\circ \mu _{2}\circ \dots \circ \mu _{r}$ .

quod erat demonstrandum

For example, write $\sigma ={\begin{pmatrix}1&2&3&4&5&6\\6&5&2&4&3&1\end{pmatrix}}$ 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},\ldots ,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|\geq 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.