Mathematics Prelims

January 24, 2009

Subgroups and Permutations

Filed under: Abstract Algebra,Algebra — cjohnson @ 6:35 pm

Given a group G, a subset H \subseteq G is a called a subgroup if H is itself a group under the same operation as G.  This relationship between H and G is denoted H \leq G, and we write H < G if H is a proper subset of G and we say H is a proper subgroup of G.  Going through the “usual” process of verifying H is a group isn’t necessary to see that a subset H is a subgroup though, as some of these properties will be inherited from G.  For instance, associativity of the group operation doesn’t need to be checked.  If the operation was not associative in H, then there would be elements of G for which the operation wasn’t associative and G wouldn’t be a group.  The only three things we need to check for H to be a subgroup are that it contains the identity (which we’ll just call 1), that it’s closed under the group operation (i.e., \forall x,y \in H : xy \in H) and closed under inverses (\forall x \in H : x^{-1} \in H).

In fact we don’t even have to show all of those properties.  The subgroup criterion (as Dummit & Foote call it), aka the two-step subgroup test (Gallian) says that all we need to do is show that H is non-empty, and for every x, y \in H that xy^{-1} \in H.  Obviously these hold if H \leq G, so we need to show that if these properties hold then H \leq G.  Letting y = x, then we have that xy^{-1} = xx^{-1} = 1 \in H.  Now let x = 1 and we have xy^{-1} = 1 \cdot y^{-1} = y^{-1} \in H.  Finally, since we’ve shown that H is closed under inversion, we have that for x(y^{-1})^{-1} = xy \in H and so H is a subgroup of G.

As an example, let G be \mathbb{R}^2 under vector addition.  We will show that the set of all points lying on the line y = x form a subgroup of G.  Let H = \{ (x, y) \in \mathbb{R}^2 : y = x \}.  This is clearly a non-empty set as (1, 1) \in H.  Now let x,y \in H where x = (x, x) and y = (y, y).  Note the inverse of (y, y) is (-y, -y).  Adding our vectors together we have (x, x) + (-y, -y) = (x-y, x-y) \in H and so H is a subgroup of G.

If A is any set, we denote by S_A the set of all bijective functions (normally just called permutations) of A.  We claim that S_A is a group under function composition.  Note that function composition is associative as for any f, g, h \in S_A and a \in A that {}[(f \circ g) \circ h](a) = [f \circ g](h(a)) = f(g(h(a)) = f([g \circ h](a)) = [f \circ (g \circ h)](a).  There is an identity element given by the map a \mapsto a, and that for any f \in S_A we have an inverse by mapping f(a) back to a: by assumption f is bijective so there are no problems with having multiple things map to f(a) under f, or mapping multiple things to a under f^{-1}.

In the case A = \{1, 2, ..., n\} we generally write S_n in place of S_A.  We also generally write these permutations in cycle notation.  A cycle is a parenthesized list of distinct numbers where the first number maps to the second, the second to the third, the third to the fourth, and so on.  The last number in the list maps back to the first number, hence the name “cycle.”  For example, (1 4 5 3 2) means 1 \mapsto 4, 4 \mapsto 5, 5 \mapsto 3, 3 \mapsto 2 and finally 2 \mapsto 1.  In the cycle decomposition of a function we list all such cycles.  If we see (1 4 5 3 2)(6 7)(8), for instance, we have the cycle previously discussed, but in addition we have 6 \mapsto 7 and 7 \mapsto 6 by the second cycle, and the third cycle tells us 8 \mapsto 8 (elements that map to themselves are called fixed points).  The convention is not to list any fixed points in the cycle decomposition though, with the understanding that any any points not appearing in the decomposition map to themselves, so the above permutation would normally be written (1 4 5 3 2)(6 7).  Of course, this permutation is equivalently given by (7 6)(3 2 1 4 5).  By convention though, we list the cycle containing 1 first, the cycle containing the lowest number not in the first cycle next, and so forth.  In a given cycle we will normally list the least element first.

Now let H be set of all permutations of S_{10} that fix the elements 3 and 7.  We will show that H \leq S_{10}.  Obviously H \neq \emptyset.  Let f, g \in H.  Note that if 3 and 7 are fixed by g, they will be fixed by g^{-1} as well.  Applying f after g^{-1} we still keep 3 and 7 fixed.  This gives us that fg^{-1} \in H.


1 Comment »

  1. […] group, some index set, and suppose for every .  We will show that by applying the subgroup test previously described.  First note that the identity is in since each means the identity is in each .  Now let .  […]

    Pingback by Generators and the Dihedral Groups « Mathematics Prelims — January 26, 2009 @ 10:34 pm | Reply

RSS feed for comments on this post. TrackBack URI

Leave a Reply

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

You are commenting using your 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

Blog at

%d bloggers like this: