# 抽象代数代写| 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:

$$f=\left(\begin{array}{ccc} A & B & C \ f(A) & f(B) & f(C) \end{array}\right)$$

We have the following 6 bijections:

\begin{aligned} & \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 \end{array}\right) \end{aligned}

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

$$\mu_{2}^{-1}=\mu_{1}$$

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

$$\mu_{2}^{3}=\mathrm{id}_{X}$$

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:$

\begin{aligned} &\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 \end{aligned}

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)

\begin{tabular}{c||cccccc}
$\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}$
\end{tabular}

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$$
H={[1],[6]}
$$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:$$
H={0}
$$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 .