Groups and Homomorphisms

One often sees that proving theorems about groups and related structures can involve clever reasoning and ingenuity. I will be collecting, when possible, problems which use such reasoning, because what is more disorienting than not being able to re-use a clever method you discovered a few weeks ago?

Problem 1: Show that $S_n$ has the same number of even permutations as of odd permutations.

Solution: Here $S_n$ denotes the set of permutations of the set $\{1,2,\dots,n\}$.

A permutation is defined as even if it can factorized into an even number of transpositions (an operation involving only the interchange of two elements), and odd otherwise.

Consider the function $f(\alpha) = \tau\alpha$, where $\alpha \in S_n$. Therefore we need to show that this mapping $f : S_n \rightarrow S_n$ maps each even permutation to an unique odd permutation and vice-versa.

Now using the fact that $sgn(\tau\alpha) = -sgn(\alpha)$ ($sgn()$ stands for the signum function), it is clear that an odd permutation is mapped to an even while and an even one to an odd one. It remains to show that it is injective in both directions. Surjection will naturally be taken care of then: for if assume that we have shown that $f$ is injective in both directions, and if the subset of odd permutations is $S_{n,o}$ and of even ones is $S_{n,e}$, then $|S_{n,o}| \leq |S_{n,e}|$ and $|S_{n,e}| \leq |S_{n,o}|$ would follow from the condition of one-to-oneness. This will result in $|S_{n,o} | = |S_{n,e}|$, implying a surjection.

Now to show that $f$ is an injection between the subsets $S_{n,o}$ and $S_{n,e}$, we will establish it in one direction, from odd to even, the reverse being virtually same.

If $\alpha_1, \alpha_2 \in S_{n,o}$ and $f(\alpha_1) = f(\alpha_2)$, then that would mean $\tau \alpha_1 = \tau \alpha_2$, leading to $\alpha_1 = \alpha_2$. This completes the proof.

$\square$

Problem 2: For every $n \geq 3$, there exists a non-abelian  group with $2n$ elements that is generated by two elements of order 2.

The proof makes use of Cayley diagrams or digraphs.  A digraph (short for directed graph) is essentially a graph, in which each vertices represents an element of a group and each directed edge represents a generator of the group. Different colors (or kinds of lines- dotted, solid, etc.) can be used to represent different generators of the group. An edge, denoting a generator $a$, going from the vertex representing $x$ to one representing $y$ means that $y = xa$. An undirected edge is used to represent a generator of order 2. It turns out that every digraph having certain properties (like connectedness) represents a valid group. Furthermore given a certain group, one can construct the digraph representing it.

In light of the above exposition of a Cayley digram, to solve the problem it will suffice to show that a general method to construct a digraph with $2n$ vertices and consisting of only two kinds of edges exists. The digraph for the case $n =3$ looks like this:

It’s clear that the dotted lines represent the generator $b$ and the solid lines represents $a$$e$ is the identity element. This indeed represents the group consisting of $\{e, a, b, ba, ab, bab\}$ with $aba = bab$.

For a general $n$ one could elongate the graph on both sides so that the dotted and solid lines alternate, finally ending with a vertex so that there $2n$ vertices in the graph.

$\square$