During the EPIC2 year shutdown of VMware, I spent some time reading the book Algebra. Many trivial matters so the progress is slow. This is the first note on Group. This part is important and I find MIT OCW’s course Modern Algebra uses almost half of the content for group-related topics.

Law of Composition to Group Definition

Group is just a set with special properties. The properties are based on a key concept: a map S \times S \rightarrow S . It is a law of composition: combine two elements in the group and generate a new one using this law.

Then naturally come to the two important concepts of elements in the group:

1. Identity: \forall a \in \mathbf{G}, \mathcal{1} a = a, a\mathcal{1} = a
2. Inverse (need to firstly define Identity ): ab = \mathcal{1} \implies a = b^{-1}, b = a^{-1}

Now we are ready to give the definition of Group: a set G with a law of composition and,

1. contains the identity \mathcal{1}
2. every element has an inverse, and the inverse is also in this Group
3. the law of composition satisfies the associative law: \forall a,b,c \in G, (ab)c = a(bc)

NOTE: we do not mention closure ( \forall a,b \in G, ab \in G ) when defining group because we take it obviously.

The definition reminds me of the class concept in analytic combinatorics: class is just a set, with a size function defined for each element.

Understanding the definition of Group, we define the order of it and leads to finite group and infinite group.

With enough concepts, it is time to go through some important groups:

• \Z^{+} : integer with add as the law of composition, 0 as the identify
• GL_n : general linear group
• S_n : symmetric group
  • an interesting fact: if a group’s order is 2, then there is just one law of composition

Subgroup

Why do we choose GL_n and S_n and emphasize these two Groups? Because many other groups are contained in the two groups as subgroups. This sentence gives an answer and also a question: what is a subgroup?

Given a group G , a subset S of G is a subgroup of G if (of course, S uses the same law of composition as G ):

• Composition closure: \forall a,b \in S, ab \in S
• S contains the identity
• Inverse closure: \forall a \in S, a^{-1} \in S

Typical examples:

1. SL_n (n \times n matrix with determinant equals 1) is subgroup of GL_n
2. The unit circle in the complex plane is a subgroup of \mathbb{C}^{+}

Subgroup of \Z^{+}: number theory in terms of group

\Z a = \{ n \in \Z \mid \exists k \in \Z, n = ka \} is a subgroup of \Z^{+} for a given a . And every subgroup of \Z^{+} has this format: if S is a subgroup of \Z^{+} , then \exists a \in \Z, S = \Z a . (We can prove this by discussing on the least positive element in S ).

Another interest subgroup is S_1 = \{ n \in \Z \mid \exists r, s \in \Z, n = ra + sb \}. Basd on the lemma in the previous paragraph, we can prove this proposition by proving S_1 = S_2 = \Z g, g = gcd(a,b). To prove the equivalence of two sets, we need prove two sub-propositions:

P1: \forall n \in S_1, n \in S_2 .

g=gcd(a,b), n \in S_1   \implies \exists r,s \in \Z, n = ra + sb \\
     \implies n \mod g = (ra \mod g + rb \mod g) \mod g \\
\implies n \mod  g = 0 \implies \exists k\in Z, n = kg  \implies n \in S_2

P2: \forall n \in S_2, n \in S_1 .

g = gcd(a,b), n \in S_2 \implies \exists k \in Z, n = kg

Then let’s try to solve the equation: find r,s \in \Z , so that g = r'a + s'b for given a, b \in \Z. This is easy and can be done by extend Euclid algorithm (please refer to Knuth’s Concrete Mathematics (p103, 2nd edition) [4]. Then we have r = kr', s = ks' satisfies n = kg = ra + sb , so n \in S_1 .

A dual interesting problem is \Z a \cap \Z b = \Z lcm(a, b).

Cyclic Groups

Another important subgroup is: given a specific element in a group G , we can generate a group called a cyclic group H by (law of composition is written as product):

H = \{\dots, x^{-2}, x^{-1}, 1, x, x^2, \dots\}

This is the smallest group that contains the element x and can be written as \langle x \rangle .

H can be infinite or finite. If it is finite, then some different powers of x are the same element. If the power of x represents distinct elements, then it is an infinite group.

An important proposition is: given \langle x \rangle is a subgroup of G , and S = \{k \in Z \mid x^k=1\}, then:

1. S is a subgroup of \Z ^{+}
2. x^r = x^s, r \ge s \iff r-s \in S
3. If S is not trivial subgroup, then given (1), we know S = \Z n for some postitive integer n . We have \langle x \rangle = \{1, x, x^2, x^{n-1}\}.

Final important concept of cyclic group is: a subset U of G is said to generate G if every element of G is a product of elements of U and their inverses.

Klein four group V:

k_1 = \begin{bmatrix}
1 & 0\\
0 & 1
\end{bmatrix}, k_2 = \begin{bmatrix}
1 & 0\\
0 & -1
\end{bmatrix}, k_3= \begin{bmatrix}
-1 & 0\\
a & -1
\end{bmatrix}, k_4 = \begin{bmatrix}
-1 & 0\\
0 & 1
\end{bmatrix}

• Klein four group V is not cyclic group.
• (k_2, k_3) , or (k_2, k_4) , or (k_3, k_4) all generates the Klein four group V.

Comments for later content

Later we will discuss many important concepts that are more abstract. They are key to understanding the relationships among groups.

Homomorphisms （同态）

Homomorphism is a map between two groups with special properties: a homomorphism \varphi : G \mapsto G' such that \forall a\ b \in G, \varphi (ab) = \varphi (a) \varphi (b) . Homomorphism is a map that is compatible with the laws of composition in the two groups and it provides a way to relate different groups.

Let \varphi be a group homomorphism, then:

• a_1\ a_2\ a_3 \dots a_k \in G \implies \varphi (a_1a_2\dots a_k) = \varphi (a_1) \varphi (a_2) \dots \varphi (a_k)
• \varphi maps identity to identity: \varphi (\mathbb{1}_G) = \mathbb{1}_{G'}
• \varphi maps inverses to inverses: \varphi (a^{-1}) = \varphi (a)^{-1}

When reading here, a case comes to my mind: \varphi_A : \R ^{n} \mapsto \R ^{m} , and R^n is the full n-dim vector space, with (0,0,\dots, 0)^T as its identity, and n-dim vector plus as its law of composition. (Similar for R^{m} ). So R^m and R^n are both groups and they are Abelian groups. And the map here is matrix multiplication of some specific matrix : A: \varphi_A (x) = Ax . It is easy to verify that \varphi_A is a homomorphism. And the properties in the above paragraph are also satisfied.

Two important subgroups along with the concept of homomorphism are image and kernel (let \varphi: G \mapsto G' be the homomorphism):

• image: im \varphi = \{x \in G' \mid \exists a \in G, x = \varphi (a) \}
• kernel: ker \varphi = \{a \in G \mid \varphi (a) = \mathbb{1}_{G'}\}, it is a subgroup of G.

The image of \varphi_A is the column space of the matrix A . The kernel of \varphi_A is the null space of the matrix A .

Kernel is more important because it controls the entire homomorphism.

Let \varphi : G \mapsto G' be a homomorphism of groups, and let a and b be elements of G , then the following conditions are equivalent:

1. \varphi (a) = \varphi (b)
2. a^{-1} b \in ker \ \varphi
3. b \in a(ker \ \varphi)
4. a(ker \ \varphi) and b(ker \ \varphi) are the same set.

A homomorphism \varphi : G \mapsto G' is injective if and only if its ker \ \varphi is the trivial subgroup \{\mathbb{1}_G\} . Let’s prove this lemma by proving two sub-lemmas:

(1) Given \varphi : G \mapsto G' is injective, means \forall a\ b \in G, \varphi (a) = \varphi (b) \implies a = b, let’s prove \forall a \in G, \varphi (a) = \mathbb{1}_{G'} \implies a = \mathbb{1}_G .

Given\ \forall a \in G, \varphi (a) = \mathbb{1}_{G'} \implies \varphi (a) \varphi (a) = \varphi (a) = \\ \implies \varphi (aa) = \varphi (a)
\implies aa = a \implies a = \mathbb{1}_G

(2) Given ker\ \varphi only contains identity, means \forall a \in G, \varphi (a) = \mathbb{1}_{G'} \implies a = \mathbb{1}_G , let’s prove \forall a\ b \in G, \varphi (a) = \varphi (b) \implies a = b .

\forall a\ b \in G, \varphi (a) = \varphi (b) \implies \varphi(a) \varphi(b)^{-1} = \mathbb{1}_{G'} \\
\varphi(a) \varphi(b^{-1}) = \mathbb{1}_{G'} \implies \varphi(a b^{-1}) = \mathbb{1}_{G'} \\
\implies ab^{-1} = \mathbb{1}_G \implies a = b

Using the matrix multiplication as an example can make the above abstract lemma a bit concrete: the columns of matrix A are linear independent \iff the null space of matrix A only contains a zero vector.

Now the book introduces the concept of conjugate: Given a group G, a\ g \in G, then gag^{-1} is called the conjugate of a by g. With conjugate, naturally, we define the concept of normal subgroup:

A subgroup N of group G is a normal subgroup if \ \forall a \in N, \forall g \in G, gag^{-1} \in N.

It’s easy to use the definition to verify that the kernel of a homomorphism is a normal subgroup. Let \varphi : G \mapsto G' be a homomorphism, ker\ \varphi is a normal subgroup of G .

Every subgroup of an Abelian Group is a normal subgroup. But subgroups of non-Abelian group can be normal or be non-normal.

Now a new definition comes out suddenly. Z is the center of a group G : Z = \{z \in G \mid \forall x \in G, zx=xz\} .

The book uses an important example to close this small section. A homomorphism between two symmetric groups: \varphi : S_4 \mapsto S_3 . I’d explain this in my own words as below.

S_4 contains 24 bijective maps that permutate 4 indices D = \{1,2,3,4\} . Each permutation bijective map is p_i : D \mapsto D .

Then consider 3 elements (can be taken as partitions of order 2 of D):\ \Pi_1 = \{1,2\} \cap \{3,4\},\ \Pi_2 = \{1,3\} \cap \{2,4\},\ \Pi_3 = \{1,4\} \cap \{2,3\}. According to reference [2], the number of partitions that contain only 2-cylce is: N! [z^N] e^{\frac{z^2}{2}},for this example, N=4 then we have 3 such partitions.

Any element p_i \in S_4, using it, a two-cycle will be mapped to another two-cycle, thus using it we can also map one partition to another: \Pi \mapsto \Pi. For example, the right rotation permutation is p=1\mapsto 2, 2\mapsto 3, 3\mapsto 4, 4\mapsto 1, using it, we can have p(\Pi_1)=\Pi_3, p(\Pi_2) = \Pi_2, p(\Pi_3) = \Pi_1 . This is just a permutation of 3 indices. So we have defined a map from S_4 to S_3 . Can we prove it is a homomorphism and if so try to find its kernel and image?

Isomorphism（同构）

An isomorphism \varphi : G \mapsto G' from a group G to a group G' is a bijective group homomorphism —— a bijective map such that \forall a\ b \in G, \varphi (ab) = \varphi (a) \varphi (b) .

Some examples:

• f(x) = e^x, f: \R^{+} \mapsto \R^{\times}
• Given G is infinite order group, and a\in G, then f(n)=a^n, f: \Z^{+} \mapsto \langle a \rangle
• \mathcal{P} is the n \times n permutation matrices, it is a subgroup of GL_n , then the map S_n \mapsto \mathcal{P}.

Given a homomorphism, we need two steps to check if it is an isomorphism (means to check the map is bijective):

1. test if the map is injective: ker\ \varphi = \{\mathbb{1}_{G}\} ?
2. test if the map is surjective: im\ \varphi = G' ?

Bijective map is invertable, and here is a lemma involving the inverse map: if \varphi: G \mapsto G' is an isomorphism, then the inverse map \varphi^{-1}: G' \mapsto G is an isomorphism. This lemma shows when we have an isomorphism then we do computation in either group and then use the map to send it to the other group.

Concept of isomorphic: G and G' are said to be isomorphic （written as G \approx G'）\iff \exists \varphi: G \mapsto G, \varphi is an isomorphism.

We can define isomorphism class of a given group G as: \{S \mid S \approx G' \} .

When the target group happens to be the same one as the source group, then such kinds of isomorphisms are called automorphism. The most important type of automorphisms is conjugation: given a fixed element of a group G, g \in G, we can define a map \varphi : G \mapsto G, \varphi (x) = gxg^{-1}. We call \varphi: conjugation by g. We can show it is an isomorphism by showing:

1. it is a homomorphism: given a\ b \in G, \varphi (ab) = g(ab)g^{-1} = gag^{-1}gbg^{-1}=\varphi (a) \varphi (b)
2. the map is bijective: \varphi ^{-1}(x) = g^{-1} x g , that is conjugation by g^{-1}.

Equivalence relations and partitions

A partition \Pi of a set S is a subdivision of S into nonoverlapping, nonempty subsets:

S = \cup _{i} \Pi_i, \ \forall i,j: \ \Pi_i \cap \Pi_j = \empty, \Pi_i \ne \empty. 

On relation and equivalence relation we can refer to [3]. Three important properties required by equivalence relation is:

1. transitive: a \sim b, b \sim c \implies a \sim c
2. symmetric: a \sim b \implies b \sim a
3. reflexive: a \sim a

An equivalence relation on a set S determines a partition of S, and conversely.

First, from partition to a equivalence relation: a \sim b \iff a, b \in \Pi_i. The rest is easy to verify.

Second, given an equivalence relation, let’s define a partition: the subset that contains a is C_a = \{b \in S \mid a \sim b\}. We call it the equivalence class of a. With the following lemma, we can finish the proof of the above proposition.

Lemma: Given an equivalence relation on a set S , the subsets of S that are equivalence classes partition S. This lemma is important, we carefully prove it as below:

Before the proof, let’s emphasize the above C_a notation for a subset might not be unique. Several different notations might represent the same subset.

For any given element a \in S, reflexive implies a \in C_a, so that we know C_a is not empty. a can be any element of S, so the union of the equivalence classes is the whole set S. Then the last thing to prove is disjoint (easy to prove, skip it here):

C_a \cap C_b \ne \empty \implies C_a = C_b

We next look at the equivalence relation defined by a map. Any map from sets to sets: f: S \mapsto T gives us an equivalence relation on its domain S.This is defined as f(a) = f(b) \implies a \sim b.

With this, we recall that a group homomorphism is a map, and the equivalence relation defined by \varphi : G \mapsto G' is denoted as \equiv , and is referred to as congruence.

\varphi (a) = \varphi (b) \implies  a \equiv b

Looking back we have already known: a \equiv b \iff b \in a\ (ker\ \varphi ).

Cosets

Left coset defined as:

• Given a group G and its subgroup H, and a \in G,
• then a left coset is: aH = \{ah \mid h \in H\} .

The cosets of H in G are equivalence classes for the congruence relation. \exists h \in H, b = ah \implies a \equiv b :

1. reflexive: a = \mathbb{1}_G a \implies a \equiv a
2. symmetric: b = ah \implies a = bh^{-1} \implies b \equiv a
3. transitive: b=ah_1, c=bh_2 \implies c = a(h_1h_2) \implies a \equiv c

The number of left cosets of a subgroup H is called the index of H in G, denoted by [G:H] .

Lemma: all left cosets aH for a subgroup H of a group G have the same order.

Proof: Compostition by a defines a map, this map is bijective map since its reverse is just composition by a^{-1}. Bijective map does not change the order the group.

Now we know two facts (we can have Counting Formula): |G| = |H| [G:H]

• all cosets have the same order
• they partition the whole group

Then it is easy to understand Lagrange’s Theorem: Let H be a subgroup of a finite group G, then the order of H divides the order of G.

We define the order of an element of a group as: a \in G, |a| = |\langle a \rangle| . Then we know the order of an element of a finite group divides the order of the group.

What’s more: if a group G has a prime order p, and a is an element other than the identity, then G=\langle a \rangle . And we find an isomorphism class: the class of cyclicgroupsof order p.

Given a homomorphism \varphi: G \mapsto G', the kernel ker\ \varphi is a subgroup of G. \forall a \in G, the left coset is a(\ker \ \varphi), and \forall x \in a(ker \ \varphi), \varphi (x) = \varphi (a) . Then we can define an equivalence relation \forall a\ b \in G, \exists c \in G, a \in c (ker\ \varphi) \land b \in c(ker\ \varphi) \implies a \equiv b .We can further prove that there is a bijective map from left costes of ker\ \varphi to im\ \varphi. Thus we have [G:ker\ \varphi] = |im \ \varphi|.

With all the above conclusions, given a homomorphism \varphi : G \mapsto G'of a finite group G, we have:

• |G| = |ker \ \varphi| \cdot |im\ \varphi|
• |ker \ \varphi| divides |G|
• |im \ \varphi| divides both |G| and |G'|

There is a chain rule for the order of subgroups: let G \supset H \supset K be subgroups of a group G, then [G:K] = [G:H][H:K].

For right coset and more propositions: XXX.

Modular Arithmetic

For some interesting discussion please refer to [4].

Two integers a, b are said congruent modulo n, denoted as a \equiv b \pmod n. And it is easy to know a \equiv b \pmod n \iff (b-a) \mod n = 0 . It is an equivalence relation, so for any integer, we can have an equivalence class, here we also call it congruence class. The congruence class given a \in Z under n is \bar{a} = \{\dots, a-n,a,a+n,a+2n\dots\}.

Proposition: there are n congruence classes modulo n , namely \bar{0}, \bar{1}, \bar{2}, \dots, \overline{n-1}. [\Z : \Z n] = n.

Basic number theory conclusion: a' \equiv a \pmod n \land b' \equiv b \pmod n \implies a'+b' \equiv a+b \pmod n \land a'b' \equiv ab \pmod n.

Congruences modulo a prime integer have special properties, we discuss it in next section.

The correspondence theorem

Let \varphi: G \mapsto \mathcal{G} be a group homomorphism, and let H be a subgroup of G. We may restrict \varphi to H, and obtaining a homomorphism \varphi |H : H \mapsto \mathcal{G}. We can know the kernel is also restricted: ker(\varphi | H) = ker (\varphi) \cap H.

Let \varphi : G \mapsto \mathcal{G} be a homomorphism, its kernel is ker\ \varphi, and \mathcal{H} be a subgroup of \mathcal{G}.And the inverse image \varphi ^{-1}(\mathcal{H}) = \{x \in G \mid \varphi (x) \in \mathcal{H}\} is H. (NOTE: \varphi ^{-1} is not a map).Then, we have:

• H is subgroup of G and ker\ \varphi \subset H.
• If \mathcal{H} is normal subgroup of \mathcal{G}, then H is also a normal subgroup of G.
• If \varphi is a surjective and H is also a normal subgroup of G, then \mathcal{H} is normal subgroup of \mathcal{G}.

Then we come to an important theorem: Correspondence Theorem.

Theorem (Correspondence Theorem) Let \varphi : G \mapsto \mathcal{G} be a subjective group homomorphism with kernel K = ker\ \varphi. There is a bijective correspondence between subgroups of \mathcal{G} and subgroups of G that contain K:

\{H \mid H\ is\ a\ subgroup\ of\ G, H\supset K\} \longleftrightarrow \{\mathcal{H} \mid \mathcal{H}\ is\ a\ subgroup\ of\ \mathcal{G}\}.

The correspondence is defined as:

• \text{a subgroup }H \text{ of } G \text{ that contains } K \rightsquigarrow \text{ its image }\varphi (H) \text{ in } \mathcal{G},
• \text{a subgroup }\mathcal{H} \text{ of } \mathcal{G} \rightsquigarrow \text{ its inverse image } \varphi ^{-1}(\mathcal{H}) \text{ in } G.

And we can have the following lemmas:

• H \text{ and } \mathcal{H} \text{ are corresponding subgroups } \implies (H \text{ is normal in } G \iff \mathcal{H} \text{ is normal in } \mathcal{G}).
• H \text{ and } \mathcal{H} \text{ are corresponding subgroups } \implies |H|=|\mathcal{H}| \cdot |ker\ \varphi|.

Product Groups

Let G \text{ and } G' be two groups. Then G \times G' = \{(a,a')\mid a \in G, a' \in G'\}. By proper definition of the law of composition, we can make <meta charset="utf-8">G \times G' a group, and the proper definition of the law of composition is defined as:

(a, a') (b, b') = (aa', bb')

We call such kind of group: product group.

Quotient groups

The law of composition can be defined on the set of cosets of a normal subgroup N of any group G. We call it quotient group.

The set of cosets of a normal subgroup N of a group G is denoted as G / N.

Theorem: Let N be a normal subgroup of a group G, let \overline{G} denote the set of cosets of N in G. There is a composition on \overline{G} that make this set into a group, such that the map \pi : G \mapsto \overline{G} defined by \pi (a) = \overline{a} is surjective homomorphism with N is the kernel.

Theorem (First Isomorphism Theorem) Let \varphi : G \mapsto G' be a surjetive group homomorphism with kernel N. The quotient group \overline{G} = G/N is isomorphic to the image G'. To be precise, let \pi : G \mapsto \overline{G} be the canonical map. Thereis a unique isomorphism \overline{\varphi}: \overline{G} \mapsto G' such that \varphi = \overline{\varphi} \circ \pi.

Next Step

It takes me hard work to understand the chapter of the book and this is only Chapter 2. I search MIT’s course 18.703(Modern Algebra), it seems half of the content is covered by this note. So my next plan is to use MIT’s content and homework to review this note and then try to finish the tour of algebra using MIT’s course.

References

• [1] Algebra 2nd Edition by Michael Artin
• [2] Analysis of Algorithm Slide: Permutation by Robert Sedgewick
• [3] Felleisen, Matthias, and Matthew Flatt. “Programming languages and lambda calculi.”
• [4] Concrete Mathematics by Donald Knuth, Oren Patashnik, and Ronald Graham