MHB The subgroup of S_4 <σ,τ> is the whole S_4

[mathmari]

Hey!

I am looking at the following exercise:
$$\sigma=(1 \ \ \ 2 \ \ \ 3), \ \ \ \tau=(1 \ \ \ 4) \ \ \ \in S_4$$
Calculate the following permutations and notice that they are different from each other and also different from $\sigma, \tau, id$. Show that the subgroup of $S_4$ that is generated from $\sigma, \tau $ (that means $<\sigma,\tau>$) is the whole $S_4$.
The permutations are the following:
$$ \ \ \ \ \ \ \ \sigma= \begin{pmatrix}
1 & 2 & 3 & 4 \\
2 & 3 & 1 & 4
\end{pmatrix} , \ \ \ \ \ \ \ \ \ \ \ \ \tau=\begin{pmatrix}
1 & 2 & 3 & 4 \\
4 & 2 & 3 & 1
\end{pmatrix}, \ \ \ \ \ \ \ \ \ \ \ \ \sigma^2=\begin{pmatrix}
1 & 2 & 3 & 4 \\
3 & 1 & 2 & 4
\end{pmatrix}$$
$$\ \ \ \ \ \sigma \tau=\begin{pmatrix}
1 & 2 & 3 & 4 \\
4 & 3 & 1 & 2
\end{pmatrix}, \ \ \ \ \ \ \ \ \ \ \tau \sigma=\begin{pmatrix}
1 & 2 & 3 & 4 \\
2 & 3 & 4 & 1
\end{pmatrix}, \ \ \ \ \ \ \ \ \ \ \sigma^2 \tau= \begin{pmatrix}
1 & 2 & 3 & 4 \\
4 & 1 & 2 & 3
\end{pmatrix}$$
$$\ \ \ \tau \sigma^2=\begin{pmatrix}
1 & 2 & 3 & 4 \\
3 & 4 & 2 & 1
\end{pmatrix}, \ \ \ \ \ \ \ \tau \sigma \tau=\begin{pmatrix}
1 & 2 & 3 & 4 \\
1 & 3 & 4 & 2
\end{pmatrix}, \ \ \ \ \ \ \ (\tau \sigma \tau)^2=\begin{pmatrix}
1 & 2 & 3 & 4 \\
1 & 4 & 2 & 3
\end{pmatrix}$$
$$\tau \sigma \tau \sigma \tau=\begin{pmatrix}
1 & 2 & 3 & 4 \\
2 & 4 & 1 & 3
\end{pmatrix}, \ \ \sigma \tau \sigma^2 \tau=\begin{pmatrix}
1 & 2 & 3 & 4 \\
2 & 4 & 3 & 1
\end{pmatrix}, \ \ \ (\sigma \tau \sigma^2 \tau)^2=\begin{pmatrix}
1 & 2 & 3 & 4 \\
4 & 1 & 3 & 2
\end{pmatrix}$$

How can we show that the subgroup of $S_4$, $<\sigma,\tau>$ is the whole $S_4$?? (Wondering)

We know that $|S_4|=4!=24$
From Lagrange, the order of each subgroup divides the order of the group.
So $|<\sigma,\tau>| \in \{1,2,3,4,6,8,12,24\}$ and we want to show that the order of this subgroup is equal to $24$, don't we?
How can we do that?? (Wondering)

 

[I like Serena]

Hi! (Happy)

There's a couple of ways to do it.

Since you already know that $|\langle \sigma,\tau \rangle|$ is either 12 or 24, finding a 13th permution means that it has to be 24.

Alternatively, you can try and construct a set of permutations that you already know generates $S_4$.
You can use for instance that $S_4=\langle (12), (13), (14) \rangle$.
So if you can find combinations of $\sigma$ and $\tau$ that yield each of these, you're also done. (Thinking)

 

[mathmari]

Since you already know that $|\langle \sigma,\tau \rangle|$ is either 12 or 24, finding a 13th permution means that it has to be 24.

Ahaa.. (Thinking) Is the $13^{th}$ permutation the identity permutation?? (Wondering)

 

[I like Serena]

Ahaa.. (Thinking) Is the $13^{th}$ permutation the identity permutation?? (Wondering)

Yep! Identity is a perfect candidate for the 13th permutation, completing the proof.

It also means there are 11 more permutations that you've missed. (Sweating)

 

[mathmari]

Yep! Identity is a perfect candidate for the 13th permutation, completing the proof.

Great! (Yes)

It also means there are 11 more permutations that you've missed. (Sweating)

How can I find them?? Do I have to find other combinations of $\sigma$ and $\tau$ and check if they are different from the permutations at the post #1??

Or is there an other way to find them?? (Wondering)

 

[I like Serena]

Great! (Yes)
How can I find them?? Do I have to find other combinations of $\sigma$ and $\tau$ and check if they are different from the permutations at the post #1??

Or is there an other way to find them?? (Wondering)

Well, I see that you don't have $\sigma^{-1}\tau\sigma = (34)$ yet... (Thinking)

Basically you want a set of 3 different 2-cycles. From those you can find all permutations that you do not have yet.
In this case I constructed $(34)$ as a so called conjugation (permutation of the form $A^{-1}BA$), meaning I switched the numbers in $(14)$ around to get $(34)$.

Btw, it helps if you use cycle notation to get an overview what you have and what you are missing. (Nerd)

 

[mathmari]

Well, I see that you don't have $\sigma^{-1}\tau\sigma = (34)$ yet... (Thinking)

Basically you want a set of 3 different 2-cycles. From those you can find all permutations that you do not have yet.
In this case I constructed $(34)$ as a so called conjugation (permutation of the form $A^{-1}BA$), meaning I switched the numbers in $(14)$ around to get $(34)$.

Btw, it helps if you use cycle notation to get an overview what you have and what you are missing. (Nerd)

Using cycle notation, the permutations of the post #1 are the following:
$( \ 1 \ \ \ 2 \ \ \ 3 \ )$
$( \ 1 \ \ \ 4 \ ) \ ( \ 2 \ \ \ 3 \ )$
$( \ 1 \ \ \ 3 \ \ \ 2 \ )$
$( \ 1 \ \ \ 4 \ \ \ 2 \ \ \ 3 \ )$
$( \ 1 \ \ \ 2 \ \ \ 3 \ \ \ 4 \ )$
$( \ 1 \ \ \ 4 \ \ \ 3 \ \ \ 2 \ )$
$( \ 1 \ \ \ 3 \ \ \ 4 \ \ \ 2 \ )$
$( \ 2 \ \ \ 3 \ \ \ 4 \ )$
$( \ 2 \ \ \ 4 \ \ \ 3 \ )$
$( \ 1 \ \ \ 2 \ \ \ 4 \ \ \ 3 \ )$
$( \ 1 \ \ \ 2 \ \ \ 4 \ )$
$( \ 1 \ \ \ 4 \ \ \ 2 \ )$

Are they correct?? (Wondering)

Then I have found the following:
$( \ 1 \ \ \ 2 \ )$
$( \ 1 \ \ \ 3 \ )$
$( \ 1 \ \ \ 4 \ )$
$( \ 2 \ \ \ 3 \ )$
$( \ 2 \ \ \ 4 \ )$
$( \ 3 \ \ \ 4 \ )$
$( \ 1 \ \ \ 3 \ \ \ 4 \ )$
$( \ 1 \ \ \ 4 \ \ \ 3 \ )$
$( \ 1 \ \ \ 2 \ ) \ ( \ 3 \ \ \ 4 \ )$
$( \ 1 \ \ \ 3 \ ) \ ( \ 2 \ \ \ 4 \ )$

Which permutation have I missed?? (Worried)

 

[Deveno]

Note that any 4-cycle starts off (1 ...)

and so we have 3 choices for what comes next.

Having chosen the 2nd element in the cycle, we now have 2 left to choose from for our 3rd element, after which we must put the sole remaining element last.

This gives us 6 4-cycles (= 3*2).

You have 2 4-cycles starting off (1 2 ...), and 2 4-cycles starting off (1 4 ...), but only one starting off (1 3 ...), namely:

(1 3 4 2)

so you are missing: (1 3 2 4).

Now here is another way to deduce the order of $\langle \sigma,\tau\rangle$:

Since $\sigma$ is a 3-cycle, $\langle \sigma\rangle$ = 3. Since $\tau$ is a transposition, $\langle \tau\rangle$ = 2.

Thus 6 divides $|\langle \sigma,\tau\rangle|$.

Now $\sigma\tau = (1\ 2\ 3)(1\ 4) = (1\ 4\ 2\ 3)$ so 4 divides $|\langle \sigma,\tau\rangle|$, so its order is at least 12.

Now $\langle \sigma,\tau\rangle$ contains both even (a 3-cycle) and odd (a tranposition) permutations.

If it is of order 12, 6 of these would have to be odd permutations.

But we have: $e,\tau,\sigma\tau,\tau\sigma,\sigma^2\tau,\tau\sigma^2,\sigma\tau\sigma^{-1} \in \langle \sigma,\tau\rangle$ so we conclude that $|\langle \sigma,\tau\rangle| \geq 14$, and divides 24, so must be 24.

A third way:

$\tau = (1\ 4)$
$\sigma\tau\sigma^{-1} = (\sigma(1)\ \sigma(4)) = (2\ 4)$
$\sigma^{-1}\tau\sigma = (\sigma^{-1}(1)\ \sigma^{-1}(4)) = (3\ 4)$
$(\tau\sigma)\tau(\tau\sigma)^{-1} = (\tau\sigma(1)\ \tau\sigma(4)) = (2\ 1) = (1\ 2)$
$(\sigma^{-1}\tau\sigma)\tau(\sigma^{-1}\tau\sigma)^{-1} = (3\ 4)(1\ 4)(3\ 4) = (1\ 3)$

So these 5 transpositions are in $\langle\sigma,\tau\rangle$. It then follows that:

$(2\ 3) = (3\ 4)(2\ 4)(3\ 4) \in \langle\sigma,\tau\rangle$, so $\langle\sigma,\tau\rangle$ contains all 6 transpositions of $S_4$, and since every permutation in $S_4$ can be written as a product of transpositions, $S_4 \subseteq \langle\sigma,\tau\rangle \subseteq S_4$.

 

[I like Serena]

You forgot to mention identity.
Usually denoted as $(1)$. (Nerd)

And then there is another 4-cycle.
There should be 6 of them. (Sweating)