\input fremtex
%\fullsize
\smallprint
\filename{ma301.tex}
\versiondate{19.3.02}
\def\lectureend#1{\discrversionA{\hfill{\twelverm #1}}{}}
\def\omitted#1{\discrversionA{\hfill{\twelverm omitted #1}}{}}
\ifamstexsupported\font\twelverm=cmr12
\else\font\twelverm=cmr10 at 12 pt\fi
\def\action{\mathchoice{\lower-.3ex\hbox{$\ssbullet$}}
{\lower-.3ex\hbox{$\ssbullet$}}
{\ssbullet}
{\ssbullet}}
\def\cycle#1{(\overleftarrow{#1})}
\def\Rot{\mathop{\text{Rot}}}
\def\Isom{\mathop{\text{Isom}}}
\def\Orb{\mathop{\text{Orb}}}
\def\Stab{\mathop{\text{Stab}}}
\def\kernel{\mathop{\text{ker}}}
\Centerline{\bf MA301 Algebra}
\Centerline{\smc D.H.Fremlin}
\oldfootnote{}{These notes are distributed to students on the
understanding that they have not been fully checked for errors. They
are not intended to provide a substitute for attendance at lectures.
If you notice a mistake, please tell the lecturer!}
\medskip
This course introduces the theory of finite groups, with applications to
geometry and combinatorics.
\medskip
\noindent{\bf Semigroups}
\medskip
I begin with a short section on the general theory of semigroups.
\medskip
{\bf Definition} A {\bf semigroup} is a set $F$ (allowing $F=\emptyset$)
together with a binary operation $(x,y)\mapsto xy:F\times F\to F$ which
is {\bf associative}, that is, such that $x(yz)=(xy)z$ for all $x$, $y$,
$z\in F$.
\medskip
{\bf Examples (a)} $(\Bbb N\setminus\{0\},+)$, where $\Bbb
N=\{0,1,2,\ldots\}$ is the set of non-negative integers.
\medskip
{\bf (b)} $(\Bbb N,\times)$.
\medskip
{\bf (c)} The set of $n\times n$ real matrices, with matrix
multiplication.
\medskip
{\bf (c)} Let $X$ be any set. Let $F$ be the set of all functions $f$
such that $\dom f\subseteq X$ and $f(x)\in X$ for every $x\in\dom f$,
with composition. Then $F$ is a semigroup. \Prf\ (i) If $f$, $g\in
F$ then
\Centerline{$\dom(f\smallcirc g)=\{x:x\in\dom g,\,g(x)\in\dom f\}
\subseteq\dom g\subseteq X$}
\noindent and $(f\smallcirc g)(x)=f(g(x))\in X$ for every
$x\in\dom(f\smallcirc g)$, so $f\smallcirc g\in F$; thus $\smallcirc$
is a binary operation on $F$. (ii) If $f$, $g$, $h\in F$ then
$$\eqalign{\dom(f\smallcirc(g\smallcirc h))
&=\{x:x\in\dom(g\smallcirc h),\,(g\smallcirc h)(x)\in\dom f\}\cr
&=\{x:x\in\dom h,\,h(x)\in\dom g,\,g(h(x))\in\dom f\}\cr
&=\{x:x\in\dom h,\,h(x)\in\dom(f\smallcirc g)\}\cr
&=\dom((f\smallcirc g)\smallcirc h).\cr}$$
\noindent So $(f\smallcirc g)\smallcirc h$ and $f\smallcirc(g\smallcirc
h)$ have the same domain. And if $x$ is any point of this common
domain,
$$\eqalign{(f\smallcirc(g\smallcirc h))(x)
=f((g\smallcirc h)(x))
&=f(g(h(x)))\cr
&=(f\smallcirc g)(h(x))
=((f\smallcirc g)\smallcirc h)(x).\cr}$$
\noindent So $(f\smallcirc g)\smallcirc h$ and $f\smallcirc(g\smallcirc
h)$ have the same domain and the same value at every point of that
domain, and are the same function.\ \Qed
\medskip
{\bf (e)} If $F$ is any semigroup, then for $A$, $B\subseteq F$ write
$AB$ for the set $\{ab:a\in A,\,b\in B\}$. With this multiplication,
$\Cal PF$ is a semigroup, because
$$\eqalignno{A(BC)&=\{ay:a\in A,\,y\in BC\}
=\{a(bc):a\in A,\,b\in B,\,c\in C\}\cr
&=\{(ab)c:a\in A,\,b\in B,\,c\in C\}\cr
\displaycause{because multiplication in $F$ is associative}
&=\{xc:x\in AB,\,c\in C\}
=(AB)C.\cr}$$
\medskip
{\bf Multiplying strings} If $F$ is a semigroup and $a$, $b$, $c$, $d$
belong to $F$, then
\Centerline{$(ab)(cd)=((ab)c)d=(a(bc))d=a((bc)d)=a(b(cd))=\ldots$.}
\noindent Generally, given any finite string $a_0$, $a_1,\ldots,a_n$ of
elements of a semigroup, we can safely write $a_0a_1\ldots a_n$ for
their product, doing the multiplications in any way we like, so long as
we keep the elements in order. (We do {\it not} expect
$abc=a(bc)=(ab)c$ to be the same as $cba$.)
\medskip
{\bf Commutative semigroups} However, it does sometimes happen that we
can do our multiplications either way round without changing the
answers; a semigroup is called {\bf commutative} or {\bf abelian} if
$xy=yx$ for all $x$, $y$. Of the examples above, $(\Bbb
N\setminus\{0\},+)$ and $(\Bbb N,\times)$ are commutative and the others
aren't.) This course is going to concentrate on
{\it non-commutative} operations, and commutativity will be rare (and
correspondingly important).
\medskip
{\bf Identities} If $F$ is a semigroup, an {\bf identity} in $F$ is an
$e\in F$ such that $xe=ex=x$ for every $x\in F$.
\medskip
{\bf Theorem} If $F$ is a semigroup, it has at most one identity.
\medskip
\noindent{\bf proof} If $e$, $e'$ are identities in $F$, then
$$\eqalign{e&=ee'\text{ because }e'\text{ is an identity},\cr
&=e'\text{ because }e\text{ is an identity}.\cr}$$
\lectureend{02/1}
\medskip
{\bf Remark} We can therefore safely speak of {\it the} identity in a
semigroup
with identity.
\medskip
{\bf Inverses} If $F$ is a semigroup with identity $e$, and $x\in F$,
then an
{\bf inverse} of $x$ in $F$ is a $y\in F$ such that $xy=yx=e$.
\medskip
{\bf Theorem} If $F$ is a semigroup with identity, then any element of
$F$ has at most one identity.
\medskip
\noindent{\bf proof} If $y$ and $z$ are both inverses of $x$, then
\Centerline{$y=ye=y(xz)=(yx)z=ez=z$.}
\medskip
{\bf Definition} A {\bf group} is a semigroup with identity in which
every element has an inverse.
\medskip
{\bf Remark} Because any element of the group has exactly one inverse,
we can safely write $x^{-1}$ for the inverse of $x$, just as we can
safely write $e$ for the unique identity of the group.
\medskip
{\bf Theorem} Let $F$ be a semigroup with identity $e$. Then the set
$F^*$ of invertible elements of $F$, with the multiplication inherited
from $F$, is a group.
\medskip
\noindent{\bf proof (a)} If $a$, $b\in F^*$ there are $x$, $y\in F$ such
that
$ax=xa=by=yb=e$. In this case
\Centerline{$(ab)(yx)=a(by)x=aex=ax=e$,
\quad$(yx)(ab)=y(xa)b=yeb=yb=e$.}
\noindent So $ab$ has an inverse $yx\in F$, and belongs to $F^*$. This
shows that multiplication provides a binary operation from $F^*\times
F^*$ to $F^*$.
\medskip
{\bf (b)} If $a$, $b$, $c\in F^*$ then $(ab)c=a(bc)$ because the
multiplication of $F$ is associative. So $F^*$ is a semigroup.
\medskip
{\bf (c)} $ee=e$ so $e$ is its own inverse in $F$ and $e\in F^*$. Now
$ae=ea=a$ for every $a\in F^*$ (because $ae=ea=a$ for every $a\in F$),
and $e$ is an identity in $F^*$. Thus $F^*$ is a semigroup with
identity.
\medskip
{\bf (d)} If $a\in F^*$, there is an $x\in F$ such that $ax=xa=e$.
Because $xa=ax=e$, $a$ is an inverse of $x$ in $F$, and $x\in F^*$.
Now $ax=xa=e$ is the identity in $F^*$, so $x$ is an inverse of $a$ in
$F^*$. As $a$ is arbitrary, every element of $F^*$ is invertible in
$F^*$ and $F^*$ is a group.
\medskip
{\bf Remarks} Observe that in the argument for (a) of the proof, I
showed that $(ab)^{-1}=b^{-1}a^{-1}$, because $abb^{-1}a^{-1}=b^{-1}a^{-
1}ab=e$. Similarly, in (d), I showed that $(a^{-1})^{-1}=a$, because
$aa^{-1}=a^{-1}a=e$.
\medskip
{\bf Cancellation laws} If $G$ is a group, then
\Centerline{whenever $ax=ay$ in $G$, then $x=y$.}
\noindent\Prf\ $x=ex=(a^{-1}a)x=a^{-1}(ax)=a^{-1}(ay)=(a^{-1}a)y=ey=y$.\
\Qed
Similarly,
\Centerline{whenever $xa=ya$ in $G$, then $x=y$.}
\noindent\Prf\ $x=xe= x(aa^{-1})=(xa)a^{-1}=(ya)a^{-1}=y(aa^{-
1})=ye=y$.\ \Qed
\medskip
{\bf Subgroups: definition} Let $G$ be a group. A {\bf subgroup} of
$G$ is a subset $H$ of $G$ such that
\Centerline{$e\in H$,}
\Centerline{$ab\in H$ for all $a$, $b\in H$,}
\Centerline{$a^{-1}\in H$ for every $a\in H$.}
\noindent{\bf Notation} The formula `$H\le G$' is often used to mean
`$H$ is a subgroup of $G$'.
\medskip
{\bf Theorem} If $G$ is a group and $H$ is a subgroup of $G$, then $H$,
with the multiplication inherited from that of $G$, is a group in its
own right.
\medskip
\noindent{\bf proof} If $a$, $b\in H$ then $ab\in H$ (second clause in
the definition of `subgroup'. So multiplication is a binary operation
on $H$.
If $a$, $b$, $c\in H$ then $(ab)c=a(bc)$ because the multiplication on
$G$ is associative. So $H$ is a semigroup.
The identity $e$ of $G$ belongs to $H$ (first clause in the definition
of `subgroup'), and $ea=ae=a$ for every $a\in H$, so $e$ is also an
identity in $H$, and $H$ is a semigroup with identity.
If $a\in H$, then $a^{-1}$ (the inverse of $a$ in $G$) belongs to $H$
(third clause in the definition of `subgroup'), and $aa^{-1}=a^{-1}a=e$,
the identity of $H$; so $a^{-1}$ is an inverse of $a$ in $H$. Thus
every element of $H$ has an inverse in $H$ and $H$ is a group.
\lectureend{02/2}
\medskip
{\bf Useful Fact} If $G$ is a group and $H$ is a subgroup of $G$, then
$H=HH$. \Prf\ $HH=\{ab:a,\,b\in H\}\subseteq H$ just because $ab\in H$
for every $a$, $b\in H$. On the other hand,
$H=\{ae:a\in H\}\subseteq HH$ because $e\in H$.\ \Qed
\medskip
{\bf Cosets} Let $G$ be a group and $B$ a subset of $G$. Then a {\bf
left coset} of $B$ is a set of the form $aB=\{ab:b\in B\}=\{a\}B$ where
$a\in B$. Similarly, a {\bf right coset} of $B$ is a set of the form
$Ba=\{ba:b\in B\}$.
\medskip
\noindent{\bf Remark} It is essential to distinguish between a {\it
coset} of $B$ (which is just a subset of $G$) and its {\it name} $aB$ or
$Ba$. The point is that the same coset may be expressible as $aB$ in
many different ways, but is still only one set.
\medskip
{\bf Lemma} Let $G$ be a group and $H$ a subgroup of $G$. Then every
element of $G$ belongs to exactly one left coset of $H$.
\medskip
\noindent{\bf proof} Let $x$ be any point of $G$. Then $x=xe\in xH$ so
$x$ belongs to the left coset $xH$ of $H$.
Now suppose that $A$ is any left coset of $H$ containing $x$. Then $A$
is expressible as $aH$ for some $a\in H$. Since $x\in A=aH$,
\Centerline{$xH\subseteq(aH)H=a(HH)=aH=A$.}
\noindent On the other hand, there is an $h\in H$ such that $x=ah$.
Now
\Centerline{$a=ae=a(hh^{-1})=(ah)h^{-1}=xh^{-1}\in xH$,}
\noindent so $A=aH\subseteq xHH=xH$. Thus $A=xH$, and $xH$ is the only
left coset of $H$ containing $x$.
\medskip
\noindent{\bf Remark} Similarly, for any $x\in G$, $Hx$ is the only
right coset of $H$ containing $x$.
\medskip
{\bf Lemma} Let $G$ be a group and $H$ a finite subgroup of $G$. Then
every left coset of $H$ has exactly $\#(H)$ members.
\medskip
\noindent{\bf proof} Let $A$ be a left coset of $H$. Then $A$ is
expressible as $aH$ where $a\in G$. Consider the function
\Centerline{$h\mapsto ah:H\to aH$.}
\noindent This is surjective by the definition of $aH$. On the other
hand, if $ah=ah'$, then $h=h'$, by the cancellation law. So
$h\mapsto ah$ is injective, and is a bijection between $H$ and $aH$.
Accordingly $A=aH$ and $H$ must have the same number of members.
\medskip
{\bf Theorem} Let $G$ be a finite group and $H$ any subgroup of $G$.
Then
\Centerline{$\#(G)=\#(H)\times$(number of left cosets of $H$).}
\medskip
\noindent{\bf proof} The left cosets of $H$ cut $G$ up into disjoint
sets which are all of the same size $\#(H)$.
\medskip
{\bf Corollary (Lagrange's Theorem)} If $G$ is a finite group and $H$ is
a subgroup of $G$, then $\#(H)$ is a factor of $\#(G)$.
\medskip
{\bf Example} Consider the group $S_3$ of bijections from $\{1,2,3\}$ to
itself. This has 6 elements, being
\Centerline{$e$,\quad$\rho=\cycle{1 2 3}$,
\quad$\rho^2=\cycle{1 3 2}$,}
\Centerline{$\sigma=\cycle{1 2}$, \quad$\rho\sigma=\cycle{1 3}$,
\quad$\rho^2\sigma=\cycle{2 3}$;}
\noindent we have $\rho^3=\sigma^2=e$ and $\sigma\rho=\rho^2\sigma$, so
that $\sigma^{-1}=\sigma$ and $\rho^{-1}=\rho^2$.
The sets $H=\{e,\rho,\rho^2\}$ and $K=\{e,\sigma\}$ are subgroups of
$S_3$. Their cosets are
$$H=eH=\rho H=\rho^2H=He=H\rho=H\rho^2,$$
$$\eqalign{\{\sigma,\rho\sigma,\rho\sigma^2\}
&=\sigma H=(\rho\sigma)H=(\rho^2\sigma)H\cr
&=H\sigma=H(\rho\sigma)=H(\rho^2\sigma);\cr}$$
$$K=eK=\sigma K,\quad\{\rho,\rho\sigma\}=\rho K=(\rho\sigma)K,
\quad\{\rho^2,\rho^2\sigma\}=\rho^2K=(\rho^2\sigma)K,$$
$$K=Ke=K\sigma,\quad\{\rho,\rho^2\sigma\}=K\rho=K(\rho^2\sigma),
\quad\{\rho^2,\rho\sigma\}=K\rho^2=K(\rho\sigma).$$
\noindent Note that all the left cosets of $H$ are right cosets, and
vice versa; but that the left and right cosets of $K$ are different,
except of course for $eK=Ke=K$.
\lectureend{02/3}
\bigskip
\noindent{\bf Normal subgroups: Definition} If $G$ is a group, a {\bf
normal subgroup} of $G$ is a subgroup $H$ such that $aH=Ha$ for every
$a\in G$; in this case we write $H\normalsubgroup G$.
\medskip
{\bf Remark} If $H$ is a subgroup of $G$, then it is normal iff
$aha^{-1}\in H$ for every $h\in H$, $a\in G$. \Prf\ (i) If
$H\normalsubgroup G$, $a\in G$ and $h\in H$, then
$aha^{-1}\in aHa^{-1}=aa^{-1}H=eH=H$. (ii) If $H$ satisfies the
condition and $a\in G$, then
\Centerline{$aHa^{-1}=\{aha^{-1}:h\in H\}\subseteq H$,}
\noindent so $aH=aHe=aHa^{-1}a\subseteq Ha$. Similarly,
$a^{-1}H\subseteq Ha^{-1}$ and $Ha=eHa=aa^{-1}Ha\subseteq aHa^{-1}a=aH$.
So $aH=Ha$. As $a$ is arbitrary, $H\normalsubgroup G$.\ \Qed
\medskip
{\bf Theorem} If $G$ is a group and $H\normalsubgroup G$, then the set
$G/H$ of cosets of $H$ is a group under multiplication of subsets.
\medskip
\noindent{\bf proof (a)} (The key) If $a$, $b\in G$ then
\Centerline{$(aH)(bH)=a(Hb)H=a(bH)H=(ab)(HH)=abH$}
\noindent (remember that $HH=H$ for any subgroup $H$ of $G$).
\medskip
{\bf (b)(i)} If $A$, $B\in G/H$ we can express them as $aH$, $bH$ where
$a$, $b\in G$; now $AB=aHbH=abH\in G/H$. Thus multiplication of
subsets is a binary operation on $G/H$.
\medskip
\quad{\bf (ii)} Multiplication of subsets is an associative operation on
$\Cal PG$, so $G/H$ is a semigroup.
\medskip
\quad{\bf (iii)} $H=eH\in G/H$. If $A\in G/H$, we can express it as
$aH$ where $a\in G$; now
\Centerline{$AH=aHeH=aeH=aH=A$,
\quad$HA=eHaH=eaH=aH=A$.}
\noindent So $H$ is the identity of $G/H$.
\medskip
\quad{\bf (iv)} If $A\in G/H$, we can express it as $aH$ where $a\in G$;
now $B=a^{-1}H\in G/H$, and
\Centerline{$AB=aHa^{-1}H=aa^{-1}H=eH=H$,
\quad$BA=a^{-1}HaH=a^{-1}aH=eH=H$.}
\noindent Thus $B$ is the inverse of $A$ in $G/H$. As $A$ is
arbitrary, every element of $G/H$ has an inverse and $G/H$ is a group.
\bigskip
\noindent{\bf Homomorphisms: Definition} If $G$ and $H$ are groups, a
function $\phi:G\to H$ is a {\bf homomorphism} if
$\phi(ab)=\phi(a)\phi(b)$ for all $a$, $b\in G$.
\medskip
\noindent{\bf Remark} Note that in the formula
\Centerline{$\phi(ab)=\phi(a)\phi(b)$}
\noindent we are using two different multiplications. In the product
$ab$ we are using the group operation of $G$ and in the product
$\phi(a)\phi(b)$ we are using the group operation of $H$. A stricter
notation would be to say `if $(G,\cdot)$ and $(H,*)$ are groups, a
function $\phi:G\to H$ is a homomorphism if $\phi(a\cdot
b)=\phi(a)*\phi(b)$ for all $a$, $b\in G$'. A typical example would be
the function $\exp:\Bbb R\to\ooint{0,\infty}$. Since
$\exp(x+y)=\exp(x)\times\exp(y)$ for all real $x$ and $y$, this is a
homomorphism from the group $(\Bbb R,+)$ to the group
$(\ooint{0,\infty},\times)$.
\medskip
{\bf Theorem} Let $G$, $H$ be groups and $\phi:G\to H$ a homomorphism.
Then,
writing $e_G$ for the identity of $G$ ad $e_H$ for the identity of $H$,
\Centerline{$\phi(e_G)=e_H$,\quad$\phi(a^{-1})=\phi(a)^{-1}$ for every
$a\in G$.}
\medskip
\noindent{\bf proof (a)}
\Centerline{$e_H\phi(e_G)=\phi(e_G)=\phi(e_Ge_G)=\phi(e_G)\phi(e_G)$;}
\noindent cancelling $e_G$ on the right, $e_H=\phi(e_G)$.
\medskip
{\bf (b)}
\Centerline{$\phi(a)^{-1}\phi(a)=e_H=\phi(e_G)=\phi(a^{-1}a)
=\phi(a^{-1})\phi(a)$;}
\noindent cancelling $\phi(a)$ on the right, $\phi(a)^{-1}=\phi(a)^{-
1}$.
\medskip
{\bf Examples (i)} If $G=(\Bbb R,+)$, $H=(\ooint{0,\infty},\times)$ and
$\phi=\exp$, then $e_G=0$ and $e_H=1=\exp(0)$; if $x\in G$, its inverse
in $G$ is $-x$, and $\exp(-x)=\Bover1{\exp(x)}$ is the inverse of
$\exp(x)$ in $H$.
\medskip
\quad{\bf (ii)} If $G$ is any group and $H\normalsubgroup G$, then the
map $a\mapsto aH:G\to G/H$ is a homomorphism (because $aHbH=abH$ for all
$a$,
$b\in G$); the image of $e_G$ is $e_GH=H$, the identity of $G/H$; and
for any $a\in G$ the image of $a^{-1}$ is $a^{-1}H$, which is the
inverse of $aH$ in $G/H$.
\medskip
{\bf Theorem} Let $G$, $H$ and $K$ be groups, and $\phi:G\to H$,
$\psi:H\to K$ homomorphisms. Then $\psi\phi:G\to K$ is a homomorphism.
\medskip
\noindent{\bf proof} If $a$, $b\in G$, then
$$\eqalignno{(\psi\phi)(ab)
&=\psi(\phi(ab))=\psi(\phi(a)\phi(b))\cr
\displaycause{because $\phi$ is a homomorphism}
&=\psi(\phi(a))\psi(\phi(b))\cr
\displaycause{because $\psi$ is a homomorphism}
&=(\psi\phi)(a)(\psi\phi)(b).\cr}$$
\medskip
\noindent{\bf Remark} Note that in the line
\Centerline{$(\psi\phi)(ab)=\psi(\phi(a)\phi(b))
=\psi(\phi(a))\psi(\phi(b))$}
\noindent we are using three different multiplications; a stricter
notation would be to say that if $\cdot$, $*$ and $\times$ are the
multiplications in $G$, $H$ and $K$ respectively, then
\Centerline{$(\psi\phi)(a\cdot b)=\psi(\phi(a)*\phi(b))
=\psi(\phi(a))\times\psi(\phi(b))$.}
\medskip
{\bf Definition} If $G$ and $H$ are groups, an {\bf isomorphism} from
$G$ to $H$ is a bijective homomorphism. We say that $G$ and $H$ are
{\bf isomorphic},
$G\cong H$, if there is an isomorphism from $G$ to $H$.
\medskip
{\bf Proposition} If $\phi:G\to H$ is an isomorphism, then $\phi^{-
1}:H\to G$ is a homomorphism, therefore an isomorphism.
\medskip
\noindent{\bf proof} Because $\phi:G\to H$ is a bijection, $\phi^{-
1}:H\to G$ is defined, and is a bijection. If $a$, $b\in H$ then
\Centerline{$\phi(\phi^{-1}(a)\phi^{-1}(b))
=\phi(\phi^{-1}(a))\cdot\phi(\phi^{-1}(b))=ab
=\phi(\phi^{-1}(ab))$;}
\noindent because $\phi$ is injective,
$\phi^{-1}(a)\phi^{-1}(b)=\phi^{-1}(ab)$; as $a$ and $b$ are arbitrary,
$\phi^{-1}$ is a homomorphism. Since it is also a bijection, it is an
isomorphism.
\medskip
\noindent{\bf Remark} This proposition is not a happy accident. If it
hadn't been true we would have changed the definition of `isomorphism'
until it was.
\medskip
{\bf Proposition} Isomorphism is an equivalence relation on the class of
groups.
\medskip
\noindent{\bf proof} If $G$ is any group, let $\iota:G\to G$ be the
identity map. Then $\iota$ is an isomorphism from $G$ to itself so
$G\cong G$. Thus $\cong$ is reflexive.
If $G\cong H$, let $\phi:G\to H$ be an isomorphism. Then (by the last
proposition) $\phi^{-1}:H\to G$ is an isomorphism, so $H\cong G$. Thus
$\cong$ is symmetric.
If $G\cong H$ and $H\cong K$, let $\phi:G\to H$ and $\psi:H\to K$ be
isomorphisms. Then $\psi\phi:G\to K$ is a composition of
homomorphisms, so is a homomorphism, and is a composition of bijections,
so is a bijection. Accordingly $\psi\phi$ is an isomorphism from $G$
to $K$, and $G\cong K$. Thus $\cong$ is transitive.
Being reflexive, symmetric and transitive, $\cong$ is an equivalence
relation.
\medskip
{\bf Definition} Let $G$ and $H$ be groups, and $\phi:G\to H$ a
homomorphism.
The {\bf kernel} of $\phi$ is $\kernel\phi=\{a:a\in G,\,\phi(a)=e_H\}$;
the {\bf image} of $\phi$ is $\phi[G]=\{\phi(x):x\in G\}$.
\medskip
{\bf Theorem} Let $G$ and $H$ be groups, and $\phi:G\to H$ a
homomorphism.
(a) The kernel of $\phi$ is a normal subgroup of $G$.
(b) The image of $\phi$ is a subgroup of $H$.
\medskip
\noindent{\bf proof (a)} Write $K$ for the kernel of $\phi$. Then
$e_G\in K$ because $\phi(e_G)=e_H$. If $x$, $y\in K$, then
\Centerline{$\phi(xy)=\phi(x)\phi(y)=e_He_H=e_H$,}
\noindent so $xy\in K$. If $x\in K$, then
\Centerline{$\phi(x^{-1})=\phi(x)^{-1}=e_H^{-1}=e_H$,}
\noindent so $x^{-1}\in K$. Thus $K$ is a subgroup of $G$. If $x\in
G$ and $k\in K$ then
\Centerline{$\phi(xkx^{-1})=\phi(x)\phi(k)\phi(x^{-1})
=\phi(x)\cdot e_H\cdot\phi(x)^{-1}
=\phi(x)\phi(x)^{-1}=e_H$,}
\noindent so $xkx^{-1}\in K$; as $x$ and $k$ are arbitrary,
$K\normalsubgroup G$.
\medskip
\quad{\bf (b)} $e_H\in \phi[G]$ because $e_H=\phi(e_G)$. If $a$, $b\in
\phi[G]$ there are $x$, $y\in G$ such that $\phi(x)=a$ and $\phi(y)=b$;
now
\Centerline{$ab=\phi(x)\phi(y)=\phi(xy)\in \phi[G]$.}
\noindent If $a\in \phi[G]$ there is an $x\in G$ such that $\phi(x)=a$,
and now
\Centerline{$a^{-1}=\phi(x)^{-1}=\phi(x^{-1})\in \phi[G]$.}
\noindent Thus $\phi[G]$ is a subgroup of $G$.
\medskip
{\bf Proposition} Let $G$ and $H$ be groups, and $\phi:G\to H$ a
homomorphism.
Then $\phi$ is injective iff $\kernel\phi=\{e_G\}$.
\medskip
\noindent{\bf proof (a)} If $\phi$ is injective, then surely
$e_G\in\kernel\phi$. But also
\Centerline{$x\in\kernel\phi\Rightarrow\phi(x)=e_H=\phi(e_G)\Rightarrow
x=e_G$,}
\noindent so $\kernel\phi$ contains no other element and is $\{e_G\}$
exactly.
\medskip
{\bf (b)} If $\phi$ is not injective, let $x$, $y\in G$ be distinct
elements such that $\phi(x)=\phi(y)$. Then
\Centerline{$\phi(x^{-1}y)=\phi(x)^{-1}\phi(y)=\phi(y)^{-
1}\phi(y)=e_H$,}
\noindent so $x^{-1}y\in\kernel\phi$. But $x^{-1}y\ne e_G$ (because
$xx^{-1}y=y\ne x=xe_G$, for instance), so $\kernel\phi\ne\{e_G\}$.
\medskip
{\bf The First Isomorphism Theorem} Let $G$ and $H$ be groups, and
$\phi:G\to H$ a homomorphism with kernel $K$. Then the quotient $G/K$
is isomorphic to the image $\phi[G]$ of $\phi$.
\medskip
\noindent{\bf proof} Note that because $K\normalsubgroup G$, we have a
group $G/K$, and because $\phi[G]\le H$, we can regard $\phi[G]$ as a
group in its own right.
\medskip
{\bf (a)} (The key.) If $x$, $y\in G$, then $xK=yK$ iff
$\phi(x)=\phi(y)$. \Prf\ (i) If $xK=yK$, then $y=ye\in K$, so there is
a $k\in K$ such that $y=xk$; now
\Centerline{$\phi(y)=\phi(x)\phi(k)=\phi(x)e_H=\phi(x)$.}
\noindent(ii) If $\phi(x)=\phi(y)$, then
\Centerline{$\phi(x^{-1}y) =\phi(x)^{-1}\phi(y) =\phi(x)^{-
1}\phi(x)=e_H$,}
\noindent and $x^{-1}y\in K$; accordingly $y=xx^{-1}y\in xK$ and
$yK=xK$.\ \Qed
\medskip
{\bf (b)} We can therefore safely define a function $\psi:G/K\to\phi[G]$
by setting $\psi(xK)=\phi(x)$ for every $x\in G$.
If $A$, $B\in G/K$, there are $x$, $y\in G$ such that $A=xK$ and $B=yK$;
now
$AB=xyK$ so
\Centerline{$\psi(AB)=\phi(xy)=\phi(x)\phi(y)=\psi(A)\psi(B)$.}
\noindent Thus $\psi$ is a homomorphism.
If $A$, $B\in G/K$ and $\psi(A)=\psi(B)$, there are $x$, $y\in G$ such
that $A=xK$ and $B=yK$; now
\Centerline{$\phi(x)=\psi(A)=\psi(B)=\phi(y)$}
\noindent so $A=B$ by (a) above. Thus $\psi$ is injective.
If $a\in\phi[G]$ there is an $x\in G$ such that $a=\phi(x)=\psi(xK)$;
thus $\psi:G/K\to H$ is surjective.
Putting these together, $\psi:G/K\to H$ is a bijective homomorphism,
that is, an isomorphism.
\medskip
{\bf Cyclic groups} Let $G$ be any group and $a\in G$. Define $a^n$
inductively, for $n\in\Bbb N$, by setting $a^0=e$, $a^{n+1}=a^na$ for
every $n\in\Bbb N$. (Thus $a^1=ea=a$, $a^2=a^1a=aa$,
$a^3=a^2a,\ldots,a^{71}=a^{70}a,\ldots$.) Now for integers $m\le 0$,
set $a^m=(a^{-1})^{-m}$. (Note that if $m=0$, this definition gives
$a^0=(a^{-1})^0=e$, as before.)
\medskip
{\bf Proposition} If $G$ is a group and $a\in G$, $a^{m+n}=a^ma^n$ for
all $m$, $n\in\Bbb Z$.
\medskip
\noindent{\bf *proof (a)} $a^{-n+1}=a^{-n}a$ for every integer $n\ge 1$.
\Prf\ $-n+1\le 0$ and $n-1\ge 0$ so
\Centerline{$a^{-n}a=(a^{-1})^na=(a^{-1})^{n-1}a^{-1}a=(a^{-1})^{n-1}
=a^{-n+1}$. \Qed}
Consequently $a^{m+1}=a^ma$ for every $m\in\Bbb Z$. \Prf\ This is the
definition of $a^{m+1}$ if $m\ge 0$, and otherwise is covered by what I
have
just shown.\ \Qed
\medskip
{\bf (b)} $a^{m+n}=a^ma^n$ for all $m\in\Bbb Z$, $n\in\Bbb N$. \Prf\
Induce on $n$. If $n=0$ we have to show that $a^{m+0}=a^ma^0$, which
is true, because $a^0=e$. For the inductive step to $n+1$, we have
$$\eqalignno{a^{m+(n+1)}
&=a^{(m+n)+1}=a^{m+n}a\cr
\displaycause{by (a)}
&=a^ma^na\cr
\displaycause{by the inductive hypothesis}
&=a^ma^{n+1}\cr}$$
\noindent by the definition of $a^{n+1}$. Thus the induction
proceeds.\ \Qed
\medskip
{\bf (c)} $a^{-m}=(a^{-1})^m$ for every $m\in\Bbb Z$. \Prf\ For $m\ge
0$, this is the definition of $a^{-m}$. For $m<0$, say $m=-n$ where
$n\in\Bbb N$, we have
\Centerline{$(a^{-1})^m=(a^{-1})^{-n}=((a^{-1})^{-1})^n=a^n$. \Qed}
\medskip
{\bf (d)} $a^{m+n}=a^ma^n$ for all $m$, $n\in\Bbb Z$. \Prf\ If $n\ge
0$ this is in (b). If $n<0$, then
$$\eqalign{a^ma^n
&=(a^{-1})^{-m}(a^{-1})^{-n}\cr
\displaycause{by (c)}
&=(a^{-1})^{-m-n}\cr
\displaycause{by (b), because $-n\ge 0$}
&=a^{m+n}\cr}$$
\noindent by (c) again.\ \QeD\ So the proof is complete.
\medskip
\noindent{\bf Remark} What this says is that the map $n\mapsto a^n:\Bbb
Z\to G$ is a homomorphism between the groups $(\Bbb Z,+)$ and
$(G,\cdot)$.
Its image $\{a^n:n\in\Bbb Z\}$ is therefore a subgroup of $G$ (the {\bf
cyclic subgroup generated by} $a$, sometimes written $$), and its
kernel
$K=\{n:a^n=e\}$ is a (normal) subgroup of $\Bbb Z$. (Of course all
subgroups of $\Bbb Z$ are normal, because $\Bbb Z$ is abelian.)
Moreover,
$\cong\Bbb Z/K$, by the First Isomorphism Theorem.
\medskip
{\bf Subgroups of $\Bbb Z$: Proposition} A subset $K$ of $\Bbb Z$ is a
subgroup iff it is of the form $n\Bbb Z=\{mn:m\in\Bbb Z\}$ for some
$n\in\Bbb N$.
\medskip
\noindent{\bf proof (a)} For any $n\in\Bbb Z$, the map
$m\mapsto mn:\Bbb Z\to\Bbb Z$ is a homomorphism (because
$(m+m')n=mn+m'n$ for all $m$, $m'$), so its image $n\Bbb Z$ is a
subgroup of $\Bbb Z$.
\medskip
{\bf (b)} Suppose that $K\le\Bbb Z$ is a subgroup.
\medskip
\quad{\bf case (i)} If $K=\{0\}$ then $K=0\Bbb Z$ is of the required
form.
\medskip
\quad{\bf case (ii)} Otherwise, there is a non-zero $k_0\in K$. Now $-
k_0$ is the inverse of $k_0$ in the group $(\Bbb Z,+)$, so also belongs
to $K$, and one of $k_0$, $-k_0$ is greater than $0$; so $K$ contains
some strictly positive integer. Let $n$ be the {\it least} member of
$K\cap\Bbb N\setminus\{0\}$.
Then $mn\in K$ for every $m\in\Bbb N$ (induce on $m$). If $k\in
K\cap\Bbb N$, then $k$ is expressible as $mn+j$ where $m\in\Bbb N$ and
$0\le j=\{a^m:m\in\Bbb Z\}$ is isomorphic to $\Bbb Z/n\Bbb
Z$ for some $n\in\Bbb N$, and this in turn is either isomorphic to $\Bbb
Z$ (if the homomorphism $m\mapsto a^m$ is injective) or to $(\Bbb
Z_n,+_n)$ (if $n$ is the least strictly positive integer belonging to
the kernel of the homomorphism, that is, such that $a^m=e$.) Moreover,
we can find out which, because if $$ is infinite it must be
isomorphic to $\Bbb Z$, and if it has $n$ members it must be isomorphic
to $\Bbb Z_n$. Of course $\Bbb Z_1=\{0\}$ is the trivial group; this
is what we get if $a=e$, $=\{e\}$.
\medskip
{\bf Definition} If $G$ is a group, the {\bf order} of an element $a$ of
$G$ is $\#()$.
\medskip
\noindent{\bf Remarks} If the order of $a$ is $n\in\Bbb N$, then $n$ is
the least integer (greater than $0$) such that $a^n=e$, and
$\cong\Bbb Z/n\Bbb Z\cong\Bbb Z_n$; if the order of $a$ is infinite,
then $\cong\Bbb Z$.
\medskip
\bigskip
{\bf Permutation Groups}
{\bf Theorem} If $X$ is any set, the set of bijections from $X$ to $X$
is a group under composition of functions.
\medskip
\noindent{\bf proof} It is the group of invertible elements of the
semigroup of all functions from $X$ to itself.
\medskip
{\bf Definitions} For $n\ge 1$, I will write $S_n$ for the group of all
bijections from $\{1,2,\,\ldots,n\}$ to itself.
For distinct $i_1,\ldots,i_k\le n$, $\cycle{i_1\,i_2\,\ldots\,i_k}$ will
be the permutation $\rho\in S_n$ defined by saying that
\inset{$\rho(i_1)=i_2$, $\rho(i_2)=i_3,\ldots,\rho(i_{k-1})=i_k$,
$\rho(i_k)=i_1$
and $\rho(j)=j$ for all other $j\le n$.}
We say that two cycles $\cycle{i_1\ldots i_k}$ and $\cycle{j_1\ldots
j_l}$ are {\bf disjoint} if $i_r\ne j_s$ for $r\le k$, $s\le l$; that
is, if all the numbers moved by one of the cycles is left alone by the
other.
\medskip
\noindent{\bf Remark} Permutations are functions. So when we multiply
two cycles together, say $\rho=\cycle{1 2 3 4}$ and $\sigma=\cycle{2 3 4
5}$, then
\inset{$\cycle{1 2 3 4}\cycle{2 3 4 5}(1)
=(\rho\sigma)(1)=\rho(\sigma(1))=\rho(1)=2$,
$\cycle{1 2 3 4}\cycle{2 3 4 5}(2)
=(\rho\sigma)(2)=\rho(\sigma(2))=\rho(3)=4$,
$\cycle{1 2 3 4}\cycle{2 3 4 5}(3)
=(\rho\sigma)(3)=\rho(\sigma(3))=\rho(4)=1$,
$\cycle{1 2 3 4}\cycle{2 3 4 5}(4)
=(\rho\sigma)(4)=\rho(\sigma(4))=\rho(5)=5$,
$\cycle{1 2 3 4}\cycle{2 3 4 5}(5)
=(\rho\sigma)(5)=\rho(\sigma(5))=\rho(2)=3$.}
\noindent So
\Centerline{$\cycle{1 2 3 4}\cycle{2 3 4 5}=\cycle{1 2 4 5 3}$.}
\medskip
{\bf Theorem} Any permutation in $S_n$ can be expressed as a product of
disjoint cycles. The expression is unique except that
\quad(i) you may write the cycles in any order
\hfill[$\cycle{1 2 3}\cycle{4 5}=\cycle{4 5}\cycle{1 2 3}$]
\quad(ii) you may start a cycle at any point of the cycle
\hfill[$\cycle{1 2 3 4}=\cycle{2 3 4 1}=\cycle{3 4 1 2}$]
\quad(iii) you may include one-cycles $\cycle{i}$ or omit them as you
like
\hfill[$\cycle{1}$ is the identity permutation.]
\medskip
{\bf The order of a permutation} A cycle $\rho=\cycle{i_1\ldots i_k}$
moves the numbers $i_1\ldots i_k$ in a circle; it will take just $k$
moves to get them
back to their original positions, so the order of $\rho$ is $k$.
If we have expressed a permutation $\rho$ as a product
$\rho_1\rho_2\ldots\rho_r$ of disjoint cycles, then each of the $\rho_j$
is acting independently on a set with $k_j$ elements, where $k_j$ is the
order of $\rho_j$. Now a power $\rho^n$ of $\rho$ will get the
elements of the $j$th cycle back into their places iff $n$ is a multiple
of $k_j$. So we shall have
everything right iff $n$ is a multiple of every $k_j$, that is, $n$ is a
multiple of the least common multiple of all the $k_j$; the order of
$\rho$ is the l.c.m.\ of the orders of its disjoint cycles.
\medskip
{\bf Example} The order of
\Centerline{$\cycle{1\,2}\cycle{3\,4\,5}\cycle{6\,7\,8\,9}
\cycle{10\,11\,12\,13\,14\,15}$}
\noindent is lcm(2,3,4,6)=12.
\medskip
{\bf Inverses} For any cycle we can find its inverse by just writing it
backwards: $\cycle{1 2 3 4}^{-1}=\cycle{4 3 2 1}$. For a product of
cycles the same rule applies:
\Centerline{$(\cycle{1 2 3}\cycle{2 3 4}\cycle{3 4 5})^{-1}
=\cycle{3 4 5}^{-1}\cycle{2 3 4}^{-1}\cycle{1 2 3}^{-1}
=\cycle{5 4 3}\cycle{4 3 2}\cycle{3 2 1}$.}
\noindent(It doesn't matter here whether the cycles are disjoint or not;
but
if they aren't disjoint then we must make sure to write them in the
correct order.)
\medskip
{\bf Definition} A {\bf transposition} is a 2-cycle, that is, a
permutation of the form $\cycle{i j}$ exchanging two numbers $i$ and $j$
and leaving everything else unmoved.
\medskip
{\bf Proposition} Any permutation in $S_n$ can be expressed as a product
of transpositions (counting the identity as a product of no
transpositions).
\medskip
\noindent{\bf proof} Observe that any cycle of length $k\ge 2$ is a
product of $k-1$ transpositions; e.g.,
\Centerline{$\cycle{1 2 3\ldots k}
=\cycle{1 k}\cycle{1\,\,k\hbox{-}1}\ldots\cycle{1 3}\cycle{1 2}$.}
\noindent Now any permutation is a product of cycles (counting $e$ as a
product of no cycles) and therefore a product of transpositions.
\bigskip
\noindent{\bf The signature of a permutation} Let $n\ge 1$ be an
integer, and $\rho\in S_n$ a permutation. Write $c(\rho)$ for the
number of cycles in the disjoint-cycle representation of $\rho$,
counting one-cycles.
\indent{Thus if $n=6$ and $\rho=\cycle{1 2 3}\cycle{4 5}$, $c(\rho)=3$,
because we must count the one-cycle
$\cycle{6}$ as part of the representation of $\rho$.}
\noindent Now we say that $\rho$ is {\bf even}, with {\bf signature}
$\epsilon_{\rho}=(-1)^{n-c(\rho)}=1$, if $n-c(\rho)$ is even, and
otherwise we say that $\rho$ is {\bf odd}, with signature
$\epsilon_{\rho}=(-1)^{n-c(\rho)}=-1$.
\medskip
\noindent{\bf Remark} Note that if we interpret $\cycle{1 2}\cycle{3 4}$
as a member of $S_4$, then its signature is $(-1)^{4-2}=1$; while if we
interpret it as a member of $S_5$, we have to re-write it as
$\cycle{1 2}\cycle{3 4}\cycle{5}$, so that its signature is $(-1)^{5-3}$
is still $1$. This is an {\it even} permutation whichever $S_n$ we
think of it as belonging to.
\medskip
{\bf Lemma} If $\tau\in S_n$ is a transposition, then
$\epsilon_{\tau\rho}=-\epsilon_{\rho}$ for any $\rho\in S_n$.
\medskip
\noindent{\bf proof} Start by expressing $\rho$ as a product of disjoint
cycles, including one-cycles if necessary. Suppose that
$\tau=\cycle{i j}$ where $i$, $j\le n$ are distinct.
\quad{\bf case 1} Suppose that $i$ and $j$ belong to different cycles of
$\rho$. Since we can write the cycles in any order, we can put the one
containing $i$ at the left-hand end of the product, and the one
containing $j$ next to it; and since we can start any cycle at any
point, we can suppose that these cycles are written $\cycle{i\ldots}$
and $\cycle{j\ldots}$, so that
\Centerline{$\rho
=\cycle{i\ldots}\cycle{j\ldots}\cycle{\ldots}\ldots\cycle{\ldots}$}
\noindent (of course one or more of the strings suggested by $\ldots$
might be empty; if $\rho(i)=i$, then the leading cycle is just
$\cycle{i}$). In this case,
$$\eqalign{\tau\rho
&=\cycle{i j}\cycle{i\ldots}\cycle{j\ldots}
\cycle{\ldots}\ldots\cycle{\ldots}\cr
&=\cycle{i\ldots j\ldots}\cycle{j\ldots}
\cycle{\ldots}\ldots\cycle{\ldots},\cr}$$
\noindent so that $c(\tau\rho)=c(\rho)-1$ and
$\epsilon_{\tau\rho}=-\epsilon_{\rho}$.
\inset{Maybe this step will be more convincing with a couple of
examples:
\Centerline{$\cycle{1 2}\cycle{1 3 4 5}\cycle{2 6 7}\cycle{8 9}
=\cycle{1 3 4 5 2 6 7}\cycle{8 9}$,}
\Centerline{$\cycle{1 2}\cycle{1 3 4 5}\cycle{2}\cycle{7 8 9}
=\cycle{1 3 4 5 2}\cycle{7 8 9}$.}}
\quad{\bf case 2} If $i$ and $j$ belong to the same cycle as $\rho$,
bring it to the left-hand end of the product forming $\rho$ and start it
at $i$, so that
\Centerline{$\rho
=\cycle{i\ldots j\ldots}\cycle{\ldots}\ldots\cycle{\ldots}$}
\noindent and
$$\eqalign{\tau\rho
&=\cycle{i j}\cycle{i\ldots j\ldots}
\cycle{\ldots}\ldots\cycle{\ldots}\cr
&=\cycle{i \ldots}\cycle{j\ldots}
\cycle{\ldots}\ldots\cycle{\ldots}\cr}$$
\noindent has $c(\tau\rho)=c(\rho)+1$, so that once again $\rho$ and
$\tau\rho$ have opposite parity and
$\epsilon_{\tau\rho}=-\epsilon_{\rho}$.
\inset{Examples:
\Centerline{$\cycle{1 2}\cycle{1 3 4 2 5}\cycle{6 7 8 9}
=\cycle{1 3 4}\cycle{2 5}\cycle{6 7 8 9}$,}
\Centerline{$\cycle{1 2}\cycle{1 2 3 4 5}
=\cycle{1}\cycle{2 3 4 5}$.}}
\medskip
{\bf Theorem} Suppose that $n\ge 1$.
(a) $\rho\in S_n$ is even/odd iff it can be expressed as the product of
an even/odd number of transpositions.
(b) $\epsilon_{\rho\sigma}=\epsilon_{\rho}\epsilon_{\sigma}$ for all
$\rho$, $\sigma\in S_n$.
\medskip
\noindent{\bf proof (a)} Note first that
$e=\cycle{1}\cycle{2}\ldots\cycle{n}$ has $c(e)=n$ so that
$\epsilon_e=(-1)^{n-n}=1$. Next, any $\rho$ can certainly be expressed
as a product $\tau_k\tau_{k-1}\ldots\tau_2\tau_1$ where every $\tau_j$
is a transposition, allowing the case $\rho=e$, $k=0$. In this case,
\inset{$\epsilon_e=1$,
$\epsilon{\tau_1}=\epsilon_{\tau_1e}=-\epsilon_e=-1$,
$\epsilon{\tau_2\tau_1}=-\epsilon_{\tau_1}=-(-1)=(-1)^2=1$,
$\epsilon{\tau_3\tau_2\tau_1}=-\epsilon_{\tau_2\tau_1}=(-1)^3=-1$,
$\ldots$
$\epsilon{\tau_k\ldots\tau_3\tau_2\tau_1}
=(-1)^k=1$ if $k$ is even, $-1$ if $k$ is odd.}
\medskip
{\bf (b)} Now if $\rho=\tau_1\tau_2\ldots\tau_k$ and
$\sigma=\tau_1'\tau_2'\ldots\tau_l'$, where all the $\tau_i$, $\tau'_j$
are transpositions, $\rho\sigma=\tau_1\ldots\tau_k\tau'_1\ldots\tau'_l$
is the product of $k+l$ transpositions, so that
\Centerline{$\epsilon_{\rho\sigma}=(-1)^{k+l}
=(-1)^k(-1)^l=\epsilon_{\rho}\epsilon_{\sigma}$.}
\medskip
{\bf The group of even permutations} The formula
`$\epsilon_{\rho\sigma}=\epsilon_{\rho}\epsilon_{\sigma}$' can be
interpreted as saying: $\epsilon:S_n\to\{-1,1\}$ is a homomorphism, if
$\{-1,1\}$ is regarded as a group under multiplication (a subgroup of
$(\Bbb R\setminus\{0\},\times)$, or the group of invertible elements of
the semigroup $(\Bbb Z,\times)$). Its kernel is $A_n$, the group of
even permutations, which is therefore a normal subgroup of $S_n$.
Except in the case $n=1$ (in which case $S_1=\{e\}=A_1$ has just one
element), there is a transposition $\tau=\cycle{1 2}$, so that
$\epsilon:S_n\to\{-1,1\}$ is surjective and $S_n/A_n\cong\{-1,1\}$ (by
the First Isomorphism Theorem). In particular, $A_n$ has just two
cosets, itself and its complement, and
$\#(A_n)=\Bover12\#(S_n)=\Bover{n!}2$.
\bigskip
\noindent{\bf Normal subgroups of $A_n$ and $S_n$} It is a very
remarkable fact that $A_n$ and $S_n$ have very few normal subgroups.
Actually
\inset{the normal subgroups of $A_n$ are exactly $\{e\}$ and $A_n$
itself, except when $n=4$, in which case
$K=\{e,\cycle{1 2}\cycle{3 4},\cycle{1 3}\cycle{2 4},
\cycle{1 4}\cycle{2 3}\}$ is a normal subgroup of $A_4$;
the normal subgroups of $S_n$ are $\{e\}$, $A_n$ and $S_n$ itself,
except when $n=4$, in which case
$K=\{e,\cycle{1 2}\cycle{3 4},\cycle{1 3}\cycle{2 4},
\cycle{1 4}\cycle{2 3}\}$ is a normal subgroup of $S_4$.}
\noindent The proof of this is long but very instructive. I will break
it up into a string of lemmas; most of these have non-trivial ideas in
them, but will
I hope still be manageable, if you can remember the order they come in.
The first result is actually a bit more than a `lemma'. Since we are
talking about normal subgroups of $S_n$ and $A_n$, we are repeatedly
going to want to look at expressions of the form $\rho\sigma\rho^{-1}$
where $\rho$, $\sigma\in S_n$. Now when $\sigma$ is a cycle, this can
be calculated particularly easily, as follows.
\medskip
{\bf Proposition} If $\sigma=\cycle{i_1\,i_2\ldots i_k}$ is a simple
cycle in $S_n$, and $\rho\in S_n$, then $\rho\sigma\rho^{-1}$ is the
cycle $\cycle{\rho(i_1)\,\rho(i_2)\ldots\rho(i_k)}$.
\medskip
\noindent{\bf proof} Really this is just a direct calculation. If
$i\le n$ is of the form $\rho(i_j)$ where $j\le k$ then
$$\eqalign{\rho\sigma\rho^{-1}(i)=\rho\sigma(i_j)
&=\rho(i_{j+1})\text{ if }j=\{\iota,t\}\cong\Bbb Z_2$, then
$C\Rot(\text{cube})=\Isom(\text{cube})$ and the combination of
properties
\inset{$C\cong\Bbb Z_2$, $\Rot(\text{cube})\cong S_4$,
$C\cap\Rot(\text{cube})=\{\iota\}$,
$C\Rot(\text{cube})=\Isom(\text{cube})$,
$fg=gf$ for every $f\in\Rot(\text{cube})$ and every $g\in C$}
\noindent is enough to determine $\Isom(\text{cube})$ up to isomorphism.
\medskip
{\bf The isometry group of a regular octahedron} Every regular
octahedron has a cube inside it, with the vertices of the cube at the
centres of the faces of the octahedron. Isometries of the octahedron
take the cube to itself, and vice versa, so
$\Isom(\text{octahedron})\cong\Isom(\text{cube})$ and
$\Rot(\text{octahedron})\cong\Rot(\text{cube})\cong S_4$.
\medskip
{\bf The isometry group of a regular dodecahedron} A regular
dodecahedron has 20 vertices and 30 edges. In its faces we can
inscribe 5 cubes; each cube has each of its 12 edges in a different
face of the dodecahedron; two cubes meet at each vertex.
The dodecahedron has 60 rotations (you have 12 choices of where to put a
face, then 5 choices of which way round to put it; {\it or} you have 20
choices of where to put a vertex, then 3 places for one of its
neighbours; {\it or} you have 30 choices of where to put an edge, then
a choice of which way round its vertices should be). It has 120
isometries (after fixing two neighbouring vertices, you can now reflect
in the plane through them and the centre of the dodecahedron).
Any isometry of the dodecahedron acts as a permutation of the five
cubes, so we have a homomorphism $\phi:\Isom(\text{dodecahedron})\to
S_5$. Set $H=\phi[\Rot(\text{dodecahedron})]\cap A_5$, so that $H$ is
a subgroup of $S_5$ (being the intersection of two subgroups) and
therefore a subgroup of $A_5$. Now $H=A_5$.
\Prf\ {\bf method 1} If we look at a $120^{\circ}$ rotation about a long
diagonal, this leaves two of the cubes fixed and moves the other three
in a cycle, so $H$ contains a 3-cycle and has a subgroup of order 3.
If we look at a $72^{\circ}$ rotation about an axis through the
midpoints of a pair of opposite faces, this moves all five cubes in a
cycle, so $H$ contains a 5-cycle and has a subgroup of order 5.
If we look at a $180^{\circ}$ rotation about an axis through the
midpoints of a pair of opposite edges, this leaves one cube in place and
exchanges the others in pairs, so $H$ contains a double-transposition
and has a subgroup of order 2.
By Lagrange's theorem, $\#(H)$ must be a multiple of 3, 5 and 2 and
therefore is a multiple of 30. It is also a factor of 60. But $A_5$
has no normal subgroup of order 30, so can have no subgroup of order 30,
and $\#(H)\ne 30$. It follows that $\#(H)=60$ and $H=A_5$.
{\bf method 2} There are $\Bover{5\cdot 4\cdot 3}3=20$ 3-cycles in
$A_5$. Also there are 10 long diagonals of the dodecahedron, and about
each of these there are two $120^{\circ}$ rotations, one each way, each
corresponding to a 3-cycle in $A_5$. So every 3-cycle corresponds to a
rotation and belongs to $H$. Since every member of $A_5$ is a product
of 3-cycles, $H=A_5$.\ \Qed
Thus $\phi[\Rot(\text{dodecahedron})]$ includes $A_5$. But
$\#(\Rot(\text{dodecahedron}))=\#(A_5)$, so
$\phi[\Rot(\text{dodecahedron})]$ must be $A_5$ exactly, and
$\phi:\Rot(\text{dodecahedron})\to A_5$ must be a bijection, therefore
an isomorphism. So $\Rot(\text{dodecahedron})\cong A_5$.
Now $\#(\Isom(\text{dodecahedron}))=120=\#(S_5)$ and both
$\Isom(\text{dodecahedron})$ and $S_5$ have subgroups isomorphic to
$A_5$. However, $\Isom(\text{dodecahedron})\not\cong S_5$. \Prf\
Consider the isometry $t$ of the dodecahedron which takes every point to
its balancing point on the opposite side of the centre of the
dodecahedron. Then $t^2=\iota$ and $tf=ft$ for every
$f\in\Isom(\text{dodecahedron})$ (just as for the cube). So
$\{\iota,t\}$ is a normal subgroup of $\Isom(\text{dodecahedron})$ with
two elements, and we know that $S_5$ has no such subgroup.\ \Qed
Now let us try to classify the rotations of the dodecahedron.
(i) We know that there are $\Bover{5\cdot 4\cdot 3\cdot 2\cdot 1}5=24$
5-cycles in $A_5$. If we look at rotations about axes through
midpoints of opposite faces, we see that there are 6 such axes, and for
each axis there are two $72^{\circ}$ rotations (one each way) and two
$144^{\circ}$ rotations, all of which are of order 5; so between them
they give us $6\cdot 4=24$ rotations of order 5, which must correspond
to the 24 5-cycles in $A_5$.
Note that these 5-cycles come in two types: those corresponding to
$72^{\circ}$ rotations and those corresponding to $144^{\circ}$
rotations. What is happening here is that while in $S_5$ all 5-cycles
are conjugate, in $A_5$ the 5-cycles fall into two conjugacy classes
(just as the 3-cycles do in $A_4$).
(ii) We know that there are $\Bover{5\cdot 4\cdot 3}3=20$ 3-cycles in
$A_5$; as described in `method 2' above, all of these are got by
rotations about long diagonals.
(iii) There are $\Bover{5\cdot 4\cdot 3\cdot 2}{2\cdot 2\cdot 2}=15$
double-transpositions in $A_5$. Also there are 15 pairs of opposite
edges, so there are fifteen $180^{\circ}$ rotations about axes through
the midpoints of opposite edges. This means that every
double-transposition corresponds to such a rotation.
{\bf check}: $24+20+15=59$; add one for the identity, we have all the
members of $A_5$ and therefore all the rotations of the dodecahedron.
\bigskip
{\bf Group Actions}
\medskip
{\bf Definition} Let $G$ be a group and $X$ a set. An {\bf action} of
$G$ on $X$ is a function $(a,x)\mapsto a\action x:G\times X\to X$ such
that
\Centerline{$(ab)\action x=a\action(b\action x)$,
\quad$e\action x=x$}
\noindent whenever $a$, $b\in G$ and $x\in X$.
\medskip
{\bf Examples (a)} If $G$ is any group, the {\bf left action} of $G$ on
itself is defined by the formula
\Centerline{$a\action x=ax$ for all $a$, $x\in G$.}
\noindent To see that this is an action, we need only check that
\Centerline{$(ab)\action x=(ab)x=a(bx)=a\action(b\action x)$,}
\Centerline{$e\action x=ex=x$}
\noindent for all $a$, $b$, $x\in G$.
\medskip
{\bf (b)} If $G$ is any group, the {\bf right action} of $G$ on itself
is defined by the formula
\Centerline{$a\action x=xa^{-1}$ for all $a$, $x\in G$.}
\noindent To see that this is an action, we need only check that
\Centerline{$(ab)\action x=x(ab)^{-1}=x(b^{-1}a^{-1})
=(xb^{-1})a^{-1}=a\action(xb^{-1})=a\action(b\action x)$,}
\Centerline{$e\action x=xe^{-1}=x$}
\noindent for all $a$, $b$, $x\in G$.
\medskip
{\bf (c)} If $G$ is any group, the {\bf conjugacy action} of $G$ on
itself is defined by the formula
\Centerline{$a\action x=axa^{-1}$ for all $a$, $x\in G$.}
\noindent To see that this is an action, we need only check that
\Centerline{$(ab)\action x=(ab)x(ab)^{-1}=abxb^{-1}a^{-1}
=a(b\action x)a^{-1}=a\action(b\action x)$,}
\Centerline{$e\action x=exe^{-1}=x$}
\noindent for all $a$, $b$, $x\in G$.
\medskip
{\bf (d)} If $G=\Rot(\text{cube})$ is the rotation group of the cube,
and $X$ is the set of principal axes of the cube (i.e., axes through
midpoints of opposite faces), then $G$ acts on $X$, just because any
rotation of the cube must move pairs of opposite faces to pairs of
opposite faces.
\medskip
{\bf Theorem} Let $G$ be a group and $X$ a set. Any action of $G$ on
$X$ corresponds to a homomorphism $\phi$ from $G$ to the group $S_X$ of
all bijections from $X$ to itself, defined by the formula
\Centerline{$\phi(a)(x)=a\action x$ for $a\in G$, $x\in X$.}
\noindent Conversely, any homomorphism $\phi:G\to S_X$ corresponds to an
action.
\medskip
\noindent{\bf proof (a)} Given an action $\action:G\times X\to X$, then
the formula $\phi(a)(x)=a\action x$ defines a function $\phi(a):X\to X$
for every $a\in G$, just because $a\action x\in X$ for every $x\in X$
and $a\in G$.
If $a\in G$, then $\phi(a):X\to X$ is injective. \Prf\ If $x$, $y\in
X$ and $\phi(a)(x)=\phi(a)(y)$, then
$$\eqalign{x
&=e\action x=(a^{-1}a)\action x
=a^{-1}\action(a\action x)
=a^{-1}\action(\phi(a)(x))\cr
&=a^{-1}\action(\phi(a)(y))
=a^{-1}\action(a\action y)
=(a^{-1}\action a)\action y
=e\action y
=y. \text{\Qed}\cr}$$
If $a\in G$, then $\phi(a):X\to X$ is surjective. \Prf\ If $y\in X$,
then
\Centerline{$\phi(a)(a^{-1}\action y)=a\action(a^{-1}\action y)
=(aa^{-1})\action y=e\action y=y$. \Qed}
Thus $\phi(a)\in S_X$ for every $a\in G$, and $\phi$ is a function from
$G$ to $S_X$. Now $\phi$ is a homomorphism. \Prf\ If $a$, $b\in G$
and $x\in X$,
$$\eqalign{\phi(ab)(x)
&=(ab)\action x=a\action(b\action x)\cr
&=\phi(a)\bigl(\phi(b)(x)\bigr)
=\bigl(\phi(a)\circ\phi(b)\bigr)(x).\cr}$$
\noindent As $x$ is arbitrary,
\Centerline{$\phi(ab)=\phi(a)\circ\phi(b)$.}
\noindent As $a$ and $b$ are arbitrary, $\phi:G\to S_X$ is a
homomorphism.\ \Qed
This shows that, starting from an action $\action$ of $G$ on $X$, the
formula $\phi(a)(x)=a\action x$ defines a homomorphism from $G$ to
$S_X$.
\medskip
{\bf (b)} Now suppose that we have a homomorphism $\phi:G\to S_X$ and we
define a function $\action:G\times X\to X$ by the formula $a\action
x=\phi(a)(x)$. Then, writing $\iota:X\to X$ for the identity function,
$$\eqalign{(ab)\action x
&=\phi(ab)(x)
=\bigl(\phi(a)\circ\phi(b)\bigr)(x)\cr
&=\phi(a)\bigl(phi(b)(x)\bigr)
=a\action(b\action x),\cr
e\action x
&=\phi(e)(x)=\iota(x)=x\cr}$$
\noindent for all $a$, $b\in G$ and $x\in X$, because $\phi(e)$ must be
the identity of $S_X$, which is $\iota$. So $\action$ is an action.
\medskip
{\bf Corollary} If $\action$ is an action of a group $G$ on a set $X$,
then
\Centerline{$K=\{a:a\action x=x$ for every $x\in X\}$}
\noindent is a normal subgroup of $G$, and $G/K$ is isomorphic to a
subgroup of $S_X$.
\medskip
\noindent{\bf proof} If $\phi:G\to S_X$ is the homomorphism associated
with $\action$, then
\Centerline{$K=\{a:\phi(a)(x)=x\Forall x\in X\}=\{a:\phi(a)=\iota\}$}
\noindent is the kernel of $\phi$, so is a normal subgroup of $G$, and
$G/K\cong\phi[G]\le S_X$ by the First Isomorphism Theorem.
\medskip
\noindent{\bf Remark} $\{a:a\action x=x$ for every $x\in X\}$ may be
called the {\bf kernel} of the action.
\medskip
{\bf Example} When $G=\Rot(\text{cube})$ and $X$ is the set of principal
axes of the cube, then $K$ becomes the identity together with the three
$180^{\circ}$ rotations about the principal axes. When we identify $G$
with $S_4$ in the usual way, $K$ becomes matched with the special normal
subgroup of $S_4$ with 4 elements. When we look at the image of $G$ in
$S_X\cong S_3$, we see that a $90^{\circ}$ rotation about a principal
axis give a transposition (of the other two axes), and that all the
three transpositions can be got in this way; so the image of $G$
contains every transposition and must be the whole of $S_X$. What this
means is that $G/K\cong S_X$; or, in terms of $S_4$, $S_4/K\cong S_3$,
where in this formula $K$ means the 4-element normal subgroup of $S_4$.
[As a general rule, whenever you have a normal subgroup you should try
to identify the corresponding quotient group.]
\medskip
{\bf Definition} Let $\action$ be an action of a group $G$ on a set $X$.
For any $x\in X$, the {\bf stabilizer} of $x$ is
\Centerline{$\Stab(x)=\{a:a\in G,\,a\action x=x\}$,}
\noindent and the {\bf orbit} of $x$ is
\Centerline{$\Orb(x)=\{a\action x:a\in G\}$.}
\medskip
{\bf Proposition} Whenever a group $G$ acts on a set $X$, the stabilizer
of any $x\in X$ is a subgroup of $G$.
\medskip
\noindent{\bf proof} $e\action x=x$ so $e\in\Stab(x)$.
If $a$, $b\in\Stab(x)$ then
\Centerline{$(ab)\action x=a\action(b\action x)=a\action x=x$,}
\noindent so $ab\in\Stab(x)$.
If $a\in\Stab(x)$ then
\Centerline{$a^{-1}\action x=a^{-1}\action(a\action x)
=(a^{-1}a)\action x=e\action x=x$,}
\noindent so $a^{-1}\in\Stab(x)$.
\medskip
{\bf Proposition} Whenever a group $G$ acts on a set $X$, the orbits in
$X$ form a partition of $X$.
\medskip
\noindent{\bf proof (a)} For any $x\in X$, $x=e\action x\in\Orb(x)$, so
$x$ belongs to at least one orbit, its own.
\medskip
{\bf (b)} If $x$, $y\in X$ and $\Orb(x)\cap\Orb(y)\ne\emptyset$, then
$\Orb(x)=\Orb(y)$. \Prf\ Take $z\in\Orb(x)\cap\Orb(y)$; then there
are $a$, $b\in G$ such that $z=a\action x=b\action y$. If
$w\in\Orb(x)$, then there is a $c\in G$ such that
\Centerline{$w=c\action x=(ca^{-1}a)\action x
=(ca^{-1})\action(a\action x)=(ca^{-1})\action(b\action y)
=(ca^{-1}b)\action y\in\Orb(y)$.}
\noindent As $w$ is arbitrary, $\Orb(x)\subseteq\Orb(y)$. Similarly,
$\Orb(y)\subseteq\Orb(x)$, and the two orbits are identical.\ \Qed
\medskip
{\bf (c)} So there can be only one orbit containing any given element of
$X$, and the orbits are a partition of $X$.
\medskip
{\bf Theorem} Let $G$ be a finite group acting on a set $X$. Then
\Centerline{$\#(\Stab(x))\cdot\#(\Orb(x))=\#(G)$}
\noindent for every $x\in G$.
\medskip
\noindent{\bf proof} Write $S$ for $\Stab(x)$. Now the point is that,
for $a$, $b\in G$, $a\action x=b\action x$ iff $aS=bS$. \Prf\ If
$a\action x=b\action x$, then
\Centerline{$x=e\action x=(a^{-1}a)\action x
=a^{-1}\action(a\action x)=a^{-1}\action(b\action x)
=(a^{-1}b)\action x$,}
\noindent so $a^{-1}b\in S$ and $b=aa^{-1}b\in aS$ and $bS=aS$. On the
other hand, if $aS=bS$ then $a=ae\in bS$ so there is a $c\in S$ such
that $a=bc$ and
\Centerline{$a\action x=(bc)\action x=b\action(c\action x)=b\action x$.
\Qed}
This means that we have a one-to-one correspondence between members of
$\Orb(x)$ and left cosets of $S$, matching $a\action x$ with $aS$. So
the number of left cosets of $S$ is exactly $\#(\Orb(x))$. But now
Lagrange's theorem tells us that
\Centerline{$\#(G)=\#(S)\cdot(\text{number of left cosets of }S)
=\#(S)\cdot\#(\Orb(x))$,}
\noindent as claimed.
\medskip
{\bf Example} Once again, let $G$ be the rotation group of the cube and
$X$ the set of principal axes. If $x\in X$, then $\Orb(x)=X$, just
because we can move any axis to another by a rotation. So $\Stab(x)$
has $\Bover{24}{8}$ members.
To see what $\Stab(x)$ looks like, consider the plane through the centre
of the cube perpendicular to $x$. This meets the cube in a square $Q$
say. Any rotation of the cube which returns $x$ to its place must also
put $Q$ back where it was, and vice versa. So $\Stab(x)$ corresponds
to the rotations and reflections of $Q$, and is isomorphic to $D_4$.
(We can also identify $\Stab(x)$ in terms of permutations in $S_4$.
$\Stab(x)$ contains the $90^{\circ}$ rotation about $x$, which
corresponds to a
4-cycle in $S_4$. The other members of $\Stab(x)$ are the reflections
of $Q$; two of them are $180^{\circ}$ rotations about the other two
axes, corresponding to double-transpositions in $S_4$; the other two
are $180^{\circ}$ rotations about the axes which are the diagonals of
$Q$, corresponding to transpositions in $S_4$.
So if $H$ is the subgroup of $S_4$ corresponding to
$\Stab(x)\le\Rot(\text{cube})$, $H$ contains all three
double-transpositions and a couple of transpositions. If we label the
diagonals in such a way that $\cycle{1 2}\in H$, then $H$ must contain
\Centerline{$e$, $\cycle{1 2}\cycle{3 4}$, $\cycle{1 3}\cycle{2 4}$,
$\cycle{1 4}\cycle{2 3}$}
\noindent and also their products with $\sigma=\cycle{1 2}$, being
\Centerline{$\cycle{1 2}$, $\cycle{3 4}$, $\rho=\cycle{1 4 2 3}$,
$\cycle{1 3 2 4}$.}
\noindent Observe that (of course) $\rho^4=\sigma^2=e$ and
$\sigma\rho\sigma^{-1}=\cycle{2 4 1 3}=\rho^{-1}$.
\medskip
{\bf The conjugacy action} Recall that any group $G$ acts on itself
through the {\bf conjugacy action} $a\action x=axa^{-1}$. The
stabilizer of $x\in G$ under
this action is the {\bf centralizer subgroup} $C_x=\{a:axa^{-
1}=x\}=\{a:ax=xa\}$
of elements commuting with $x$. The orbit of $x\in G$ under the action
is the
{\bf conjugacy class} $\{axa^{-1}:a\in G\}$ of elements conjugate to $x$
in $G$.
The kernel of the action is the {\bf centre}
\Centerline{$C=\{a:axa^{-1}=x$ for every $x\in G\}
=\{a:ax=xa$ for every $x\in G\}$}
\noindent of $G$, the set of elements commuting with every element of
$G$.
$G$ is abelian iff $C=G$ iff $C_x=G$ for every $x\in G$ iff every
conjugacy class has just one element.
Generally, $C$ consists of those $x$ such that $\{x\}$ is a conjugacy
class;
$G\setminus C$ is the union of the non-singleton conjugacy classes.
\medskip
{\bf Proposition} Let $G$ be a non-abelian group. Then $G/C$ is not
cyclic.
\medskip
\noindent{\bf proof} \Quer\ Suppose, if possible, that
$G/C==\{w^n:n\in\Bbb Z\}$ for some $w\in G/C$. As $G\ne C$, $w$
cannot be the identity of $G/C$. Express $w$ as $bC$ where $b\in G$.
Then $b\notin C$
so there is an $x\in G$ such that $bx\ne xb$.
Consider $v=xC$. We know that $v=w^n$ for some $n\in\Bbb Z$. Now
$w^n=b^nC$, because the map $y\mapsto yC:G\to G/C$ is a homomorphism.
So $xC=b^nC$ and $x\in b^nC$ and $x=b^nc$ for some $c\in C$. Now
$bc=cb$, so
\Centerline{$bx=b(b^nc)=(bb^n)c=b^{n+1}c=(b^nb)c=b^n(bc)=b^n(cb)=(b^nc)b
=xb$,}
\noindent contrary to the choice of $x$.\ \Bang
\medskip
{\bf Proposition} Suppose that $G$ is a finite group of prime power
order, not
$\{e\}$. Then the centre of $G$ is not $\{e\}$.
\medskip
\noindent{\bf proof} Suppose that $\#(G)=p^r$, where $p$ is a prime and
$r\ge 1$. $G/C$ is a union of non-trivial conjugacy classes. Now if
$x\in G\setminus C$, $\#(C_x)\cdot\#($conjugacy class of $x)=\#(G)=p^r$,
so the number of elements of $G$ conjugate to $x$ is a factor of $p^r$;
but it is not
1, because $x\notin C$, so is a multiple of $p$. Since the non-
singleton
conjugacy classes of $G$ form a partition of $G\setminus C$,
$\#(G\setminus C)$ is a multiple of $p$ and $\#(C)=\#(G)-\#(G\setminus
C)$ is a multiple of $p$.
In particular, $C\ne\{e\}$.
\medskip
{\bf Proposition} Suppose that $G$ is a group of order $p^2$, where $p$
is a prime. Then $G$ is abelian.
\medskip
\noindent{\bf proof} Consider the centre $C$ of $G$. Then $\#(C)$ is a
factor
of $p^2$, by Lagrange's theorem, so is 1 or $p$ or $p^2$. By the last
proposition, it cannot be $1$. Also $G/C$ is not cyclic, so
$\#(G/C)\ne p$ and $\#(C)\ne p$. We are left with $\#(C)=p^2$, that
is, $C=G$, and $G$ is abelian.
\medskip
{\bf Dihedral groups} Suppose that $n\ge 3$ and that we take the
standard generators $\rho$, $\sigma$ of the dihedral group $D_n$, so
that $\rho^n=\sigma^2=e$ and $\sigma\rho\sigma^{-1}=\rho^{-1}$; in the
interpretation of $D_n$ as the isometry group of a regular $n$-gon, we
can take $\rho$ to be the anticlockwise rotation through
$(360/n)^{\circ}$ and $\sigma$ to be the reflection about an axis
through the midpoint of the edge joining the vertices $1$ and $n$ and
the centre of the polygon.
In this case, the conjugacy class $E_{\rho}$ of $\rho$ contains (at
least) $\rho$ and $\sigma\rho\sigma^{-1}=\rho^{-1}$, and the centralizer
$C_{\rho}$ of $\rho$ contains (at least) the subgroup $<\rho>$ generated
by $\rho$, just because it is a subgroup containing $\rho$. But as
\Centerline{$\#(C_{\rho})\cdot\#(E_{\rho})=\#(D_n)=2n=2\#(<\rho>)$,}
\noindent there is no room for either $C_{\rho}$ or $E_{\rho}$ to be
larger; so $C_{\rho}=<\rho>$ and $E_{\rho}=\{\rho,\rho^{-1}\}$ exactly.
Similarly, for any $i$ and
$E_{\rho^i}$ includes $\{\rho^i,\rho^{-i}\}$ (because
$\sigma\rho^i\sigma^{-1}=(\sigma\rho\sigma^{-1})^i=\rho^{-i}$); so
$C_{\rho^i}=<\rho>$ and $E_{\rho^i}=\{\rho^i,\rho^{-i}\}$ {\it unless}
$\rho^i=\rho^{-i}$, that is, $\rho^{2i}=e$, that is, $i=n/2$. Of
course this can happen only when $n$ is even. When $n$ is even, then
$\sigma\rho^{n/2}\sigma^{-1}=\rho^{n/2}$, that is,
$\sigma\rho^{n/2}=\rho^{n/2}\sigma^{-1}$, and
$\sigma\in C_{\rho^{n/2}}$. Since $\rho$ certainly belongs to
$C_{\rho^{n/2}}$, $C_{\rho^{n/2}}=D_n$, that is, $\rho^{n/2}$ belongs to
the centre $C$ of $D_n$, and $E_{\rho^{n/2}}=\{\rho^{n/2}\}$.
Geometrically, $\rho^{n/2}$ corresponds to a $180^{\circ}$ rotation,
which is also the map which takes every vertex to its opposite across
the centre of the polygon.
Now consider $C_{\sigma}$. This contains $e$ and $\sigma$. If $n$ is
odd, it does not contain $\rho^i$ for any $i$ such that $0*=\{e,\sigma\}$. In this case, $E_{\sigma}$ must
have $n$ members and must be the whole of
$\{\sigma\rho^i:i\in\Bbb Z\}=D_n\setminus<\rho>$.
If $n$ is even, however,
$C_{\sigma}=\{e,\sigma,\rho^{n/2},\sigma\rho^{n/2}\}$ and $E_{\sigma}$
has $n/2$ members. To see what they are, note that
$\rho\sigma\rho^{-1}=\sigma\rho^{-2}$ belongs to $E_{\sigma}$;
similarly, $\rho^2\sigma\rho^{-2}=\sigma\rho^{-4}\in E_{\sigma}$, and so
on; generally, $\sigma\rho^{-2i}=\sigma\rho^{n-2i}\in E_{\sigma}$ for
every $i\in\Bbb N$. Because $n$ is even, this amounts to saying that
$\sigma\rho^{2i}\in E_{\sigma}$ for every $i<\Bover{n}2$. Since there
are $\Bover{n}2$ such elements, we have found the whole of $E_{\sigma}$.
Geometrically speaking, if $n$ is {\it odd} then every axis of symmetry
of the polygon passes through a vertex and the midpoint of the opposite
side, and all the reflections are conjugate. But if $n$ is {\it even},
then half the axes of symmetry pass through midpoints of opposite sides,
and are conjugate to $\sigma$ as described, and the other half are long
diagonals passing through pairs of opposite vertices, and are conjugate
to each other but not to $\sigma$.
If $n$ is {\it odd}, then the centre $C$ of $D_n$ is $\{e\}$, and
$D_n/C\cong D_n$. If $n$ is {\it even}, then $C=\{e,\rho^{n/2}\}$.
In this case, $\#(D_n/C)=n$. In fact, $D_n/C\cong D_{n/2}$. \Prf\
For $x\in D_n$, write $\bar x$ for its image $xC\in D_n/C$; remember
that $x\mapsto\bar x$ is a homomorphism. So we shall have
\Centerline{$\bar\rho^{n/2}=(\rho^{n/2})^{-}=\bar e$,
\quad$\bar\sigma^2=(\sigma^2)^-=\bar e$,}
\Centerline{$\bar\sigma\bar\rho\bar\sigma^{-1}
=(\sigma\rho\sigma^{-1})^-=(\rho^{-1})^-=\bar\rho^{-1}$.}
\noindent Thus $\bar\rho$, $\bar\sigma$ satisfy the defining relations
for $D_{n/2}$ and $D_n/C\cong D_{n/2}$.
Geometrically, for even $n$, we can think of $D_n$ as acting on the
$\Bover{n}2$ long diagonals of the polygon. The kernel of this action
is $C$ and $D_n/C$ is isomorphic to the image of the action. The image
$\bar\rho$ of $\rho$ acts as an $\Bover{n}2$-cycle while $\bar\sigma$
acts as a reflection.
\medskip
{\bf Automorphism groups} If $G$ is a group, an {\bf automorphism} of
$G$ is an isomorphism from $G$ to itself. I will write $\Aut G$ for
the set of automorphisms of $G$.
\medskip
{\bf Proposition} For any group $G$, $\Aut G$ is a subgroup of the group
$S_G$ of all bijections from $G$ to itself; so $\Aut G$ is a group in
its own right.
\medskip
\noindent{\bf proof} By definition, an isomorphism is a bijection; so
$\Aut G\subseteq S_G$. Writing $\iota$ for the identity of $S_G$,
\Centerline{$\iota(xy)=xy=\iota(x)\iota(y)$}
\noindent for all $x$, $y\in G$, so $\iota:G\to G$ is a homomorphism,
therefore an isomorphism, and belongs to $\Aut G$. If $\phi$,
$\psi\in\Aut G$ then $\phi\circ\psi$ is a homomorphism (because any
composition of homomorphisms is a homomorphism), so (being bijective)
belongs to $\Aut G$. If $\phi\in\Aut G$, $\phi^{-1}:G\to G$ is an
isomorphism (because the inverse of an isomorphism is always an
isomorphism), so belongs to $\Aut G$.
\medskip
{\bf Inner automorphisms} Again, let $G$ be any group. Then the
conjugacy action of $G$ on itself corresponds to a homomorphism from $G$
to $S_G$; write $\hat a\in S_G$ for the bijection corresponding to
$a\in G$, so that $\hat a(x)=axa^{-1}$ for every $x\in G$. Set
$J=\{\hat a:a\in G\}$, the image of the homomorphism, and
\Centerline{$C=\{a:\hat a=\iota\}
=\{a:axa^{-1}=x\Forall x\in G\}=\{a:ax=xa\Forall x\in G\}$,}
\noindent so that $C$ is the kernel of the homomorphism and is the
centre of $G$. By the First Isomorphism Theorem, $G/C\cong J$.
\medskip
{\bf Theorem} In the language here, $J\normalsubgroup\Aut G$.
\medskip
\noindent{\bf proof (a)} If $a\in G$, then
\Centerline{$\hat a(xy)=axya^{-1}=axa^{-1}aya^{-1}=\hat a(x)\hat a(y)$}
\noindent for all $x$, $y\in G$, so that $\hat a:G\to G$ is a
homomorphism. As we already know that it is a bijection,
$\hat a\in\Aut G$. This is true for every $a\in G$, so
$J\subseteq\Aut G$. Since $J$ is a subgroup of $S_G$, it is also a
subgroup of $\Aut G$.
\medskip
{\bf (b)} Now $J\normalsubgroup\Aut G$. \Prf\ Suppose that $\phi\in J$
and $\psi\in\Aut G$. Express $\phi$ as $\hat a$, where $a\in G$, and
set $b=\psi(a)$. Then, for any $x\in X$,
$$\eqalignno{(\psi\phi\psi^{-1})(x)
&=\psi(\phi(\psi^{-1}(x)))\cr
\displaycause{by the definition of multiplication in $S_G$}
&=\psi(a\psi^{-1}(x)a^{-1})\cr
\displaycause{because $\phi=\hat a$}
&=\psi(a)\psi(\psi^{-1}(x))\psi(a^{-1})\cr
\displaycause{because $\psi$ respects multiplication}
&=\psi(a)x\psi(a)^{-1}\cr
\displaycause{because homomorphisms respect inversion}
&=bxb^{-1}
&=\hat b(x).\cr}$$
\noindent As $x$ is arbitrary, $\psi\phi\psi^{-1}=\hat b$ belongs to
$J$; as $\psi$ and $\phi$ are arbitrary, $J\normalsubgroup\Aut G$.
\medskip
{\bf Example: the Klein group $K_4$} Consider the exceptional normal
subgroup $\{e,\cycle{1 2}\cycle{3 4},\cycle{1 3}\cycle{2 4},
\cycle{1 4}\cycle{2 3}\}$ of $A_4$ and $S_4$. This group is abelian,
so its centre $C$ is itself, and $J\cong K_4/C$ has just one element.
If we think of $K_4$ in the abstract, it has elements $e$, $a$, $b$, $c$
with $a^2=b^2=c^2=e$ and $ab=ba=c$, $ac=ca=b$, $bc=cb=a$. This means
that any permutation of $a$, $b$, $c$ corresponds to an automorphism of
$K_4$, and $\Aut K_4\cong S_3\cong D_3$.
\medskip
\noindent{\bf Remark} Note that if $G$ is any group with four elements,
it is isomorphic to either $K_4$ or $\Bbb Z_4$. For if $G$ has an
element $a$ of order 4, then $G=*\cong\Bbb Z_4$. Otherwise,
$G\setminus\{e\}$ must have just 3 elements $a$, $b$ and $c$. Because
the order of any element must divide the order of the group (by
Lagrange's theorem), we must have $a^2=b^2=c^2=e$. Now $ab$ cannot be
equal to $e$ (because $a\ne b$) nor to $a$ (because $b\ne e$) nor to $b$
(because $a\ne e$). So $ab=c$; and the rest of the multiplication
table follows similarly. Thus in this case $G\cong K_4$.
$K_4$ is sometimes called the {\bf Klein group}.
\medskip
{\bf Example: cyclic groups} Suppose that
$G=\{e,a,a^2,\ldots,a^{n-1}\}$ where $n\ge 2$. (Of course $G$ is
isomorphic to $\Bbb Z_n$ but I think it will be less confusing to keep
to multiplicative notation.) For $0\le i1$, then $a^i\in H$
where $i=n/j$, so $\kernel\phi_k\ne\{e\}$. What this means is
that
$$\eqalignno{k\text{ and }n\text{ have no common factor}
&\iff \kernel\phi_k=\{e\}\cr
&\iff \phi_k\text{ is injective}\cr
\displaycause{remember that a homomorphism is injective iff its kernel
is trivial}
&\iff\phi_k\text{ is bijective}\cr
\displaycause{because $G$ is finite, so any function from $G$ to itself
is bijective iff it is injective}
&\iff\phi_k\in\Aut G. \text{ \Qed}\cr}$$
Thus we can identify $\Aut G$ with $\{\phi_k:k\in\Bbb Z_n^*\}$, where
$\Bbb Z_n^*=\{k:0\le k