MATH 415 Lecture 6

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

Cayley's Theorem

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 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 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 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 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 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} . 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 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} into equivalence classes. If $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 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 \sim} is an equivalence relation:

Proof.:

• It is reflexive since $a=\sigma ^{0}(a)$.
• It is symmetric since 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 = \sigma^{-n}(b)} (i.e. 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 \sim a} ) 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 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 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} be a permutation 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 A} . The equivalence classes 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 \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 $A=\left\{1,2,3,4,5,6,7,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 = e} (identity permutation), 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 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 \left\{ 1 \right\}} , 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 \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:

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 &= \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{align}}

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 $\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 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 $\sigma$ of a finite set is a product of disjoint cycles.

Proof. 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 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 $\sigma =\mu _{1}\circ \mu _{2}\circ \dots \circ \mu _{r}$.

quod erat demonstrandum

For example, write 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\\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.

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,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 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 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} , 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 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 : 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 $n\geq 2$ then $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