# 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$.