# Subgroup of $S_7$ generated by two permutations

I'm trying to solve an assignment about subgroups of symmetric groups but realized that I'm a bit rusty.

Let $\pi_1 = (1234567)$ and $\pi_2=(124)(357)$ be elements of $S_7$, $G := \left<\pi_1,\pi_2\right>$ and $H := \left<\pi_1\right>$.

First of all $|G|$ is needed. I remember an easy to calculate by just multiplying the orders of both permutations (in this case $7$ and $3$), thus $|G|=21$ but I do not remember the theorem itself. Otherwise the application of Lagrange would lead to $3 \mid |G|$ and $7 \mid |G|$ and therefore $21 \mid |G|$ as well as $|G| \mid 7!$ but I cannot deduce $|G|$ in the end.

Afterwards all normal subgroups of $G$ and the conjugacy classes of all subgroups of $G$ have to be computed. I know that the conjugacy classes of $S_n$ are always represented by permutations of the same "type" and that normal subgroups are the union of conjugacy classes. Can that be applied here?

In the end $\operatorname{Aut}(H)$ has to be calculated. $H \cong \mathbb{Z}_7$ since it has $7$ elements. Thus $\operatorname{Aut}(H) \cong C_6$.

It turns out that $G\simeq GL_3(\Bbb{F}_2)$. This is a simple group of order $168$, so it has no non-trivial normal subgroups (the proof isn't trivial, but not too taxing - see e.g. Jacobson's Basic Algebra I or Alperin & Bell or any other text on groups at about that level).

The way I figured this out is the following. Let $V=\Bbb{F}_2^3$ be the 3-dimensional vector space over $\Bbb{F}_2$. Let $$A_1=\pmatrix{0&0&1\cr 1&0&1\cr 0&1&0\cr}$$ be the companion matrix of the primitive polynomial $x^3+x+1$. This is of order seven, and we can use $A_1$ to label the non-zero (column) vectors of $V$ as follows. Let $v_1=(100)^t$ and then proceed cyclically: $v_{i+1}=A_1v_i$ where $i+1$ calculated modulo seven, so $$\begin{array}{cc} v_2=A_1v_1&=(010)^t,\\ v_3=A_1v_2&=(001)^t,\\ v_4=A_1v_3&=(110)^t,\\ v_5=A_1v_4&=(011)^t,\\ v_6=A_1v_5&=(111)^t,\\ v_7=A_1v_6&=(101)^t, \end{array}$$ whence $A_1v_7=v_1$. Basically setting it up in such a way that the permutation $\pi_1$ corresponds to multiplication from the left by the matrix $A_1$.

It is easy to check that the linear mapping uniquely determined by $v_1\mapsto v_2$, $v_2\mapsto v_4$, $v_3\mapsto v_5$, i.e. the one corresponding to multiplication from the left by the matrix $$A_2=\pmatrix{0&1&0\cr1&1&1\cr0&0&1\cr}$$ permutes the vectors according to $\pi_2$, in other words $v_1\mapsto v_2\mapsto v_4\mapsto v_1$, $v_3\mapsto v_5\mapsto v_7\mapsto v_3$ and $v_6\mapsto v_6$.

The way a matrix from $GL_3(\Bbb{F}_2)$ permutes the non-zero vectors of $V$ is clearly a homomorphism of groups $\rho:GL_3(\Bbb{F}_2)\to S_7$. We have shown that $\rho(A_1)=\pi_1$ and $\rho(A_2)=\pi_2.$

This implies that $G=\langle\pi_1,\pi_2\rangle\le \operatorname{Im}(\rho)$. Most notably, we can deduce that $|G|\mid |GL_3(\Bbb{F}_2)|=168$.

There are probably many ways of proving that we actually have equality here, i.e. $$G=\operatorname{Im}(\rho).$$ A "simple" way would be to prove that $A_1$ and $A_2$ generate $GL_3(\Bbb{F}_2)$. Instead I will flesh out the line of thinking from my comments, and prove that $|G|\ge168$. The claim follows from that right away. The following calculations do it. The idea is to find enough permutations $\in G$ that fix a given element of $\{1,2,3,4,5,6,7\}$. For some reason I chose to concentrate on finding permutations from the subgroup $K:=Stab_G(7)\le G$.

• $\pi_2$ has $6$ as a fixed point, so $$\alpha:=\pi_1\pi_2\pi_1^{-1}=(146)(235)\in K.$$
• $\sigma:=\pi_1\pi_2\pi_1^{-1}\pi_2^{-1}=(16)(2437)\in G$ has $5$ as a fixed point, so $$\beta=\pi_1^2\sigma\pi_1^{-2}=(13)(2465)\in K.$$
• The elements $\beta^2=(26)(45)$ and $\gamma:=\alpha\beta^2\alpha^{-1}=(13)(26)$ are in $K$. By looking at the action of $\gamma$ and $\beta$ on $\{2,4,6,5\}$ we see that they generate a copy of the dihedral group $D_4$. Therefore $8\mid |K|$.
• Clearly $\operatorname{ord}(\alpha)=3\mid |K|$, so $|K|\ge24$. By the orbit-stabilizer theorem we can conclude that $|G|=7\cdot |K|$, so $|G|\ge 168$.

All of this implies that $|G|=168$ and $G\simeq GL_3(\Bbb{F}_2)$.

• Thanks a lot Jyrki, great explanation to follow through and I'll check the literature you mentioned :) – PeterMcCoy Sep 4 '17 at 18:27
• Glad you liked it @PeterMcCoy. I don't think I would dare use this as an exercise in an early course. Then again, I no longer have the stamina I did as young :-/ – Jyrki Lahtonen Sep 4 '17 at 19:35

I'll address what you have said in order.

$|G|$ is not, in general, given as the product of its generators. If the generators commute with relatively prime orders, then it is the product of the two... but not in general. E.g. the problem of finding two permutations that generate all of $S_n$ in general is not an easy task. E.g. it is part of an unsolved problem listed here: http://mathworld.wolfram.com/UnsolvedProblems.html

If you can write $\pi_1\pi_2 = \pi_2\pi_1^k$ for some $k$, then you can express $G$ in the form $\{\pi_1^a\pi_2^b\}$ which will have order $21$ (This is actually an "if and only if"). It seems that by telling you to list the conjugacy classes and all normal subgroups, you might as well calculate, by systematical multiplication, all the elements of $G$, but knowing that there are $21$ elements or not should be helpful.

A conjugacy class in $S_n$ is just all the permutations of the same "type" because conjugating by a permuation $\sigma$ like $\sigma \pi \sigma^{-1}$ replaces the "numbers" in the permutation $\pi = (a_1 \; a_2 \; \cdots \; a_n)$ with $(\sigma(a_1) \; \sigma(a_2) \; \cdots \; \sigma(a_n))$. However, when asking what the conjugacy classes of $G$ are, you are only asking about conjugating by elements in $G$. So, all the elements of a conjugacy class should be of the same "type", but there will be some restrictions since $G$ is a subset of $S_n$, so a conjugacy class of $G$ should not include any element of $S_n$ that is not in $G$.

What you said about the last group seems correct.

• $(1\,2\,3\,\cdots\,n)$ and $(1\,2)$ generate $S_n$. – Lord Shark the Unknown Aug 27 '17 at 5:53
• Here is an article that talks about some generators of $S_n$: math.uconn.edu/~kconrad/blurbs/grouptheory/genset.pdf In general it is not trivial, though. – user357980 Aug 27 '17 at 5:59
• I guess Lord Shark the Unknown wanted you to rephrase it to read: it is not easy to see whether two given permutations generate all of $S_n$ or not. I may be wrong - I didn't check Keith Conrad's blurb. – Jyrki Lahtonen Aug 27 '17 at 6:35
• @user357980 I am unsure which general problem you are saying is hard. The general problem of deciding the order of the she subgroup of $S_n$ generated by a specified subset is solvable in polynomial time. The more specific problem of deciding whether they generate $S_n$ is even easier in the sense that it can be done by a very fast Monte-Carlo algorithm that decides either that the group is $S_n$ or that it is not $S_n$ with very high probability. – Derek Holt Aug 27 '17 at 10:09
• Also listing the probability that two random permutations generate $S_n$ as an unsolved problem, as on the Wolfram website, seems weird to me, because it is known that the probability of them generating $A_n$ or $S_n$ approaches $1$ as $n \to \infty$, and there are accurate estimates of the rate of convergence. – Derek Holt Aug 27 '17 at 10:12