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

1. $\phi [G]$ is a subgroup of $G'$, and
2. $\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma} is a permutation of a set $A$. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma} naturally partitions $A$ into equivalence classes. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a,b \in A} , then

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma} .

For example, let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma = \mu_1 \circ \mu_2 \circ \mu_3}

A permutation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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{aligned}\mu _{1}&=(1,3,6)\\\mu _{2}&=(2,8)\\\mu _{3}&=(4,7,5)\end{aligned}}$

By this we mean that (in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_i} as follows:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_n} be the subset of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_n} of all even permutations and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B_n} be the set of all odd permutations.

Lemma. $|A_{n}|=|B_{n}|={\frac {|S_{n}|}{2}}={\frac {n!}{2}}$

Proof. Let $\phi :A_{n}\to B_{n}$ by $\phi (\sigma )=(1,2)\circ \sigma$.

We need to show that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} is bijective.

Theorem 9.20

Theorem. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \ge 2} then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_n} is called the alternating group