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:grpah1

It’s clear that the dotted lines represent the generator b and the solid lines represents ae 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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s