Skip to main content

Worksheet 10.1.1 Activity: Cayley Permutations
A4US

We have studied permutation groups, as well as groups that do not appear to be groups of permutations (such as \(\Z_n\text{,}\) \(\Z_n\times \Z_m\text{,}\) groups of functions or matrices, \(D_4\text{,}\) etc.). How distinct are these non-permutation groups from permutation groups?

1.

Write the \(4\times 4\) group tables for \(\Z_4\) and \(U(8)\text{,}\) the group of units of \(\Z_8\) (numbers relatively prime to 8) under multiplication.

Solution.
\begin{equation*} \begin{array}{c|cccc} + & 0 & 1 & 2 & 3 \\ \hline 0 & 0 & 1 & 2 & 3 \\ 1 & 1 & 2 & 3 & 0 \\ 2 & 2 & 3 & 0 & 1 \\ 3 & 3 & 0 & 1 & 2 \end{array} \qquad \end{equation*}
2.

For each element in the groups above, we can see what adding or multiplying it by the other elements does to the other elements. For example, \(5 \in U(8)\) corresponds to this function: \(\lambda_5 = \begin{pmatrix}1 \amp 3 \amp 5 \amp 7\\ 5 \amp 7 \amp 1 \amp 3\end{pmatrix}\text{,}\) since \(5 \cdot 1 = 5 \text{,}\) \(5 \cdot 3 = 7\text{,}\) and so on.

For each element \(g\) in each group above, write down the corresponding function \(\lambda_g\text{.}\)

Solution.

For \(Z_4\) we have

\begin{equation*} \lambda_0 = \begin{pmatrix}0 \amp 1 \amp 2 \amp 3 \\ 0 \amp 1 \amp 2 \amp 3\end{pmatrix} \end{equation*}
\begin{equation*} \lambda_1 = \begin{pmatrix}0 \amp 1 \amp 2 \amp 3 \\ 1 \amp 2 \amp 3 \amp 0\end{pmatrix} \end{equation*}
\begin{equation*} \lambda_2 = \begin{pmatrix}0 \amp 1 \amp 2 \amp 3 \\ 2 \amp 3 \amp 0 \amp 1\end{pmatrix} \end{equation*}
\begin{equation*} \lambda_3 = \begin{pmatrix}0 \amp 1 \amp 2 \amp 3 \\ 3 \amp 0 \amp 1 \amp 2\end{pmatrix} \end{equation*}

For \(U(8)\) we get

\begin{equation*} \lambda_1 = \begin{pmatrix}1 \amp 3 \amp 5 \amp 7\\ 1 \amp 3 \amp 5 \amp 7\end{pmatrix} \end{equation*}
\begin{equation*} \lambda_3 = \begin{pmatrix}1 \amp 3 \amp 5 \amp 7\\ 3 \amp 1 \amp 7 \amp 5\end{pmatrix} \end{equation*}
\begin{equation*} \lambda_5 = \begin{pmatrix}1 \amp 3 \amp 5 \amp 7\\ 5 \amp 7 \amp 1 \amp 3\end{pmatrix} \end{equation*}
\begin{equation*} \lambda_7 = \begin{pmatrix}1 \amp 3 \amp 5 \amp 7\\ 7 \amp 5 \amp 3 \amp 1\end{pmatrix} \end{equation*}

Notice that we are getting the rows in the group table as the outputs of the function. This makes sense, right?

3.

What happens when you compose two functions \(\lambda_g\) and \(\lambda_h\) for \(g\) and \(h\) in a group? Try this with a few examples you have above. What do you notice about the function you get?

Solution.

For example, in the case of \(\Z_4\text{,}\) we have

\begin{equation*} \lambda_2\lambda_1 = \begin{pmatrix}0 \amp 1 \amp 2 \amp 3\\ 2 \amp 3 \amp 0 \amp 1 \end{pmatrix}\begin{pmatrix}0 \amp 1 \amp 2 \amp 3\\ 1 \amp 2 \amp 3 \amp 0 \end{pmatrix} = \begin{pmatrix}0 \amp 1 \amp 2 \amp 3\\ 3 \amp 0 \amp 1 \amp 2 \end{pmatrix} = \lambda_3 \text{.} \end{equation*}

In \(U(8)\text{,}\) we have \(\lambda_3\lambda_7 = \lambda_5\text{.}\) But notice that \(5 = 3 \cdot 7\) in \(U(8)\text{.}\) In other words, the \(\lambda_g\) are acting just like \(g\text{.}\)

4.

Consider the set \(\overline{G} = \{\lambda_g \st g \in G\}\text{.}\) Since each \(\lambda_g\) is a permutation of the elements of \(G\text{,}\) each of these will be a subset of \(S_n\) where \(n = |G|\) (in our case, \(n=4\)). Is \(\overline{G}\) a subgroup of \(S_4\) in both our cases? Will it be a subgroup in general?

Solution.

Instead of using the elements of \(G\) themselves, if we put them in some order (a first one, second one, etc), then we can associate numbers \(1,2,3,\ldots,n\) to the \(n\) elements of \(G\text{.}\) The permutations \(\lambda_g\) are then exactly elements of \(S_n\text{.}\)

What we found in the previous question is that the \(\lambda_g\) act just like the elements \(g\) they come from. In fact, we can prove that \(G \cong \overline{G}\text{:}\) the set of permutations \(\overline{G}\) is a subgroup of \(S_n\text{,}\) in fact, a subgroup isomorphic to \(G\text{.}\)