Skip to content

抽象代数代写| Cayley tables. Subgroups

1. Groups

Last time we have introduced a notion of a group $(G, *) .$ In a certain sense which we make precise later in the course, the following example is an ultimate source of all groups.

2. Example 1

Let $X$ be an arbitrary set. Consider

\mathcal{B}(X, X) \subset \mathcal{F}(X, X)

the set of all bijections from $X$ to itself $X$.

Since the composition of bijections is a bijection, we have a set with a composition law:

(\mathcal{B}(X, X), \circ)

  • This composition law is trivially associative, since the composition of functions is always associative
  • $\mathcal{B}(X, X)$ also admits a neutral element with respect to $\circ$ – the identity $\operatorname{map} \operatorname{id}_{X} \in \mathcal{B}(X, X)$.

Now, the point of considering only bijections among all maps $X \rightarrow X$, is that a bijection $f: X \rightarrow X$ always admits an inverse $f^{-1}: X \rightarrow X$ which makes $(\mathcal{B}(X, X), \circ)$ a group. Some of you might have seen this group under the disguise of permutation group of $X$.

3. Remark 1

The group of bijections is not commutative, unless the set $X$ consists of $\leqslant 2$ elements.

4. Cayley tables

If $G$ is finite set consisting of $|G|$ elements, and we want to specify a composition law on $G$, the most straightforward way is to use a Cayley table. This is a table of size $|G| \times|G|$, with rows and columns labeled by elements of $G$.

To fill out Cayley table, in the cell at the intersection of a row of element $x \in G$ and of a column of element $y \in G$ we record their composition $x * y$.

Given a Cayley table of $(G, *)$ we can read off all the possible compositions of all the pairs of elements of $G .$

Problem $1:$ If $(G, *)$ is a group, then every column (resp. row) of its Cayley table contains every element exactly once.

5. Example 2

Let $X={A, B, C}$ and consider the set of bijections $\mathcal{B}(X, X)$. Any bijection would permute elements $A, B, C .$ To define a bijection we have to specify the image of $A$ ( 3 choices), the image of $B$ (only 2 choice left), and the image of $C$ will be determined uniquely. Therefore we will have exactly $3 \times 2=6$ bijections. If $f:{A, B, C} \rightarrow{A, B, C}$ is a bijection, we will represent it as a $2 \times 3$ matrix:

A & B & C \
f(A) & f(B) & f(C)

We have the following 6 bijections:

& \mathrm{id}{X}=\left(\begin{array}{lll} A & B & C \ A & B & C \end{array}\right) \ \tau{1}:=\left(\begin{array}{lll}
A & B & C \
A & C & B
\end{array}\right) \tau_{2}:=\left(\begin{array}{lll}
A & B & C \
C & B & A
\end{array}\right) \tau_{3}:=\left(\begin{array}{lll}
A & B & C \
B & A & C
\end{array}\right) \
\mu_{1} &:=\left(\begin{array}{lll}
A & B & C \
B & C & A
\end{array}\right) \mu_{2}:=\left(\begin{array}{lll}
A & B & C \
C & A & B

So $G=\mathcal{B}(X, X)$ is

G=\left{\mathrm{id}{X}, \tau{1}, \tau_{2}, \tau_{3}, \mu_{1}, \mu_{2}\right}

To finish description of the group $(G, \circ)$ it remain to construct the (multiplication) Cayley table.

Since each of $\tau_{1}, \tau_{2}, \tau_{3}$ just swaps two elements, we find that $\tau_{i} \circ \tau_{i}=\mathrm{id}_{X} .$

Also, it is easy to see that $\mu_{1}^{2}=\mu_{2}$ and $\mu_{1}^{3}=\mathrm{id}_{X}$. The latter implies that


Therefore $\mu_{2}=\mu_{1}^{-1}$, and since $\left(\mu_{1}^{-1}\right)^{3}=\mathrm{id}_{X}$, we see that


To see that group $(G, \circ)$ is not commutative, we consider

\tau_{1} \circ \tau_{2} \text { and } \tau_{2} \circ \tau_{1}

Let us find out how map $\tau_{1} \circ \tau_{2}: X \rightarrow X$ acts on $A, B, C:$

&\left(\tau_{1} \circ \tau_{2}\right)(A)=\tau_{1}\left(\tau_{2}(A)\right)=\tau_{1}(C)=B \
&\left(\tau_{1} \circ \tau_{2}\right)(B)=\tau_{1}\left(\tau_{2}(B)\right)=\tau_{1}(B)=C \
&\left(\tau_{1} \circ \tau_{2}\right)(C)=\tau_{1}\left(\tau_{2}(C)\right)=\tau_{1}(A)=A

So we see that $\tau_{1} \circ \tau_{2}=\mu_{1}$.

Problem 2: Check hat $\tau_{2} \circ \tau_{1}=\mu_{2}\left(\neq \mu_{1}\right)$. This is a manifestation of the fact that $(G, \circ)$ is not commutative.

So far we have essentially computed the following entries of the Cayley table (see below)

(The first row and column just reflect the fact that $\mathrm{i} d_{X}$ is a neutral element)

$\circ$ & $\mathrm{id}{X}$ & $\tau{1}$ & $\tau_{2}$ & $\tau_{3}$ & $\mu_{1}$ & $\mu_{2}$ \
\hline \hline $\mathrm{id}{X}$ & $\mathrm{id}{X}$ & $\tau_{1}$ & $\tau_{2}$ & $\tau_{3}$ & $\mu_{1}$ & $\mu_{2}$ \
$\tau_{1}$ & $\tau_{1}$ & $\mathrm{id}{X}$ & $\mu{1}$ & & & \
$\tau_{2}$ & $\tau_{2}$ & $\mu_{2}$ & $\mathrm{id}{X}$ & & & \ $\tau{3}$ & $\tau_{3}$ & & & $\mathrm{id}{X}$ & & \ $\mu{1}$ & $\mu_{1}$ & & & & $\mu_{2}$ & $\mathrm{id}{X}$ \ $\mu{2}$ & $\mu_{2}$ & & & & $\mathrm{id}{X}$ & $\mu{1}$

Part of the Cayley table of $\mathcal{B}(X, X), X={A, B, C}$

6. Remark 2

From the known compositions, we can formally find, for example, $\mu_{2} \circ \tau_{1}$ :

\tau_{2} \circ \tau_{1}=\mu_{2} \Rightarrow \tau_{2} \circ \tau_{1} \circ \tau_{1}=\mu_{2} \circ \tau_{1} \Rightarrow \tau_{2}=\mu_{2} \circ \tau_{1}

Problem 3: Fill in the remaining entries of the table. Check that the product of two $\tau$ ‘s is either identity of $\mu$, and the product of a $\tau$ and a $\mu$ is always a $\mu .$

7. Subgroups

Let $(G, )$ be a group. Often we would like to understand $G$ by considering subsets which themselves are groups with respect to $$. To this end we need the following definition.

8. Definition 1: $S$

bset $H \subset G$ is called a subgroup if it satisfies the following properties:

  • $e \in H$
  • if $x, y \in H$, then $x * y \in H$;
  • if $x \in H$, then $x^{-1} \in H$.

9. Clearly $(H, *)$ is itself a group.

Problem 4: Prove that a subset $H \subset G$ satisfying

  • if $x, y \in H$, then $\left(x^{-1}\right) * y \in H$,

is a subgroup.

10. Example 3: Obvious subgroups

Any group $(G, *)$ has two obvious subgroups:

  1. $H={e}$ (trivial subgroup)
  2. $H=G$.

If subgroup $H$ is neither of the above, we will say that $H \subset G$ is a proper subgroup.

11. Example 4

Group $\left(\mathbb{Z}{3},+\right)$ does not have any subgroups besides ${0}$ and $\mathbb{Z}{3}$.

Indeed, we have $\mathbb{Z}{3}={[0],[1],[2]} .$ If $H \in \mathbb{Z}{3}$ is a nontrivial subgroup, then either $[1] \in H$ or $[2] \in H .$ If $[1] \in H$, then by the second property $-[1]=[2] \in H$ and $H=\mathbb{Z}_{3}$.

12. Remark 3

If $H \subset G$ is a subgroup, and $h \in H$ is an element in $H$, then for any integer $m \in H$ we also have $h^{m} \in H .$

13. Example 5

Let $\left(\mathbb{Z}{7}^{\times}, \times\right)$be the set of units (i.e., elements admitting multiplicative inverse) in $\mathbb{Z}{7}$ under multiplication operation. In this group we have a subgroup


Indeed, since $[6] \times[6]=[36]=[1]$, this subset satisfies all the properties of a subgroup.

There is another proper subgroup in $\left(\mathbb{Z}_{7}^{\times}, \times\right):$

K={[1],[2],[4]} .

Problem 5: Prove that subset $K \subset \mathbb{Z}_{7}^{\times}$satisfies all the properties of a subgroup.

14. Example 6

Consider group $(\mathbb{Z},+) .$ Then for any fixed nonzero $m \in \mathbb{Z}$ there is a subgroup of elements divisible by $m$

m \mathbb{Z}:={k \cdot m \mid k \in \mathbb{Z}} \subset \mathbb{Z} .

It turns out that the above example provides an exhaustive list of subgroups of $(\mathbb{Z},+) .$ Specifically, we have the following theorem:

15. Theorem 1

Let $H \subset \mathbb{Z}$ be a subgroup with respect to addition. Then either $H$ is trivial:


or $H$ is of the form

H=m \mathbb{Z}

for some fixed nonzero $m \in \mathbb{Z}$.

Proof. Assume that $H$ is nontrivial. Then we have some nonzero integer $a \in H .$ By subgroup property, we also have $-a \in H$, hence there is at least one positive integer in $H$.

Let $m$ be the smallest positive integer in $H$. We claim that $H=m \mathbb{Z}$.

  1. $m Z \subset H:$ Since $m \in H$, by subgroup properties, we have $-m \in H, 2 m=m+m \in H$, and, more generally, for any $k \in \mathbb{Z}$ we have $k \cdot m \in H .$ This proves $m \mathbb{Z} \subset H .$
  2. $H \subset m \mathbb{Z}$. Let us take any element $a \in H$. We claim that $a$ is divisible by $m$ without remainder. Indeed, let us divide $a$ by $m$ with remainder:

a=m \cdot q+r, \quad r \in{0,1, \ldots, m-1}

Since $a \in H$ and $m \in H$, by subgroup properties we have

a-k \cdot m \in H

for any $k \in \mathbb{Z}$. In particular taking $k=q$ we conclude that

r \in H .

But $m$ is the smallest positive element of $H$, therefore $r$ must be 0 .