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 $\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 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 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} , we can use the following shortand:

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 \begin{align} \mu_1 &= (1,3,6) \\ \mu_2 &= (2,8) \\ \mu_3 &= (4,7,5) \end{align}}

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 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,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 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} . 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 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 \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: 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_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 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| \ge 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). 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 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. 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| = |B_n| = \frac{|S_n|}{2} = \frac{n!}{2}}

Proof. Let $\phi :A_{n}\to B_{n}$ by 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(\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 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 \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