Author: Eiko

Tags: Algebra, Group, Ring, Module, Field, Linear Algebra, Symmetry, Group Action, Group Representation, Sylow's Theorem, Commutative Algebra, PID, Number Theory, Vector Space, Jordan Canonical Form, Classification of Linear Endomorphisms, Tensor Product, Dual Space

Time: 2024-12-07 04:00:00 - 2024-12-07 04:00:00 (UTC)

The purpose of this book is to lead readers to understand and comprehend algebraic structures such as groups, rings, and modules. The book aims to explain the principles in a systematic way, so that readers can understand the basic principles and the entire theory, rather than just presenting the information in a straightforward manner. There are many exercises interspersed throughout the book, which can help readers become familiar with the concepts and check their understanding. Difficult problems are marked with a difficulty level symbol \(\bigstar\), with the number of \(\bigstar\) representing their difficulty (ranging from 0 to 5 stars). The 0-star problems are those that can be immediately solved, and readers can easily figure out the answers. When encountering 0-star problems, readers should try to think about the answer immediately, as it can be used to check their understanding of the concepts. If they cannot come up with the answer, they should review the previous content. Some exercises are actually simple but have certain importance or useful conclusions. By thinking about them, readers can have a better understanding and impression of them.

The original version of this book was written by me in Chinese. I used some neovim magic and chatgpt api to translate it into English, so there may be something missing or inaccurate. If you find any errors, please let me know. I hope this book can help you understand algebra happily and easily. Enjoy reading!

Last updated: 2024

Symmetry Phenomena and Groups

Understanding Symmetry

In the vast and boundless universe, there are countless colorful and complex symmetry phenomena. The word "symmetry" is not unfamiliar to us. For example, we often say that a circle is both an axisymmetric figure and a central symmetric figure, and it is also "rotationally" symmetric; (equilateral) triangles are axisymmetric, with three axes of symmetry. Moreover, we feel that a triangle looks the same from three different directions, which seems to be a kind of symmetry... So what is symmetry?

We need to make a high-level summary of the phenomenon of symmetry. It is not difficult to see that we can re-understand the above examples in a unified way: reflecting and rotating a circle about a symmetry axis, or performing a central symmetry transformation, i.e. mapping \((x,y)\mapsto(-x,-y)\), will bring the circle back to its original state. Reflecting an (equilateral) triangle about a symmetry axis, or rotating it by \(120\) degrees, will not change the triangle.

So we can say that the so-called symmetry of an object refers to a transformation (mapping) that keeps the entire object unchanged. However, in general, this transformation is limited, usually only considering selecting some mappings that keep it unchanged from a larger, more normal/natural mapping space. It cannot be a bad mapping, otherwise there will be too many options. For this entire triangle, we only consider the transformation of treating it as an indivisible rigid body. The mappings that would divide the triangle can also be seen as a kind of symmetry according to this definition, but we do not consider them. Under this consideration, the symmetry of an (equilateral) triangle only needs to look at how its three vertices 1,2,3 move. For example, the transformation \((1,2,3)\mapsto(2,3,1)\) is a rotation, while \((1,2,3)\mapsto(1,3,2)\) is an axis symmetry.

Essential Properties of Symmetry

We now use mathematical notation to write our previous discussion. We first have an object \(X\) that may have some symmetry, which is some transformations \(T_1, T_2, \dots\) acting on \(X\) to keep it unchanged, that is, \[T_i(X)=X.\] A natural principle is that every object has a type of symmetry, which is doing nothing. This do-nothing transformation is denoted as \(1\) and is one of the essential properties of symmetry. Since they are transformations (mappings), they can be composed, and the composition operation must satisfy the associative law. We can easily see that the composition of symmetries is also a symmetry. In slightly more abstract language, this naive (another essential property of symmetry) principle is \[T_i\circ T_j(X)=T_i(T_j(X))=T_i(X)=X\] (In the following, we will omit the composition symbol \(\circ\) and write it as \(T_iT_j\) directly.) This simple equation shows how to "create" new symmetries using two symmetries: the composition of them must still be a symmetry of \(X\)! As the simplest example, let’s take a look at the equilateral triangle again. We know that the transformation of rotating 120 degrees can be applied twice, that is, \(\sigma\circ\sigma=\sigma^2\), which is, in fact, a rotation of 240 degrees. Applying it three times is, in fact, doing nothing. Let’s use \(\sigma\) to represent the transformation of rotating (counterclockwise) 120 degrees. We have found that \(\sigma\circ\sigma\circ\sigma=1\), which is the identity mapping, that is, \[\sigma^3=1\] It is worth noting that, just like the composition of mappings does not necessarily commute, there is no reason to believe that the composition of symmetries must commute, that is, \(T_iT_j=T_jT_i\) is not necessarily true. Symmetry also has another essential property. That is, every type of symmetry can be reversed! That is, for any symmetry \(T\), there is a corresponding inverse symmetry, denoted as \(T^{-1}\), called the inverse of \(T\), such that \(T^{-1}\circ T=1\). The inverse is a mutual relationship, you are my inverse, and I am also your inverse, so it must also satisfy \(T\circ T^{-1}=(T^{-1})^{-1}\circ T^{-1}=1\). For example, the reverse operation of \(\sigma\) is rotating 120 degrees clockwise. This is, in fact, the same as \(\sigma^2\), which can be seen by simultaneously composing both sides of the equation \(\sigma^3=1\) with \(\sigma^{-1}\): \[\sigma^{-1}\sigma^3=\sigma^{-1}=\sigma^2.\] If we use \(S(X)\) to represent the set of all symmetry transformations on \(X\), the above discussion can be summarized as follows:

1. \(1\in S(X).\)

2. \(a,b\in S(X)\Rightarrow ab\in S(X).\)

3. \(a(bc)=(ab)c\).

4. \(a\in S(X)\Rightarrow\)there exists an inverse \(b\in S(X)\) for \(a\), such that \(ab=ba=1.\)

In fact, we call such a set \(S(X)\) a group, namely the symmetric group of \(X\).

Symmetric Group of an Equilateral Triangle

The symmetry of an equilateral triangle includes rotation and reflection. In fact, it has three different axes of symmetry, and we can take the reflection transformation with the vertical axis as the axis of symmetry as \(\tau\). There are also two different rotations \(\sigma, \sigma^2 = \sigma^{-1}\) (one rotates 120 degrees counterclockwise, and the other rotates 120 degrees clockwise), and a symmetry \(1\) that does nothing. As before, we use 1, 2, 3 to denote the three vertices of the triangle (we can place the equilateral triangle flat, with the top vertex as 1, the bottom right vertex as 2, and the bottom left vertex as 3). So each symmetry is actually a mapping \(f\) from \(\{1,2,3\}\) to \(\{1,2,3\}\). Don’t forget, as a symmetry, \(f\) needs to have an inverse, so \(f\) must be a bijection. How many such \(f\) are there? We only need to determine the values of \(f(1), f(2), f(3)\). There are 6 possible permutations, so there can be at most 6 symmetries on the triangle! How many does it actually have? Is each of these \(f\) a symmetry of the triangle? Indeed it is! We will use the following notation \[\left( \begin{array}{ccc} 1 & 2 & 3 \\ a & b & c \\ \end{array} \right)\] to represent the mapping that maps 1 to \(a\), 2 to \(b\), and 3 to \(c\). It is easy to see that \[\sigma=\left( \begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2 \\ \end{array} \right) \quad \tau=\left( \begin{array}{ccc} 1 & 2 & 3 \\ 1 & 3 & 2 \\ \end{array} \right)\] Don’t forget what we said, symmetric transformations can be composed. Let’s try to compose \(\sigma\) and \(\tau\) and see what happens. Calculate and give the result as \[\sigma\tau=\left( \begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2 \\ \end{array} \right)\]

\[\left(\begin{array}{ccc} 1 & 2 & 3 \\ 1 & 3 & 2 \\ \end{array}\right) =\left(\begin{array}{ccc} 1 & 2 & 3 \\ 3 & 2 & 1 \\ \end{array}\right)\] Interestingly, this composition did not produce anything new. \(\sigma\tau\) is another type of symmetry, a reflection that keeps vertex 2 fixed. It is worth noting that \(\sigma\tau\not=\tau\sigma\), and readers can verify this. We can verify that the entire symmetry group of the triangle has the following 6 distinct elements: (which happens to form all the surjective maps from {1,2,3} to {1,2,3}.) \[1,\sigma,\sigma^2,\tau,\tau\sigma,\tau\sigma^2\] This group has good operational properties: it has an identity element 1, every element has an inverse, and the composition of any two elements (also known as the product of elements) still belongs to this group, meaning that the multiplication operation is closed. In fact, we generally refer to this group as \(D_3\), called the dihedral group. The term dihedral group actually includes a whole series of groups \(D_n\), where \(D_n\) refers to the group of all symmetries acting on a regular n-gon. (Note: Some books use \(D_{2n}\) to refer to what we call \(D_n\) here, this is just a difference in notation, unfortunately both notations are widely used.)

Another simple but important example of a group: permutation group

We consider the set \(\{1,2,\dots,n\}\) and study its symmetries. What are the transformations acting on it? They are all the surjective maps from it to itself (must be surjective because symmetry transformations require an inverse). We denote this group as \(S_n\), called the n-permutation group. The elements in it are called permutations. \[S_n=\{\text{surjective map }f:\{1,2,\dots,n\}\mapsto\{1,2,\dots,n\}\}.\] It is easy to see that \(|S_n|=n!\). Permutation groups are of fundamental importance, so it is important to introduce simple and convenient notation for them. We still use \[f=\left( \begin{array}{cccc} 1 & 2 & \dots & n \\ f(1) & f(2) & \dots & f(n) \\ \end{array} \right)\] to represent a permutation. In particular, we call a permutation with the following shape a cycle: \[\left( \begin{array}{ccccccc} a_1 & a_2 & \dots & a_n & b_1 & \dots & b_k\\ a_2 & a_3 & \dots & a_1 & b_1 & \dots & b_k\\ \end{array} \right)\] We denote it as \((a_1 a_2 a_3 \dots a_n)\). There can be cycles with length less than n, such as \((12)\) which represents a cycle that maps 1 to 2, 2 to 1, and leaves other elements unchanged.

Cycle Representation of Permutations

An interesting fact is that every permutation can actually be represented as a product (composition) of cycles! To obtain the cycle representation from a permutation, we simply do the following: it may map \(a_1\) to \(a_2\), \(a_2\) to \(a_3\), and so on until it maps some \(a_k\) back to \(a_1\), then we have found a cycle \((a_1a_2\dots a_k)\). Starting from an element not yet included in any cycle, we let \(f\) act on it repeatedly until it cycles, obtaining another cycle \((b_1b_2\dots b_l)\), and so on. Eventually, we exhaust all elements of the permutation and obtain \[f=(a_1a_2\dots a_k)(b_1b_2\dots b_l)\dots\] Moreover, the cycles appearing in the expression have no common elements (hence the order of composition of these cycles does not matter). For example, we can obtain the cycle representation of this permutation: \[\left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \\ \end{array} \right)=(14)(23)=(23)(14)\] Simply by observing that \(1\mapsto4\mapsto1\), \(2\mapsto3\mapsto2\).

Write as a disjoint cycle product.

The Essential Framework of Symmetry: Groups

A group essentially refers to the set of all symmetry transformations acting on some symmetric object \(X\), denoted as \(S(X)\). This set satisfies the following properties:

1. \(1\in S(X)\).

2. \(a,b\in S(X)\Rightarrow ab\in S(X)\).

3. Multiplication is associative, \(a(bc)=(ab)c\).

4. \(a\in S(X)\Rightarrow\) there exists an inverse \(b\in S(X)\) such that \(ab=ba=1\).

In fact, when we abstractly consider a group, we can see that its operation structure has nothing to do with \(X\), and all its operation information is completely contained in the multiplication operation. These conditions are present in all symmetric phenomena. In order to study the essential structure of all symmetric phenomena in the universe, we can simplify and define it as follows:

In this group definition, we did not mention any symmetry transformations. Even if we only look at this definition, it is not clear what this is for¹, and it may be thought of as a set closed under some operation. Indeed, a group can also represent such a set closed under an operation, such as the set of all integers under addition. (In fact, such a set closed under an operation, such as the group of all integers under addition, is also a kind of symmetry transformation: it is all the translation transformations acting on the set of integers.) But please remember the origin of groups, and the most essential property of groups is symmetry. In this way, by studying all groups, we are essentially studying all possible symmetries that can act on any possible object.

We only study finite groups, i.e. groups with a finite number of elements. We call the number of elements in a group its order. In Chapter 2, we will prove that for every finite group, we can construct an object \(X\) such that this group is exactly the symmetry group of that object, i.e. every group is a symmetry group. Therefore, the essence of groups is symmetry: groups are symmetry, and symmetry is groups!

Some Examples of Groups

In addition to the groups \(S_n\) and \(D_n\) that we have already introduced, there are some simple groups. The simplest example of a group is probably \(\mathbb{Z}\), the group formed by all integers under addition. We can think of this group as the group of translations of all integers. It is easy to verify that the set of even integers also forms a group under addition. In fact, any set of multiples of \(n\) forms a group under addition (since it is closed under addition).

If we take all the rotations in \(D_n\), \(\{1,\sigma,\sigma^2,\dots,\sigma^{n-1}\}\), and form a separate group, it is easy to verify that this also forms a group (since the composition of rotations is still a rotation). This type of group is also one of the most basic groups, and we denote it as \(\mathbb{Z}_n\), calling it the \(n\)th cyclic group², which is an Abelian group.

Regarding cyclic groups, there is actually another arithmetic description: all integers are divided into \(n\) different residue classes according to the modulus \(n\), which are divided into \(n\) classes with remainders \(0,1,2,\dots,n-1\). Addition can be performed between residue classes, for example, in modulus \(5\), \(2+4=1\). In this way, these different residue classes form a group under addition, which seems different from the previous \(\mathbb{Z}_n\) because one is a rotation transformation \(\{1,\sigma,\sigma^2,\dots,\sigma^{n-1}\}\) and the other is a residue class \(\{0,1,2,3,\dots,n-1\}\). However, it can be seen that these two groups have no essential difference in structure, that is, if we identify residue class \(k\) with \(\sigma^k\), any group operation on both sides is the same. This means that under a correspondence \(f\) \[\begin{aligned} f: \{0,1,2,3,\dots,n-1\} &\to \{1,\sigma,\sigma^2,\dots,\sigma^{n-1}\}\\ k &\mapsto \sigma^k \end{aligned}\] the operations on the left can correspond to the operations on the corresponding elements on the right. In this case, we say that these two groups are isomorphic. Isomorphic groups have no essential difference and can be considered the same. A specific description of isomorphism will be given in the next chapter.

In this chapter, we will explore the basic structure of groups using a simple approach.³

Structural Information on Elements

Order of Elements

Let \(g\in G\). If there exists a positive integer \(n\) such that \(g^n=1\), then we say that \(g\) is of finite order and we call the smallest such positive integer \(n\) the order of \(g\). Otherwise, we say that \(g\) is of infinite order. For a finite group \(G\), for any element \(g\in G\), we can keep multiplying it to get the sequence \(g,g^2,g^3,\dots\). Since \(G\) is finite, this sequence will eventually repeat. Suppose \(g^k=g^l,k>l\), then we have \(g^{k-l}=1\). This means that every element in a finite group is of finite order.

In an Abelian group, if the orders of \(a\) and \(b\) are known, then the order of \(ab\) is constrained.

It is worth noting that for non-Abelian groups, knowing only the orders of \(a\) and \(b\) does not provide any information about the order of \(ab\). It can be proven that there exist groups where the order of \(ab\) can take on any given positive integer. As an example, in \(S_5\), let \(a=(12)(34), b=(135)\), then \(ab=(14352)\) is of order five.

Subgroups and Quotient Structures

It is not difficult to see that \(D_6\), the symmetry group of a regular hexagon, also contains all the symmetries of an equilateral triangle! For example, the rotation of \(120\) degrees is also a symmetry in the symmetry group of a regular hexagon. The three axes of symmetry of a triangle also form the three axes of symmetry of a regular hexagon, and of course, a regular hexagon has more axes of symmetry (reflection symmetry). In this case, we say that \(D_3\) is a subgroup of \(D_6\)⁴. The history of mathematics tells us that studying the substructures of a structure is important: we make the following definition

We have many examples of subgroups, for example, the additive group of all even numbers \(2\mathbb{Z}\) is a subgroup of \(\mathbb{Z}\). Another example is \(\mathbb{Z}_6=\{1,\sigma,\sigma^2,\sigma^3,\sigma^4,\sigma^5\}\) has subgroups \(\{1,\sigma^2,\sigma^4\}\) and \(\{1,\sigma^3\}\), which are actually \(\mathbb{Z}_3\) and \(\mathbb{Z}_2\).

Cosets and Lagrange’s Theorem

Let \(G\) be a group and let \(H \leq G\) be a subgroup. We can define an equivalence relation on \(G\) as follows: \[a \sim b \Leftrightarrow a^{-1}b \in H.\] It can be easily verified that this indeed defines an equivalence relation⁵, and according to this relation, the group \(G\) is partitioned into disjoint equivalence classes. It can be observed that the set of all elements equivalent to \(b\) is \(bH\), since \(b \sim a \Leftrightarrow b^{-1}a \in H \Leftrightarrow a \in bH\). Thus, all the equivalence classes are of the form \(bH\), and they all have the same size, which is \(|bH| = |H|\). We call such subsets of \(G\) cosets of \(H\), and we refer to them as left cosets⁶. We denote the number of cosets, or the index of the subgroup \(H\), by \([G:H]\). We have \[G = \bigcup_{i=1}^{[G:H]} b_iH\] Since the different cosets are disjoint, we have obtained

By continuously applying the coset decomposition, we can obtain

This theorem also shows that the order of a subgroup must be a factor of \(|G|\). For example, using Lagrange’s theorem, we can see that a group of order \(12\) cannot have a subgroup of order \(5\).

Quotient Groups and Normal Subgroups

Just like how a subspace can be constructed from a vector space, groups also have quotient structures.

Given \(H\le G\), we try to view the set of cosets \(G/H=\{H,b_1H,\dots,b_{k-1}H\}\) as a group, and the desired group operation is defined as: \[\forall a, b\in G\quad (aH)(bH)=(ab)H\] Unfortunately, for some subgroups \(H\), this equation does not hold. In other words, not all subgroups can be used to construct the quotient group \(G/H\). We reason as follows: \((aH)(bH)=(ab)H\Leftrightarrow HbH=bH\Leftrightarrow (b^{-1}Hb)H=H\Leftrightarrow b^{-1}Hb\subset H\), and for all \(b\), \(b^{-1}Hb\subset H\) is equivalent to \(b^{-1}Hb=H\) for all \(b\). Therefore, in order to construct the quotient group \(G/H\), the subgroup \(H\) must satisfy the condition: \(\forall b\in G, b^{-1}Hb=H\), which leads to the following definition:

It is worth noting that normal subgroups do not have transitivity, that is, \(A\triangleleft B\triangleleft C\) does not imply \(A\triangleleft C\). A counterexample will be given in the later study.

Product of Subgroups

Let \(N,H\le G\). We define the set \[NH=\{nh|n\in N,h\in H\}\subset G.\] Under the operation defined on the larger group \(G\), can this set form a group? The answer is not always. However, this is true when at least one of \(N\) or \(H\) is a normal subgroup. Without loss of generality, let \(N\triangleleft G\). We calculate \[n_1h_1n_2h_2=n_1(h_1n_2h_1^{-1})h_1h_2\in NH\] \[(n_1h_1)^{-1}=(h_1^{-1}n_1^{-1}h_1)h_1^{-1}\in NH\] \[1\in NH\] The associativity of the group \(NH\) is inherited from the associativity of the larger group, so in this case, \(NH\) forms a subgroup.

In addition, even if neither \(N\) nor \(H\) is a normal subgroup, we can still calculate the number of elements in the set \(NH\) by using the method of coset decomposition.

Group Homomorphism

The mappings between linear spaces usually only consider linear mappings related to their linear structures. Similarly, the mappings between groups also only consider group mappings related to their group structures. The group mappings we are looking for are group homomorphisms.

It is worth noting that in the equation \(f(ab)=f(a)f(b)\), the multiplication operation used for \(ab\) is from the group \(G\), while the multiplication operation used for \(f(a)f(b)\) is from the group \(H\).

It is worth noting that \(\ker f\) and \({\rm Im}f\) are subgroups of \(G\) and \(H\), respectively, and in fact \(\ker f\triangleleft G\).

Simple, important and typical group homomorphisms

Monomorphism

The simplest group homomorphism should belong to monomorphism. A monomorphism \(f:H\to G\) essentially maps \(H\) to a subgroup \(f(H)\le G\), and \(f(H)\) is isomorphic to \(H\). In other words, a monomorphism is a way to "insert" \(H\) into \(G\) in an isomorphic way.

Projection and Homomorphism Decomposition

Another simple and important mapping is projection. As we have mentioned, for a normal subgroup \(N\) of a group \(G\), we can construct the quotient group \(G/N\). We can consider a natural mapping that maps an element \(g\) in \(G\) to the coset in \(G/N\) that contains \(g\): \[\begin{aligned} p: G &\to G/N\\ g &\mapsto gN \end{aligned}\] This mapping is obviously a homomorphism, since \(p(ab)=abN=aNbN=p(a)p(b)\). It is also a surjective homomorphism. What is its kernel? Recall that the identity element in \(G/N\) is \(N\), which is the coset containing the identity element in \(G\). Therefore, \(p(a)=aN=N \Leftrightarrow a \in N\), and we conclude that \(\ker p = N\).

The importance and fundamentality of homomorphisms lies in considering the kernel \(\ker f\) of any homomorphism \(f: G \to H\). One thing worth noting is that \(a^{-1}b \in \ker f\) is equivalent to saying \(f(a^{-1}b) = 1 \Leftrightarrow f(a) = f(b)\). In other words, if we take the quotient group of \(G\) by \(\ker f\) (also known as the coset decomposition), every element in the coset \(b\ker f\) is mapped to the same element \(f(b)\) by \(f\), and different cosets are mapped to different elements (since if two cosets \(a\ker f\) and \(b\ker f\) are mapped to the same element, then \(f(a^{-1}b) \in \ker f \Leftrightarrow a\ker f = b\ker f\)). Since all elements in \(a\ker f\) are mapped to the same element \(f(a)\) (which seems like a waste), we can define a new mapping that considers \(a\ker f\) as an element in the quotient group \(G/\ker f\) and maps it to \(f(a)\).

In other words, we find that any homomorphism \(f: G \to H\) with kernel \(\ker f\) can be decomposed into the composition of two mappings: This diagram means that we can map \(a\) to \(f(a)\) in two steps: \(a \mapsto a\ker f \mapsto f(a)\). The first step is to map \(a\) to the coset \(a\ker f\) it belongs to (i.e. the natural projection from \(G\) to \(G/\ker f\)), and the second step is to map \(a\ker f\) to \(f(a)\). The only potential issue is whether the second step is a homomorphism. The answer is yes. It is easy to verify this. Any group mapping can be decomposed into the composition of two basic mappings: a projection and an injective homomorphism. By the way, we can add one more step, which is the most trivial one: \(a \mapsto a\ker f \mapsto f(a) \mapsto f(a)\), which first maps \(f(a)\) to the subgroup \({\rm Im}f\) of \(H\), and then maps \({\rm Im}f\) to \(H\) through the trivial injective mapping. Thus, the second step \(G/\ker f \to a\ker f \mapsto f(a)\) is a homomorphism and a bijection, and therefore an isomorphism. From this, we obtain the following important theorem:

Isomorphism Theorem

The Homomorphism Fundamental Theorem, also known as the First Isomorphism Theorem, is easy to derive from the Homomorphism Fundamental Theorem. We can also derive many isomorphism theorems, which are similar to those we learned in linear algebra.

The following corresponding theorem is fundamental, it describes the correspondence between subgroups of \(G/N\) and subgroups of \(G\) that contain \(N\).

Cyclic Groups, Generators and Group Representations

Cyclic groups are the simplest and most basic type of group, but they are still very important. The cyclic group \(\mathbb{Z}_n\) can be described in various ways, such as the rotation transformation group of a regular \(n\)-gon, or the additive group of residue classes modulo \(n\). The essential characteristic of a cyclic group is that it can be generated by a single element. This means that we can find an element \(a\), and by repeatedly taking inverses \(a^{-1}\) and multiplying \(1,a,a^2,a^3,\dots\), we can obtain all elements in the group \(G\). To make this clearer:

According to this definition, in addition to the finite cyclic group \(\mathbb{Z}_n\), there can be infinite cyclic groups, which are essentially \(\mathbb{Z}\).

Therefore, the cyclic group \(\mathbb{Z}_n\) can be imagined as a group generated by the abstract letter \(a\), satisfying the relation \(a^n=1\). This method of describing a group using generators and constraints is called group presentation. In this example, we write it as \[\mathbb{Z}_n=\langle a|a^n=1\rangle.\]

The description in this section is meant to be inspirational and informal. In the future, we will treat this type of group representation more rigorously.

How many generators does an \(n\)-order cyclic group have? The answer to this question is obvious. Let \(a\) be a generator, then \(a^i\) is a generator if and only if \(i\) is coprime to \(n\). In other words, there are a total of \(\varphi(n)\) generators, where \(\varphi(n)\) represents the number of numbers coprime to \(n\) in the range of \(1\) to \(n\), also known as the Euler’s totient function in number theory. There is an interesting identity about this Euler’s function: \[\sum_{d|n}\varphi(d)=n\] where \(d|n\) means \(d\) divides \(n\), and the summation symbol \(\sum_{d|n}\) represents the sum of all positive divisors of \(n\). This identity can be derived from the following observation: for each \(d|n\), there is only one \(d\)-order subgroup in the cyclic group \(\mathbb{Z}_n\), and this subgroup has \(\varphi(d)\) generators. Every element \(g\in\mathbb{Z}_n\) is exactly a generator of some \(\mathbb{Z}_d\).

There is an important proposition that characterizes the properties of cyclic groups:

Permutation Groups and Conjugation

Permutation groups are the most important class of groups in finite groups. It is not an exaggeration to say that they are the most fundamental, because permutation groups actually contain all finite groups, that is, any finite group is a subgroup of a permutation group! (We will give this later)

Structure and Conjugacy of Permutations

The fundamental element of a permutation group is, of course, the permutation itself. For a permutation, its (disjoint) cycle decomposition best reflects its structure. We know that every permutation has a product decomposition of disjoint cycles, and there can be many cycle decompositions. However, in fact, the cycle decomposition of a permutation is unique up to the order of the cycles. This is quite intuitive and can be proven by induction, without much to say.

So each permutation has a unique cycle structure, for example \((123)(45)\) and \((234)(15)\) have the same cycle structure, only the numbers are different. We say their cycle structure is \(2\cdot 3\). Similarly, if the cycle decomposition of \(\alpha\) has \(m_k\) cycles of length \(k\), we say its cycle structure is \(2^{m_2}\cdot 3^{m_3}\dots k^{m_k}\).

Having the same cycle structure is like matrices having exactly the same Jordan blocks, and can be achieved by "change of basis", for example \[(123)(45)=\sigma^{-1}(234)(15)\sigma\] where \(\sigma=(14)\). This phenomenon is called conjugation:

As an example for everyone to see, we prove a useful proposition.

So, since conjugation is an equivalence relation on a group, the elements in the group will naturally be divided into some equivalence classes, which are called conjugacy classes. Generally speaking, the situation of conjugacy classes in a group is quite complex, but it is relatively simple for \(S_n\).

It is easy to see that if a subgroup \(H\) of a group \(G\) is a normal subgroup, then \(H\) is composed of complete conjugacy classes. Conversely, if some conjugacy classes are put together and happen to form a subgroup, then this subgroup is a normal subgroup.

Parity of Permutations

Permutations can be classified as odd or even, denoted by the symbol \({\rm sgn}\sigma\): odd permutations are \(-1\), while even permutations are \(1\). The symbol \({\rm sgn}\sigma\) for permutations is not unfamiliar to us, as we have encountered it in linear algebra. It can be defined as the inverse of the number of inversions, or as the function that satisfies the following equation: \[\prod_{1\le i\le j\le n}(X_{\sigma(j)}-X_{\sigma(i)})={\rm sgn}\sigma\prod_{1\le i\le j\le n}(X_j-X_i).\] Any permutation can be decomposed into a product of transpositions, as any cycle can be decomposed into a product of transpositions, i.e. \((12\dots k)=(1k)(1,k-1)\dots(13)(12)\). We can also define the parity of a permutation as the parity of the number of transpositions it can be decomposed into. It can be proven that the parity of the number of transpositions in a permutation remains unchanged. According to this definition, a transposition \((12)\) is an odd permutation, while transpositions of odd length, such as \((123)\) and \((12345)\), are even permutations.

We will give another definition, and we will explain how this definition is derived. We know that every permutation \(\sigma \in S_n\) has a unique disjoint cycle decomposition. If we consider the fixed element \(c\) as a cycle of length \(1\), denoted as \((c)\), we can use \(t\) to represent the number of cycles in the disjoint cycle decomposition of the permutation, including the cycles of length \(1\). Then we define \[{\rm sgn}\sigma = (-1)^{n-t}.\] Firstly, for the identity permutation, \(t=n\), so \({\rm sgn}1 = 1\). For the cycle \((12\dots k)\), \(t=n-k+1\), so \({\rm sgn}(12\dots k) = (-1)^{k-1}\). And \(n-t\) is actually the sum of the length of each cycle minus \(1\), and its parity will depend on the number of odd permutations in the cycle decomposition. The tricky part is that we need to prove that this is a homomorphism. It is not easy to prove directly, so we take a slightly simpler route: to prove that for any transposition \(\tau\), we have \({\rm sgn}(\tau \sigma) = {\rm sgn}(\tau) {\rm sgn}(\sigma) = -{\rm sgn}(\sigma)\).

Direct Product

We can construct new groups using old groups, and one very simple construction is the direct product. Let \(G_1\) and \(G_2\) be groups, and we want to give the Cartesian product \(G_1\times G_2\) the structure of a group. The simplest way to do this is to define the multiplication as component-wise multiplication, that is, \[(g_1,g_2)(h_1,h_2):=(g_1h_1,g_2h_2).\] This way, the identity element in the group is \((1,1)\), and the inverse of \((g,h)\) is \((g^{-1},h^{-1})\). We will denote this group as \(G_1\times G_2\). If \(G_1\) and \(G_2\) are both abelian groups, this construction is sometimes denoted as the direct sum \(G_1\oplus G_2\), with the group operation denoted by addition.

Group Actions

Basic Terminology

A group is essentially an abstract structure of symmetric groups/transformation groups/action groups. In this chapter, we will study the action of groups, which means implementing the abstract elements of a group as concrete transformations/actions. For example, how does a cyclic group, such as a symmetry structure, act on various objects? We know that it can be implemented as rotations of regular polygons, which can be represented by a group homomorphism: \[\mathbb{Z}_n\to\{\text{rotation group of a regular $n$-gon}\}\] where the generator of \(\mathbb{Z}_n\) is mapped to a unit rotation. This action can also be described as follows: interpreting the rotation of a regular \(n\)-gon as a permutation on the set of vertices \(\{1,2,\dots,n\}\), we get a (mono)morphism: \[\mathbb{Z}_n\to S_n\] where the generator of \(\mathbb{Z}_n\) is mapped to the cycle \((123\dots n)\). To study the most general actions of a group, we consider a homomorphism from the group \(G\) to the largest possible class of transformation groups. The two main classes of transformation groups that are usually considered are permutation groups and matrix groups. The study of homomorphisms to matrix groups is known as group representation theory. When studying the action of a group on a set, we mainly focus on homomorphisms to permutation groups. We denote the set of all permutations on a set \(X\) by \({\rm Sym}(X)\)⁸, which consists of all bijective mappings, and is called the symmetric group of \(X\). Then, we define an action of a group \(G\) on a set \(X\) as a homomorphism (not necessarily injective or surjective): \[\alpha:G\to{\rm Sym}(X).\] This is also known as a permutation representation of the group \(G\), or simply a representation. In other words, \(\alpha(g)\) becomes a transformation (permutation) on the set \(X\), which is bijective, i.e. \(\alpha(g):X\to X\). This transformation can act on an element \(x\in X\) to give \(\alpha(g)(x)\). This notation is more rigorous, but it is too long. After defining the homomorphism \(\alpha\), we can imagine \(G\) as a set of "operators", and simply use \(gx\) to represent \(\alpha(g)(x)\).

Let us first give some basic terminology for group actions. If \(\alpha\) is a monomorphism, then the action is called faithful, meaning that it does not map two different elements in the group to the same transformation. For \(x\in X\), the set \[Gx=\{gx|g\in G\}\] is called the orbit of \(x\). It can be easily shown that if \(a,b\) belong to the same orbit, i.e. there exists \(g\) such that \(a=gb\), then this is an equivalence relation, closely related to the fact that \(G\) is a group. As a result, the elements in \(X\) are partitioned into disjoint classes, i.e. the union of disjoint orbits. If \(X\) has only one orbit, we say that the action is transitive, meaning that any \(x\) can be mapped to any given \(y\) by some element in \(G\).

Orbit Formula

Since \({\rm Stab}(x)\) is a subgroup, we can make a coset decomposition \[G=\bigcup_{i}g_i{\rm Stab}(x)\] where each coset acts on \(x\) in the same way, i.e. \(g_ix\). Moreover, different cosets give different actions on \(x\), otherwise \(ax=bx\iff a^{-1}b\in{\rm Stab}(x)\iff a{\rm Stab}(x)=b{\rm Stab}(x)\). We immediately obtain the following simple but fundamental orbit formula (for calculating the length of an orbit)

Since \(X\) is partitioned into some orbits, we denote each orbit’s representative element as \(x_i\). It is obvious that we must have \[|X|=\sum|\text{orbit}|=\sum_{i}[G:{\rm Stab}(x_i)].\] Do not underestimate this orbit formula, with it, we have a method to calculate the order of some symmetric groups, because \(|G|=|Gx||{\rm Stab}(x)|\).

In addition, we can immediately obtain the following formula for calculating the number of orbits. For any subset \(S\subset G\) of \(G\), we introduce the notation \[X^S=\{\text{elements of $X$ fixed by all elements of $S$}\}.\] Then we have

Kernel of Representation

We will find \(\ker\alpha\), which is generally important, because by the first isomorphism theorem, \(G/\ker\alpha\) is isomorphic to a subgroup of the permutation group \({\rm Sym}(X)\).

What is \(\ker\alpha\)? It is the set of all elements \(g\) that fix every element, so \[\ker\alpha=\bigcap_{x\in X}{\rm Stab}(x).\] If this action is transitive, then \[\ker\alpha=\bigcap_{g\in G}{\rm Stab}(gx).\] There is a natural relationship between \({\rm Stab}(x)\) and \({\rm Stab}(gx)\). The transformations that fix \(x\) can also be used to fix \(gx\) by slightly modifying them. This only requires composing with \(g^{-1}\), applying \({\rm Stab}(x)\), and then composing with \(g\). In other words, we find that \[g{\rm Stab}(x)g^{-1}\subset{\rm Stab}(gx).\] Similarly, we have \[g^{-1}{\rm Stab}(gx)g\subset{\rm Stab}(x).\] Therefore, we find that \[{\rm Stab}(gx)=g{\rm Stab}(x)g^{-1}.\] Thus, when the action is transitive, we have \[\ker\alpha=\bigcap_{g\in G}g{\rm Stab}(x)g^{-1}.\] This is a normal subgroup. This fact also suggests the following trivial proposition: for \(H\le G\), we have \[\bigcap_{g\in G} gHg^{-1}\triangleleft G.\]

Common Actions

Groups can not only act on other objects, but they can also naturally act on certain structures within themselves. In the study of group theory, this is an extremely important, intuitive, and powerful method. We will give a few simple examples.

Conjugation Action

The group \(G\) acts on itself by conjugation, i.e. \[\begin{aligned} \alpha: G &\to {\rm Sym}(G)\\ x &\mapsto (g\mapsto xgx^{-1}) \end{aligned}\]

The orbit of this action is the conjugacy class, it is easy to see that the kernel of the action \(\ker\alpha=Z(G)\). For \(g\in G\), its stabilizer \({\rm Stab}(g)\) is denoted as \(C_G(g)=\{h\in G|gh=hg\}\)¹⁰, which is a subgroup of \(G\). We call the orbit equation in this case \[|G|=\sum_{i}[G:C_G(g_i)]\] the class equation of the group \(G\). It is worth noting that some elements \(g\in G\) may have orbit length of \(1\), which means they are only conjugate to themselves, central elements, \(Z(G)\). If we let \(|G|=p^n\), where \(p\) is a prime number, then we have \[p^n=|Z(G)|+\sum_{i,g_i\not\in Z(G)}[G:C_G(g_i)]\] It is easy to see that \([G:C_G(g_i)]\) must be a multiple of \(p\). Therefore, in this case, \(|Z(G)|\) must be a multiple of \(p\), which means \(|Z(G)|>1\). In other words, we have the following conclusion:

Regular Representation (Action)

The group \(G\) acts (on the left)¹¹ by multiplication on the group \(G\), i.e. \[\begin{aligned} \alpha: G &\to {\rm Sym}(G)\\ g &\mapsto (a\mapsto ga) \end{aligned}\] This naturally views \(g\) as a permutation on \(G\), \(\alpha(g)\). This is a faithful representation.

We immediately obtain Cayley’s theorem: every group is isomorphic to a subgroup of some permutation group. This may seem extremely trivial, but it is precisely this naive observation that allows us to obtain non-trivial conclusions. We give an example.

Induced Representation (Action on Cosets)

Given a subgroup \(H\) of a group \(G\), there is a (left) coset set \(G/H\), and \(G\) can naturally act on \(G/H\). \[\begin{aligned} \alpha: G &\to {\rm Sym}(G/H)\\ g &\mapsto (aH\mapsto gaH) \end{aligned}\] This is called the (left) induced representation¹². It is obviously transitive. Its kernel is \[\ker\alpha=\bigcap_{g\in G}gHg^{-1}\] and note that \(\ker\alpha\triangleleft H\). Using this representation, we can obtain many powerful (actually simple) conclusions.

Here is another typical application:

Before we start looking at the proof, let’s understand the idea. The case of \(p=2\) has already been done as an exercise, do you remember the method? Your method is probably to pair the elements in \(G\), pairing \(g\) with \(g^{-1}\), the second-order elements \(g\) and \(g^{-1}\) are the same, so they cannot be paired. Finally, because the order of the group is a multiple of \(2\), the number of paired elements is also a multiple of \(2\), and we conclude that there are an even number of elements that satisfy \(x^2=1\). Since \(1^2=1\), we know that there must be second-order elements.

However, at first glance, this proof does not seem to be generalizable to the case of \(p>2\). But if you restate the above proof from the perspective of symmetry, you can immediately see how to generalize it. We want to understand the phenomenon mentioned in the proof as a kind of symmetry, so there must be a symmetry transformation. What is the phenomenon we observe? It is the symmetry transformation \((x,y)\mapsto (y,x)\) on the set of all ordered pairs \(X=\{(g,g^{-1})|g\in G\}\). This is the action of the group \(\mathbb{Z}_2\) on this set. So \(X\) can be decomposed into a union of orbits. And the length of the orbit under this action is \(1\) if and only if \(g=g^{-1}\), that is, \(g^2=1\). From the orbit equation \[|X|=|\{(g,g)|g^2=1\}|+\sum|\text{other orbits of length $2$}|\] the orbit formula shows that the length of the orbit can only be \(1\) or \(2\), and we immediately conclude that \(|\{g|g^2=1\}|\) is a multiple of \(2\). Now, I think it is obvious how to generalize this proof.

Conjugation on Subgroups

Let \(A\le G\) be a subgroup. It is easy to see that \(g^{-1}Ag\) is also a subgroup. This is because the mapping \(x\mapsto g^{-1}xg\) is an automorphism, and when restricted to a subgroup, it remains an isomorphism, thus its image must be a group. We say that subgroups \(A\) and \(B\) are conjugate if \(A=g^{-1}Bg\). It is clear that \(G\) can act on some of its subgroups by conjugation. A subgroup can have many conjugate subgroups, and the normal subgroups of \(G\) are those that are invariant under the conjugation action of \(G\), meaning they are only conjugate to themselves. In this case, they form a conjugacy class on their own.

For \(S\subset G\), we use the notation \(N_G(S)\) to denote \(\{g\in G|gS=Sg\}\), which is called the normalizer of \(S\). It is easy to see that the stabilizer of \(A\le G\) is \(N_G(A)\), and thus the size of the conjugacy class is \[[G:N_G(A)].\]

Applications of Groups in Counting Problems

How many ways are there to paint two faces of a cube red? At first glance, it seems like there are \[\binom{6}{2}=\frac{6\times 5}{2}=15\] ways to do so. However, many of these ways are actually the same, differing only by a rotation. In other words, when painting a symmetric object, we only need to consider its symmetry group and let this group act on all possible sets of colors. To determine if two ways of painting are the same, we just need to see if they are in the same orbit. Therefore, to find the number of essentially different ways to paint, we just need to count the number of orbits! Burnside’s theorem provides a method for doing so.

Let’s use a simple example to illustrate this method. Consider the following counting problem: how many different ways are there to color a circular necklace of length \(n\), using \(c\) different colors? Two colorings are considered the same if they are equivalent under rotation and reflection (axis symmetry). We can consider the space of group actions \[X=\{(a_1,a_2,\dots,a_n)|a_i\text{ is one of $c$ colors}\}\] and let \(D_n\) act on this space in the following way:

1. \(\sigma (a_1,a_2,\dots,a_{n-1},a_n) = (a_2,a_3,\dots,a_n,a_1)\)

2. \(\tau (a_1,a_2,\dots, a_{n-1},a_n) = (a_n,a_{n-1},\dots, a_2,a_1)\).

It is easy to see that since all elements in \(D_n\) can be represented in the form of \(\sigma^i\tau^j\), it is only necessary to define the actions of \(\sigma\) and \(\tau\) on \(X\). It can be easily verified that the above definition indeed gives an action of \(D_n\) on \(X\) (it is necessary to verify that the actions of \(\sigma^n=\tau^2=(\sigma\tau)^2=1\) are trivial). Therefore, our problem is now equivalent to calculating the number of orbits in \(X\), denoted by \(N\). By Burnside’s theorem, \[N=\frac{1}{|D_n|}\sum_{g\in D_n} |X^g|.\] Now let’s consider the size of \(X^g\). First, \(D_n\) can be viewed as a subgroup of \(S_n\), and it actually acts on \(X\) in the same way as the permutation with subscripts. Therefore, we can assume that \(g\in D_n\) has a disjoint cycle decomposition in \(S_n\): \[g=c_1c_2\dots c_k=(c_{11} c_{12} \dots c_{1l_1})(c_{21} c_{22} \dots c_{2l_2})\dots\] where \(c_i=(c_{i1} c_{i2} \dots c_{il_i})\) are disjoint cycles with lengths \(l_i\). For example, \(\sigma = (123\dots n)\), \(\tau = (1,n) (2,n-1)\dots\).

If \(g\) fixes an \(x\in X\), i.e. \(gx=x\), we can obtain \[x=(a_1,a_2,\dots,a_n)= (a_{g(1)},a_{g(2)},\dots, a_{g(n)})\] i.e. \(a_i = a_{g(i)}\). From \(gx=x\), it naturally follows that \(g^kx=x\), thus \(a_{c_{11}}=a_{c_{12}}=\dots=a_{c_{1l_1}}\). This means that in all components of the cycle \(c_1\), the corresponding positions must have the same color. Similarly, the same result can be obtained for all cycles, thus \(|X^g|=c^{g\text{number of cycles}}\), note that when considering cycles, the identity cycle \(1\) must be included.

Note that the cycle decomposition shape of elements in the same conjugacy class of \(D_n\) is the same. In general, it is only necessary to find all conjugacy classes of \(D_n\) and calculate their cycle decomposition. In this example, we can consider \[D_n=\{1,\sigma,\sigma^2,\dots,\sigma^{n-1},\tau\sigma,\tau\sigma^2,\dots,\tau\sigma^{n-1}\}\] Note that \(\sigma^{j}(\tau\sigma^{i})\sigma^{-j} =\sigma^j\tau\sigma^{i-j} = \tau \sigma^{i-2j}\), thus when \(n\) is odd, all \(\tau\sigma^i\) are conjugate, and like \(\tau\), they have \(\frac{n-1}{2}+1=\frac{n+1}{2}\) cycles. When \(n\) is even, it may be divided into two conjugacy classes \(\tau\sigma^{2k+1}\) and \(\tau\sigma^{2k}\), which have \(\frac{n}{2}\) and \(\frac{n}{2}+1\) cycles, respectively, just like \(\tau\sigma\) and \(\tau\).

For elements in \(\mathbb{Z}_n\le D_n\), \(\sigma^k\) is a cycle of length \(n\) when \(k\) and \(n\) are coprime. When their greatest common divisor \((k,n)=d\), it is a product of \(d\) cycles of length \(\frac{n}{d}\). Recall that in the section on cyclic groups, we mentioned that for factors of \(n\), the number of generators of the subgroup of order \(\frac{n}{d}\), \(d\mathbb{Z}_n\le \mathbb{Z}_n\), which are elements \(\sigma^k\) satisfying \((k,n)=d\), is equal to the Euler’s totient function \(\varphi\left(\frac{n}{d}\right)\). Therefore, we can now derive the formula for \(N\): \[\begin{aligned} N&=\frac{1}{|D_n|}\sum_{g\in D_n}|X^g|\\ &=\frac{1}{2n}\left(\sum_{k=1}^{n}c^{(k,n)}+1_{2|n}\frac{n}{2}c^{\frac{n}{2}}+1_{2|n}\frac{n}{2}c^{\frac{n}{2}+1}+1_{2|n+1}nc^{\frac{n+1}{2}}\right)\\ &=\frac{1}{2n}\sum_{d|n}\varphi\left(\frac{n}{d}\right)c^{d}+1_{2|n}\frac{c^{\frac{n}{2}}(c+1)}{4}+1_{2|n+1}\frac{c^{\frac{n+1}{2}}}{2}. \end{aligned}\]

Sylow’s Theorem

Sylow’s theorem may be the most important theorem in elementary group theory, it is also a wonderful application of group actions. We will first introduce the theorem, and then give a proof using group actions.

It is worth noting that general \(p\)-subgroups may not be conjugate to each other.

As we have seen, Sylow’s theorem is often used in conjunction with conjugation, because there is a natural relationship between them: Sylow \(p\)-subgroups are conjugate to each other. In addition to the most common numerical applications of Sylow’s theorem, which must be mastered, using it in conjunction with conjugation can often lead to non-trivial conclusions.

Using Sylow’s theorem to find normal subgroups

Finding normal subgroups is important and can often be used to classify the structure of a group or prove that a group is not simple. One common application of Sylow’s theorem is to use it to find normal subgroups. The following are common methods for using Sylow’s theorem to find normal subgroups.

• Take \(|G|=np^r\) where \(p\) and \(n\) are coprime, and calculate the possible number of Sylow \(p\)-subgroups \(N\), which satisfies \[\left\{ \begin{array}{c} N\equiv 1\mod p \\ N\text{ is a factor of }|G| \\ \end{array} \right.\]

• If \(N=1\), then by Sylow’s theorem we know that \(P\triangleleft G\).

• If \(r=1\), consider each prime \(p\) with \(r=1\) and the minimum number of elements that each \(P\) can contribute to \(N(p-1)+1\). This may help to show that there cannot be so many Sylow subgroups.

• If \(r=2\), consider the intersection \(H=P_1\cap P_2\) of two Sylow subgroups. If \(|P|^2 > |G|\), then \(|H|=p\) (since \(|P_1P_2|=|P|^2/|P_1\cap P_2|\)) and \(P_1,P_2\le N_G(H)\), so \(G=N_G(H)\) and \(H\triangleleft N_G(H)=G\).

• Consider the conjugation action of \(G\) on \(X=\{P_1,P_2,\dots,P_N\}\), and its kernel \(\ker\rho\), which may be a non-trivial normal subgroup of \(G\).

Using Sylow’s Theorem and Conjugation

How can we combine Sylow’s Theorem and conjugation? The following lemma describes how conjugation interacts with Sylow subgroups.

Structure of finitely generated abelian groups

We will study the structure of all abelian groups that can be generated by a finite number of elements. Note that not all abelian groups are finitely generated, for example, \(\mathbb{Q}\) cannot be generated by a finite number of elements. The simplest example of a finitely generated abelian group is the so-called \(n\)-element free abelian group \(\mathbb{Z}^n=\mathbb{Z}\times\mathbb{Z}\times\dots\times\mathbb{Z}\), which is generated by \(n\) elements: \(e_1=(1,0,\dots,0), e_2=(0,1\dots,0),\dots,e_n\). It can also be called a free \(\mathbb{Z}\)-module: \(\mathbb{Z}\)-modules and abelian groups are the same concept.

Let \(G\) be an Abelian group that can be generated by a finite number of elements \(g_1,\dots, g_n\in G\). Then we can define a surjective homomorphism as follows: \[\begin{aligned} \varphi: \mathbb{Z}^n &\to G\\ \sum_{i=1}^n a_ie_i &\mapsto \sum_{i=1}^n a_ig_i. \end{aligned}\] According to the fundamental homomorphism theorem, we have \(G\cong \mathbb{Z}^n/\ker\varphi\). Therefore, our goal is to study what kind of subgroups \(\mathbb{Z}^n\) has, which will allow us to determine all possible quotient groups.

Let’s first consider the simple case of \(n=1\). We know that the only subgroups of \(\mathbb{Z}\) are \(0\) and \(n\mathbb{Z}\) for \(n\ge 1\). Therefore, all non-trivial subgroups of \(\mathbb{Z}\) are isomorphic to \(\mathbb{Z}\).

For the case of \(n=2, G=\mathbb{Z}^2\), let \(H\le G\) be a subgroup. Consider \(H_1=H\cap \mathbb{Z}\times 0\cong \mathbb{Z}\) and \(H_2=H\cap 0\times \mathbb{Z}\cong \mathbb{Z}\). We can think of \(H_1\) and \(H_2\) as subgroups of \(\mathbb{Z}\), so they must be \(H_1=a\mathbb{Z}\) and \(H_2=d\mathbb{Z}\). This means we can find two elements \(\alpha_1=(a,b), \alpha_2=(c,d)\) in \(H\) such that the first component of each element is divisible by \(a\) and the second component is divisible by \(d\). So we can write \(\alpha_1=(a,xd), \alpha_2=(ya,d)\). Now, note that \[\alpha_2-y\alpha_1=(0,(1-xy)d)\in H\] and \[\alpha_1-x\alpha_2=(0,(1-yx)a)\in H.\] We will prove the following important result (essentially linear algebra) in Chapter 4:

Semidirect Product

Semidirect product is an important concept commonly used in group theory. If \(N\triangleleft G\), then we can construct the quotient group \(Q=G/N\). One might wonder if \(G\cong N\times Q\) holds? In most cases, this is not true. For example, consider the case of \(G=\mathbb{Z}_4\) and \(N=2\mathbb{Z}_4\), it is obvious that \(\mathbb{Z}_4\not\cong \mathbb{Z}_2\times \mathbb{Z}_2\).

If \(Q\) can be naturally realized as a subgroup of \(G\), i.e. there exists \(Q\le G\) such that the natural projection \(G\to G/N\) is an isomorphism, then we can assert a weaker proposition: \(G\) is the semidirect product of \(N\) and \(Q\), i.e. \(G\cong N\ltimes Q\). Let us explain this, we can reconstruct \(G\) from \(N\) and \(Q\): for each \(g\in G\), there exists an image \(q\) in \(Q\), so \(gq^{-1}\in N\), which means \(g=nq\), and this representation is unique. Since \(N\triangleleft G\), the multiplication operation on \(G=NQ\) can also be recovered from the conjugation action of \(Q\) on \(N\): \[(n_1 q_1) (n_2 q_2) = n_1 q_1 n_2 q_1^{-1} (q_1 q_2).\] This inspires us to define a group structure on the set \(N\times Q\) from \(N\), \(Q\), and the (conjugation action) homomorphism \(\theta:Q\to {\rm Aut}(N)\) as follows: \[(n_1, q_1) (n_2, q_2) = (n_1 \theta_{q_1}(n_2), q_1q_2).\] The identity element in the group is \((1, 1)\), and the inverse element is \((\theta_{q^{-1}}(n^{-1}), n^{-1})\). It can be verified that this definition satisfies the associative law, so \(N\times Q\) forms a group under the above multiplication, which we denote as \(N\rtimes_\theta Q\), called the semidirect product of \(N\) and \(Q\).

Verify that \(D_n\cong \mathbb{Z}_n\rtimes_\theta \mathbb{Z}_2\), what is the homomorphism \(\theta\)? We give the following simple criterion:

It is worth noting that although there are many possible choices for \(\theta\) in the semi-direct product \(N\rtimes_\theta Q\), different choices may result in isomorphic groups. (In fact, the same group may have different semi-direct product representations.) In order to easily identify these isomorphic groups in applications, we provide the following two criteria to determine when \(N\rtimes_\theta Q\cong N\rtimes_{\theta'} Q\).

Similarly, we have the following proposition:

All Groups with \(|G|\le 15\)

This section will contain quite a few examples: we will classify all groups with order not exceeding \(15\), that is, we will find all non-isomorphic groups in this range. First, it should be noted that when \(p\) is a prime, the only \(p\)-order group is the cyclic group \(\mathbb{Z}_p\). Therefore, we are left with orders \(n=4,6,8,9,10,12,14,15\). We have already proven that there are only two groups of order \(p^2\), \(\mathbb{Z}_{p^2}\) and \(\mathbb{Z}_p^2\). Now consider the following proposition:

So the main difficulty to be discussed is concentrated on the orders \(n=8,12\).

Classification of \(8\)-order groups

The commutative \(8\)-order groups are only \(\mathbb{Z}_8\), \(\mathbb{Z}_4\times \mathbb{Z}_2\), and \(\mathbb{Z}_2^3\). Now we will study the non-commutative \(8\)-order groups. By Sylow’s theorem, we know that \(G\) has \(2k+1\) subgroups of order \(4\). It is impossible to have \(5\) subgroups, otherwise it will occupy at least \(5\times(4-2)+2=12\) elements. Therefore, there can only be \(1\) or \(3\) subgroups.

If there is only one subgroup of order \(4\), \(H\triangleleft G\), then \(H\cong \mathbb{Z}_4\) must hold, otherwise if \(H\cong \mathbb{Z}_2^2\), there will be no elements of order \(4\) in \(G\), which leads to all elements of \(G\) being of order \(1\) or \(2\), making \(G\) abelian, which is not relevant to our discussion. So now we have \(H=\mathbb{Z}_4\). Let \(a\in G-H\), then we must have \(G=\langle a\rangle H\cong \mathbb{Z}_4\rtimes \mathbb{Z}_2\cong D_4\), and there is only one non-trivial choice for the conjugate action. However, in reality, \(D_4\) has \(3\) subgroups of order \(4\): \(\langle \sigma\rangle, \langle \sigma^2, \tau\rangle, \langle \tau\sigma, \sigma^2\rangle.\)

If there are \(3\) \(4\)th-order subgroups, note that all subgroups with an index of \(2\) are normal. By Cauchy’s theorem, we can choose an element \(b\) of order \(2\). If it does not belong to any of the \(4\)th-order subgroups, then \(G\) must be a semidirect product, which could be \(\mathbb{Z}_4\rtimes \mathbb{Z}_2\), which is the same as \(D_4\) mentioned above. If it is the case of \(\mathbb{Z}_2^2\rtimes \mathbb{Z}_2=\langle a,b,c|a^2=b^2=(ab)^2=c^2=1, cac^{-1}=b\rangle\), then choosing \(a=\tau\sigma,b=\tau\sigma^3,c=\tau\) shows that this is also \(D_4\).

Now, let’s assume that all elements of order \(2\) belong to all \(4\)th-order subgroups. Since at least one of these subgroups must be \(\mathbb{Z}_4\) (otherwise, \(G\) would be abelian with only elements of order \(2\)), we can conclude that there is only one element of order \(2\) in \(G\). This means that all \(4\)th-order subgroups are isomorphic to \(\mathbb{Z}_4\). Let \(i,j,k\) be the generators of these subgroups, then we have \(i^2=j^2=k^2=b\). Now, consider the element \(ij\), it cannot belong to \(\langle i\rangle\) or \(\langle j\rangle\), otherwise if \(ij = i^k\), we would have \(j\in \langle i\rangle\), which is impossible. Therefore, we must have \(ij\in \langle k\rangle -\{b\}\). If \(ij=k\), then \(ijk=b\). If \(ij=k^{-1}=kb\), we can choose \(k\) to be \(k^{-1}\) and reduce it to the previous case. These relations determine the group \(G\), which we will denote as \(Q_8\), known as the quaternion group. In fact, this group is generated by \(\{i,j,k\}\) in the quaternion field: \[Q_8=\{1,-1,i,-i,j,-j,k,-k\}.\] Now, we will show that \(Q_8\) is not isomorphic to \(D_4\), as \(Q_8\) has \(1\) element of order \(2\) while \(D_4\) has \(5\).

Classification of Groups of Order \(12\)

For groups of order \(12\), it is easy to see that the only Abelian groups are \(\mathbb{Z}_{12}\) and \(\mathbb{Z}_2\times \mathbb{Z}_6\). Now we only need to consider the case of non-Abelian groups. By the Sylow theorem, we know that \(G\) has either \(1\) or \(3\) normal subgroups of order \(4\), and either \(1\) or \(4\) subgroups of order \(3\). We can see that \(G=H\rtimes K\cong H\rtimes_\theta \mathbb{Z}_3\), where \(H\cong \mathbb{Z}_4\) or \(\mathbb{Z}_2^2\) and \(\theta:\mathbb{Z}_3\to {\rm Aut}(H)\) is a non-trivial homomorphism (if it is trivial, we get a direct product, which is one of the Abelian groups mentioned before).

First, let us assume that \(G\) has a normal subgroup \(H\) of order \(4\). If \(H=\mathbb{Z}_4\), then considering \(\theta:\mathbb{Z}_3\to {\rm Aut}(\mathbb{Z}_4)\cong \mathbb{Z}_2\), we can see that \(\theta\) must be trivial.

If \(H=\mathbb{Z}_2\times \mathbb{Z}_2\), we know that \({\rm Aut}(H)\cong S_3\) is the permutation group of the three \(2\)-order elements in \(H\). Consider the map \(\theta:\mathbb{Z}_3\to {\rm Aut}(H)=S_3\) that maps to the unique subgroup \(A_3\cong \mathbb{Z}_3\) in \(S_3\). Thus, \(\theta\) can be seen as an isomorphism from \(\mathbb{Z}_3\) to \(A_3\cong\mathbb{Z}_3\), and different choices of \(\theta\) differ only by an element in \({\rm Aut}(\mathbb{Z}_3)\). By the symmetric lemma of \(Q\), we know that the groups \(G=\mathbb{Z}_2^2\rtimes \mathbb{Z}_3\) induced by them are isomorphic. In fact, this group is not a new and unfamiliar group.

Now let’s consider the case where it has \(3\) subgroups of order \(4\). Since these \(3\) subgroups must occupy \((4-2)\times 3+1=7\) elements, it is impossible to have \(4\) subgroups of order \(3\), because \(4\) subgroups of order \(3\) would occupy at least \((3-1)\times 4 + 1 = 9\) elements. We conclude that there can only be one subgroup of order \(3\), which makes it normal. If \(H=\mathbb{Z}_4\), there is only one non-trivial semidirect product \(\mathbb{Z}_3\rtimes \mathbb{Z}_4\).

If \(H=\mathbb{Z}_2^2\), then \(\theta:\mathbb{Z}_2^2\to {\rm Aut}(Z_3)\cong \mathbb{Z}_2\). It is easy to see that there are only three non-trivial mappings \(\theta\) that can be chosen. But these three choices only differ by an automorphism of \(\mathbb{Z}_2^2\), which determines the same group \(\mathbb{Z}_3\rtimes \mathbb{Z}_2^2\). In fact, it is \(D_6\).

Now we will prove that \(\mathbb{Z}_3\rtimes \mathbb{Z}_4\) is neither \(D_6\) nor \(A_4\). Since \(A_4\) does not have any normal subgroup of order \(3\), \(\mathbb{Z}_3\rtimes \mathbb{Z}_4\) cannot be isomorphic to \(A_4\). Also, \(D_6\) does not have any element of order \(4\), so it cannot be isomorphic to it.

Table of Small Order Groups

To summarize our discussion in a table, we have the following tables of all groups of order not exceeding \(15\):

Ring and Field

Definition and Examples

From an operational perspective, a group is a set with a "multiplication operation". When this group is an abelian group, the operation is usually written as addition. What if we consider both addition and multiplication operations on a set? For example, \(\mathbb{Z}\) is an abelian group under addition, but it also has a multiplication structure. This is a new algebraic structure called a ring. Of course, the addition and multiplication on a ring cannot be arbitrarily defined, they need to be compatible with each other and satisfy some reasonable properties. The complete definition is as follows:

It is worth noting that in the definition of a ring, we do not require the multiplication to be commutative, we only require the addition to be commutative. If the multiplication is also commutative, we call \(R\) a commutative ring.

In a ring, non-zero elements may not have a multiplicative inverse. If a non-zero element \(r\in R\) has a multiplicative inverse, we call it a unit.

The concepts of rings and fields have many examples in algebra, here are a few common ones.

Similarly, we also need to study the relationship between rings, just like group homomorphisms. We can define ring homomorphisms and field homomorphisms, which need to preserve the operation structure and identity element.

Ideal

The concept of ideal was first introduced by Kummer. This concept was proposed to save the lack of a beautiful unique factorization law in rings considered in many number theories, unlike integers which can be uniquely factored into a product of primes. In general rings, prime factorization may not be unique. Kummer discovered that if the concept of "ideal numbers" is introduced, the product of ideals can still satisfy the unique factorization law.

Simply put, an ideal is a set of multiples. For example, for a prime number \(p\in\mathbb{Z}\), we can consider the set of all multiples of \(p\), denoted as \((p):=\{kp|k\in\mathbb{Z}\}\), which is called the ideal generated by \(p\). The essential characteristic of this set of multiples is its "absorption" property, which means that for any \(r\in\mathbb{Z}, i\in(p)\), we have \(ri\in(p)\). This leads to the concept of an ideal as follows:

One important use of ideals is that they can be used to construct a quotient ring, just like defining a quotient group. Given a ring \(R\) and a two-sided ideal \(I\), we can define the set of cosets \[R/I=\{r+I|r\in R\}.\] This is first and foremost an Abelian group, the quotient group of \(R\) by the subgroup \(I\), with elements being cosets \(r+I\) or understood as representatives of the equivalence relation on \(R\) determined by \(I\). Its multiplication is inherited from the larger ring \(R\), defined as \[(r+I)(s+I)=rs+I.\] It can be easily verified that due to the absorption property of ideals, as a subset of \(R\), the product \((r+I)(s+I)\subset rs+I\). Therefore, the above multiplication is well-defined (independent of the choice of representatives).

Prime Ideals

The concept of ideals comes from number theory, so naturally, it is related to many arithmetic concepts. In number theory, the most important step in proving the unique factorization law for natural numbers is to prove the Euclidean lemma, which states that if \(p\) is a prime number and \(p|ab\), then \(p|a\) and \(p|b\) must hold. From the perspective of ideals, \((p)=p\mathbb{Z}\subset \mathbb{Z}\) is the set of multiples of \(p\), which is an ideal of \(\mathbb{Z}\). In this case, we have \[ab\in (p)\Rightarrow a\in (p) \text{or} b\in (p).\] We can generalize this concept to any ring. If a proper ideal \(I\in R\) satisfies the above property, then \(I\) is called a prime ideal. That is, if \[ab\in I\Rightarrow a\in I \text{or} b\in I,\] then \(I\) is a prime ideal. For a commutative ring \(R\), the set of all prime ideals is usually denoted by \({\rm Spec}(R)\). Note that the trivial ideal is not a prime ideal. This is a convention, similar to the convention that \(1\) is not a prime number. The reason is that \(1\) is a unit, and should not be called a prime number.

Another useful concept is the maximal ideal. A proper ideal \(I\) of a ring \(R\) is a maximal ideal (left, right, two-sided) if there is no proper ideal (left, right, two-sided) of \(R\) that contains \(I\). We state a few simple properties of maximal ideals.

Kernels and Images of Homomorphisms

Just like the kernels and images of group homomorphisms, for a ring homomorphism \(f:R\to S\), we can define \[\ker(f):=\{r\in R|f(r)=0\}\] and \[{\rm Im}(f):=\{f(r)| r\in R\}.\]

We have an obvious isomorphism theorem.

Noetherian Property

If all ideals in the ring \(R\) are finitely generated, i.e. any ideal \(I\subset R\) can be expressed as \[I=Ra_1+Ra_2+\dots+Ra_n\] (where for right ideals, we replace \(Ra_i\) with \(a_iR\)), where \(a_i\in R\), then we say that \(R\) is a Noetherian ring (left, right, or two-sided). This is an important and fundamental property in ring theory, and most of the rings we study are Noetherian.

There are several classical equivalent statements about the Noetherian property, as follows:

The following fundamental theorem shows that many rings are Noetherian.

Arithmetic in Principal Ideal Domains

In this section, we assume that all rings are commutative. In this case, there is no need to distinguish between left and right ideals, and we refer to them collectively as ideals. Let \(a_1,\dots, a_n\in R\), we define the ideal notation \[(a_1,\dots, a_n):= Ra_1+Ra_2+\dots +Ra_n\] to represent the ideal generated by \(a_1,\dots,a_n\). If an ideal \(I\) can be generated by a single element \(a\in R\), i.e. \(I=(a)\), then we call it a principal ideal. If all ideals of an integral domain \(R\) are principal, then we call it a principal ideal domain (PID).

Let \(R\) be a general integral domain. Similar to how we define prime numbers, we call a non-unit element \(a\in R\) irreducible if \(a=bc\) implies that either \(b\) or \(c\) is a unit. We also call \(p\in R\) a prime element if \((p)\) is a prime ideal, meaning that \(p|ab\) implies \(p|a\) or \(p|b\). We know that in the case of the integer ring \(\mathbb{Z}\), irreducible elements and prime elements are equivalent, but this is not necessarily true in a general integral domain. Interestingly, this is true in a PID.

We will now show that principal ideal domains have very good properties in terms of arithmetic.

We first prove a lemma, which is equivalent to the existence of decomposition.

Note that although the unique factorization property may seem obvious and you might think it holds in all rings, this is not the case. For example, in \(\mathbb{Z}[\sqrt{-5}]=\{a+b\sqrt{-5}|a,b\in\mathbb{Z}\}\), we have \[6=2\cdot 3 = (1+\sqrt{-5}) (1-\sqrt{-5})\] These are two distinct factorizations of \(6\). The interesting thing is that the factors appearing in these factorizations are irreducible but not prime.

Interesting Example: Gaussian Integers

A Gaussian integer is defined as \(R=\mathbb{Z}[i]=\{a+bi| a,b\in\}\). We will use a method similar to \(\mathbb{Z}\) to prove that \(\mathbb{Z}[i]\) is a PID and therefore a UFD. We define a norm in the ring \(\mathbb{Z}[i]\): \[N(a+bi):= a^2+b^2\] It describes the ’size’ of elements in the ring. It is easy to see that this norm is multiplicative, i.e. \(N(\alpha \beta)=N(\alpha)N(\beta)\). This also has implications in arithmetic.

Let’s see the powerful application of the fact that \(\mathbb{Z}[i]\) is a UFD.

Polynomial rings over fields are PID

This conclusion is very classic and important. We still give its proof here, which is similar to the proof of Euclidean division.

Fractionalization and Fraction Field of Rings

This section discusses only commutative rings. For an integral domain \(R\), we can take a multiplicative subset \(S \subset R\), that is, a subset satisfying \(a \in S, b \in S \Rightarrow ab \in S\). Without loss of generality, we can assume that \(1 \in S\). The fractionalization of the ring \(R\) with respect to \(S\) is defined as \[S^{-1}R := \left\{\frac{r}{s} | r \in R, s \in S\right\}\] This set can be naturally equipped with addition and multiplication structures \[\frac{r}{s} + \frac{r'}{s'} := \frac{rs' + sr'}{ss'} \in S^{-1}R\] \[\frac{r}{s} \cdot \frac{r'}{s'} := \frac{rr'}{ss'} \in S^{-1}R.\] Two fractions \(r/s, r'/s'\) are considered equivalent if and only if \(rs' - r's = 0\). It can be easily verified that this forms a ring. If we take \(S = R \backslash \{0\}\), then the resulting fractionalization is denoted as \({\rm Frac}(R)\) and is called the fraction field of \(R\).

By following the prompts below, prove that \(K[x,y]\) is a UFD. Hence, it can be concluded that a UFD is not necessarily a PID.

1. Let \(K(x)\) be the field of fractions of \(K[x]\). Then \(K(x)[y]\) is a polynomial ring over the field \(K(x)\), and thus a PID.

2. Place any polynomial \(f(x,y)\in K[x,y]\) into \(K(x)[y]\) to obtain a factorization.

3. Examine this factorization in some \((K[x]/(p(x)))[y]\), where \(p(x)\in K[x]\) is some irreducible polynomial. Note that \(K[x]/(p(x))\) is a field, and thus \((K[x]/(p(x)))[y]\) is also a PID.

4. Prove that \(K[x,y]\) is a UFD.

Elementary Number Theory in Cryptography

\(\mathbb{Z}/n = \mathbb{Z}_n\) is an abelian group, representing the \(n\) residue classes modulo \(n\), and forms a group under addition. If we consider \(\mathbb{Z}_n^\times = (\mathbb{Z}/n)^\times\), the set of all residue classes coprime to \(n\), this set forms a group under multiplication, and its order is \(\varphi(n)\). According to Lagrange’s theorem, for any \(a\in \mathbb{Z}_n^\times\), we have \(a^{\varphi(n)}=1\), which means that for any integer \(a\) coprime to \(n\), we have \[a^{\varphi(n)} \equiv 1 \mod n.\] This is the Euler-Fermat theorem in elementary number theory. This theorem has interesting applications in modern cryptography.

In public key cryptography, people hope to achieve the following goals:

• We need to communicate in a channel that is reliable in terms of communication quality, but not secure in terms of information security.

• We want only the sender and receiver to be able to decipher the content of the message, while any third party eavesdropping on the channel can only obtain the ciphertext, not the plaintext.

• We also hope that this encryption communication system does not require pre-distribution of keys.

The most secure encryption method in classical cryptography is the one-time pad, where both parties in communication prepare a long random string \(k\in \mathbb{Z}_n^m\) as a one-time key that only they know. Before communication, the key \(k\) is added to the plaintext \(x\) to obtain the ciphertext \(x+k\). Since \(k\) is completely random and independent of \(x\), the distribution of \(x+k\) is also completely random, i.e. it has a trivial uniform distribution. Therefore, anyone who only obtains \(x+k\) without knowing \(k\) cannot gain any information about \(x\). The recipient only needs to calculate \((x+k)-k=x\) to obtain the original message. However, this key can only be used once, as \(x\) has a non-trivial probability distribution, making it unsafe to use the same key multiple times. Therefore, both parties need to prepare a large number of one-time keys, which is not only inconvenient but also makes key distribution a difficult problem: after using a one-time key, it is difficult to ensure that the key can be securely distributed to the other party (through a channel or offline).

The beginning of modern cryptography, the RSA public key encryption system, solves this problem by introducing elementary number theory and the concept of asymmetric encryption. Consider a large integer \(n=pq\) formed by multiplying two large prime numbers, then \(\mathbb{Z}_n^\times\) is a group of order \(\varphi(n)=(p-1)(q-1)\). That is, for \(a\in\mathbb{Z}^\times\), \(a^{(p-1)(q-1)}=1\). In fact, the corresponding congruence \[a^{\varphi(pq)}\equiv 1 \mod pq\] holds for all \(a\in \mathbb{Z}-(pq)\mathbb{Z}\). This means that if we take a pair of exponents \((e,d)\) such that \(ed\equiv 1\mod \varphi(pq)\), we will have \[(x^{e})^d \equiv x^{eq} \equiv x \mod n\] for all \(x\). Therefore, we can use \(e\) to encrypt the message \(x\in \mathbb{Z}/n\), obtaining the ciphertext \(x^e\in \mathbb{Z}/n\), and then use \(d\) to decrypt it, obtaining \(x^{ed}=x\in \mathbb{Z}/n\). Note that the key used for encryption and the key used for decryption are different, and their relationship needs to be obtained by solving \(ed=1 \in \mathbb{Z}/(p-1)(q-1)\) (according to ideal theory, it is only necessary to ensure that \(e\) and \((p-1)(q-1)\) are coprime to exist \(ex+(p-1)(q-1)y=1\)). If \(p,q\) are large, it will be difficult to factor \(n\), and without factoring \(n\), it is impossible to know the value of \((p-1)(q-1)\) (it can be easily proved that, given \(n\), knowing \((p-1)(q-1)\) is equivalent to knowing \(p\) and \(q\)). Therefore, we can construct the following encryption system without the need for key distribution:

1. First, generate two random, large prime numbers \(p,q\).

2. Calculate \(n=pq, m=(p-1)(q-1)\).

3. Randomly generate an integer \(e\) that is coprime to \(m\), and use Euclidean division to calculate \(d\) such that \(ed\equiv 1\mod m\).

4. Publicly announce \((n,e)\) as your public key, keep \(d\) as private (secret) information, and keep or discard information such as \(p,q,m\).

5. When someone needs to send an encrypted message \(x\in\mathbb{Z}/n\) to you, they can calculate \(x^e\in \mathbb{Z}/n\) and send it to you through a channel.

6. A third party who obtains \(x^e\) cannot know \(x\) because they do not know \(d\) and cannot factor \(n\).

7. You only need to calculate \((x^e)^d=x\in \mathbb{Z}/n\) to decrypt the original message.

Modules and Linear Algebra

Basic Knowledge of Modules

Modules can be considered as the most extensive and important algebraic structure in modern algebra. It can be seen as a natural generalization of linear algebra, but the phenomena it contains far exceed those of vector spaces over fields. Just as groups can act on sets, we can also let rings act on a set. However, we hope that the addition and multiplication of the ring can naturally act on such a set. If we regard the multiplication in the ring as the composition of actions, we are still not sure how the addition of the ring can cooperate with this action, so we need an additional structure for addition. This leads to the definition of modules:

Rings can be very complicated, and so can the modules over them. However, there are two types of modules that are particularly important, namely modules over fields (vector spaces) and modules over principal ideal domains (finitely generated).

Homomorphism of Modules

The meanings of monomorphism, epimorphism, and isomorphism are obvious and will not be repeated here. If there exists a module homomorphism \(\varphi:M\to N\), we say that \(M\) and \(N\) are isomorphic and denote it as \(M\cong N\). Since the theory of right modules is completely similar, we will mostly consider left modules by default.

For a subset \(N\subset M\) of \(M\), if it satisfies \(RN\subset N\), we call \(N\) a submodule of \(M\). For any submodule, we can construct a quotient module \(M/N\), whose elements are cosets \(m+N\), and the action is defined as \[r(m+N):=rm+N\] It can be easily verified that this definition does not depend on the choice of coset representatives and satisfies the definition of an \(R\)-module.

The following two theorems are essentially the same as the isomorphism theorem in group theory.

Exact Sequence

When we have a sequence of modules and homomorphisms if \(\ker(g)={\rm Im}(f)\), we say that the sequence is exact at \(N\). If a sequence of mappings of modules is exact at every point (except the leftmost and rightmost endpoints), we say that it is an exact sequence.

Basic Construction of Modules

In this section, we will discuss how to construct new modules from existing ones. The methods we know include quotient modules, module intersections, and module sums.

\({\rm Hom}\) Functor

Given two left \(R\)-modules \(M\) and \(N\), we can define the set of all \(R\)-module homomorphisms from \(M\) to \(N\) as \({\rm Hom}_R(M,N)\). For a collection of multiple module homomorphisms \(((A_i)|(B_j))\), we denote the set as \({\rm Hom}_{(A_i)|(B_j)}(M,N)\). Sometimes, to distinguish the direction of module homomorphisms, we use the notation \({\rm Hom}_{R|}(M,N)\) to denote the set of left \(R\)-module homomorphisms from \(M\) to \(N\). For two homomorphisms \(f:M\to N\) and \(g:M\to N\), we can define their sum as \[(f+g)(m):=f(m)+g(m)\] which is also a homomorphism. Therefore, \(f+g\in {\rm Hom}_R(M,N)\), showing that \({\rm Hom}_R(M,N)\) is an Abelian group. It is worth noting that if both \(M\) and \(N\) are either left or right \(R\)-modules without any multiple structure, then their \({\rm Hom}_R(M,N)\) does not have a natural \(R\)-module structure and is only an Abelian group (a \(\mathbb{Z}\)-module). However, if at least one of \(M\) and \(N\) has a multiple structure, the \({\rm Hom}\) functor can be naturally endowed with a module structure, which we will demonstrate.

Module Structure of \({\rm Hom}\)

Let \(R\) and \(S\) be two rings. If \(M\) has a left \(R\)-module structure and a right \(S\)-module structure, we write it as \({}_RM_S\) when we need to specify the module structure.

We will give an example to show that \({\rm Hom}_R({}_RM_S,{}_RN)\) has a left \(S\)-module structure. This is because we can define, for \(f\in{\rm Hom}(M,N)\) and \(s\in S\), \[(sf)(m):= f(ms)\] Then \((sf)\) is clearly a left \(R\)-module homomorphism (we need to use the definition of multiple module: the module structures of multiple rings need to be compatible with each other). We need to verify that \({\rm Hom}_R(M,N)\) satisfies the definition of a left \(S\)-module, all other properties are obvious, the only one that needs careful checking is the associativity: \[(s's)f = s'(sf)\] The left homomorphism is \(m\mapsto f(ms's)\), the right homomorphism is \(s'(m\mapsto f(ms))=m\mapsto f(ms's)\), so this is true, which means that \({\rm Hom}_R(M,N)\) becomes a left \(S\)-module under this definition.

There are a total of eight similar cases, and we list all cases in the following table:

In summary, the direction of the \(S\)-module structure on \(N\) determines the direction of the \(S\)-module structure on \({\rm Hom}_R(M,N)\). If the bimodule structure appears on \(M\), the action will be reversed by composing functions from the inside out, causing a change in the direction of the module.

Endomorphism Ring

When \(M=N\), \({\rm Hom}_R(M,M)\) is denoted as \({\rm End}_R(M)\), and it has a natural ring structure, where multiplication is the composition of homomorphisms from \(M\) to \(M\).

Functoriality of \({\rm Hom}\)

What does the \({\rm Hom}\) functor mean? The so-called functor is an abstract concept in modern category theory, which describes how objects in different categories correspond to each other. It requires:

1. To correspond the object \(A\) to the object \(F(A)\).

2. To correspond the map \(f:A\to B\) to another map \(F(f):F(A)\to F(B)\) or \(F(f):F(B)\to F(A)\). If it satisfies the former, it is called a covariant functor, and if it satisfies the latter, it is called a contravariant functor.

3. The functor must preserve composition, i.e. \(F(f\circ g)=F(f)\circ F(g)\).

4. We also require the functor to correspond the identity map to the identity map, i.e. \(F(1_A)=1_{F(A)}\).

As an example, we will explain in detail how \({\rm Hom}\) forms a functor.

• For a fixed \(R\)-module \(N\), we find that \(M\mapsto {\rm Hom}_{R}(M,N)\) is a contravariant functor, sometimes denoted as \(h_N\). This functor maps the \(R\)-module \(M\) to the Abelian group \({\rm Hom}_R(M,N)\), and maps the \(R\)-module homomorphism \(f:M'\to M\) to the group homomorphism \[{\rm Hom}(f,N):={\rm Hom}(M,N)\to {\rm Hom}(M',N):h\mapsto h\circ f.\] It is clear that it preserves composition and identity maps.

• Similarly, for a fixed module \(M\), we find that \(N\mapsto {\rm Hom}_R(M,N)\) is a covariant functor, which maps the module homomorphism \(g:N'\to N\) to the group homomorphism \[{\rm Hom}(M,g):={\rm Hom}(M,N')\to {\rm Hom}(M,N):h\mapsto g\circ h.\] It also preserves composition and identity maps.

Direct Sum

Given two left \(R\)-modules \(M,N\), their direct sum \(M\oplus N\) is defined as the set \(M\times N=\{(m,n)|m\in M, n\in N\}\) as an Abelian group, with addition defined as component-wise addition, and \(R\)-action defined as \[r(m,n):=(rm,rn)\] It can be easily verified that this definition gives an \(R\)-module structure. Direct sums are not limited to finite sums, for any family of \(R\)-modules indexed by a set \(I\), \(\{M_\lambda\}\), we can define the direct sum as \[\bigoplus_{\lambda\in I} M_\lambda:=\left\{(m_\lambda)\in \prod_{\lambda\in I} M_\lambda | \text{at most finitely many $m_\lambda$ are non-zero}\right\}.\] If we take a sequence of identical modules \(M_{\lambda}=M\), we denote this direct sum as \(M^{(I)}\).

Direct Product

Similar to direct sum, a direct product of a family of modules \(M_\lambda\) is obtained by giving the set \(\prod_\lambda M_\lambda\) a natural module structure. The difference is that in the direct product, we do not require that each component of an element has only finitely many non-zero elements. Any sequence \((m_\lambda)\in \prod M_\lambda\) is allowed as an element. Similarly, if we take a sequence of the same module \(M_\lambda=M\), we denote this direct product as \(M^I\).

Free Module

A module obtained from an arbitrary number of direct sums (possibly infinite) of \(R\), or a module isomorphic to it, is called a free \(R\)-module. For example, \(R^n = R \oplus R \oplus \dots \oplus R\) (\(n\) direct sums of \(R\)).

The importance of free modules lies in their good properties. Any homomorphism \(f: R^n \to M\) starting from \(R^n\) can be easily determined by specifying where each \(e_i = (0, \dots, 0, 1, 0, \dots, 0) \in R^n\) (the \(i\)-th position is \(1\)) is mapped to. The entire homomorphism is completely determined by this. Because every element \((r_1, \dots, r_n) \in R^n\) can be written as \[(r_1, \dots, r_n) = \sum r_i e_i,\] we have \[f((r_1, \dots, r_n)) = \sum f(r_i e_i) = \sum r_i f(e_i).\] It is worth noting that there is no restriction on how to choose the value of \(f(e_i)\). In other words, the determination of \(f\) depends entirely on the arbitrary choice of \(n\) values \(f(e_i)\), or, it depends on an arbitrary element \((f(e_1), f(e_2), \dots, f(e_n)) \in M^n\). This gives the following natural isomorphism \[{\rm Hom}_R(R^n, M) = M^n.\]

Generators and Basis

For a (left) \(R\)-module \(M\), after selecting a family of elements \((m_i)_{i\in I\in M^I}\), we can define a map \(\oplus (r\mapsto rm_i):R^{(I)}\to M\) from \({\rm Hom}_R(R^{(I)},M)=M^I\). We temporarily denote this map as \(\rho\). The image of this map is called the \(R\)-linear combination of \(m_i\). We say that \(\{m_i\}_{i\in I}\subset M\) is a set of generators of \(M\) if \(\rho:R^{(I)}\to M\) is surjective. In other words, any \(m\in M\) can be written as a finite linear combination of \(m_i\): \[m=r_{1}m_{i_1}+\dots+r_n m_{i_n}.\] If there exists a finite family of \(m_i\) that generates \(M\), then \(M\) is called finitely generated. We say that \(\{m_i\}_{i\in I}\) is a set of \(R\)-linearly independent elements, or simply independent, if the corresponding map \(\rho:R^{(I)}\to M\) is injective. In other words, if any finite subset of \(m_i\), \(m_{i_1},\dots, m_{i_n}\) has any \(R\)-linear relation \[r_1 m_{i_1}+\dots +r_n m_{i_n}=0,\] then all coefficients \(r_1=r_2=\dots=r_n=0\). If a set of elements \(\{m_i\}\) is both a set of generators and independent, then it is called a basis of \(M\).

Basis of Vector Space

The best thing about linear space is that it must have a basis, so all linear spaces are isomorphic to some free \(k\)-module. This makes linear space very easy to study, and we will explain this. Next, we assume that \(V\) is a \(k\)-vector space.

Dimension Theory

If \(V\) has two different bases \(B_1, B_2\), we hope to prove that \(B_1\) and \(B_2\) are equipotent, that is, there exists a bijection between them.

Finite Case

If \(B_1, B_2\) are both finite, let \(m = |B_1|\) have fewer elements. We use induction on \(m\) to prove that \(|B_2| \le m\). If \(m = 1\), \(B_1 = \{b\}\), then any element in \(B_2\) can be written as a nonzero \(k\)-coefficient multiple of \(b\), and they cannot be linearly independent unless \(|B_2| = 1\).

Now assuming that the proposition holds for \(|B_1|\le m\), we consider the case where \(|B_1|=m+1\). Let \(a\in B_2\), by the basis extension theorem, there exists a basis \(B=\{a\}\cup B'\) such that \(\{a\}\subset B\subset \{a\}\cup B_1\), so \(V\simeq ka\oplus \left(\bigoplus_{b'\in B'} kb'\right)\), and \(V'=V/ka\) has \(B'\) (as the projection image) as a basis, with \(m\) elements. Similarly, \(V'\) also has \(B_2-\{a\}\) as a basis, so \(|B_2|-1\le m\).

Infinite case

Now assuming that \(V\) has an infinite basis \(B\), so \(V\cong k^{(B)}\), if \(C\) is another basis, for each \(c\in C\), there exists a finite expression \(c=\sum_{b\in B} c_b b\) where only finitely many \(c_b\) are non-zero. Then for any \(c\in C\), consider the finite set \(B_c:=\{b\in B|c_b\neq 0\}\), since \(C\) can generate the entire space, for each \(b\) there must be some \(c\) with non-zero coefficient for \(b\), so we have \[\bigcup_{c\in C} B_c=B\] Since \(B\) is infinite, this implies \(|C|\ge |B|\), and since \(B\) is infinite, we can use the same reasoning to show that \(|B|\ge |C|\).

Matrices over Commutative Rings

Finitely Generated Free Modules

In this section, we assume that \(R\) is a commutative ring. It is worth noting that in the free module \(R^m\), there exists a standard basis, where each element can be uniquely written in the form \(a_1e_1+a_2e_2+\dots+a_me_m\).

If an \(R\)-module \(M\) is isomorphic to \(R^n\), we say that \(M\) has rank \(n\). However, we have not yet proven the uniqueness of rank, that is, we need to prove \(R^m\cong R^n\Rightarrow m=n\). Unfortunately, this is not always true in general rings. But at least in the case of PIDs, this is true. To prove this, we need to develop some knowledge of linear algebra over rings.

Matrices over Rings

We consider the \(R\)-module homomorphisms from \(R^n\) to \(R^m\). Since \[{\rm Hom}_R(R^n,R^m)=({\rm Hom}_R(R,R^m))^n=(R^m)^n=R^{mn}\] we know that to determine a homomorphism \(\varphi:R^n\to R^m\), it is essentially enough to know where each \(e_j\in R^n\) is mapped to in \(R^m\). We use \(e'_i\in R^m\) to denote the standard basis of \(R^m\). If we denote the \(i\)th component of the image of \(e_j\) as \(a_{ij}\), then we can write \[\varphi(e_j)=\sum_{i} a_{ij}e'_i\] Here \(a_{ij}\in R\) are the \(mn\) elements in \(R\) that we want. We can arrange these elements into a matrix \[A=\left( \begin{array}{ccccc} a_{11}& a_{12} & a_{13} & \dots & a_{1n} \\ a_{21}& a_{22} & a_{23} & \dots & a_{2n} \\ \dots & \dots & \dots & \dots & \dots \\ a_{m1}& a_{m2} & a_{m3} & \dots & a_{mn} \\ \end{array} \right)\] Matrices are usually represented by capital letters \(A,B,\dots\), etc. Here our matrix is the matrix of \(\varphi\), which we also denote as \(A_\varphi\). When we need to emphasize that the matrix elements are \(a_{ij}\), we write \(A=(a_{ij})_{1\le i\le m,1\le j\le n}\). This matrix has \(m\) rows and \(n\) columns, and we say it is an \(m\times n\) matrix over \(R\), denoted as \(A\in M_{m\times n}(R)\). When \(m=n\), this notation is simply written as \(M_n(R)\).

Composition of mappings and multiplication of matrices

For \(f,g\in {\rm Hom}_R(R^n,R^m)\), and \(r\in R\), we can define the homomorphisms \(rf\) and \(f+g\). Similarly, we can define scalar multiplication and addition of matrices, i.e. we define \(r\) multiplied by \(A_f\) as the matrix \(B_{rf}\) corresponding to the mapping \(rf\): \[rA_f := B_{rf}\] Let \(A_f\) and \(B_g\) be the matrices corresponding to the homomorphisms \(f\) and \(g\), respectively. Then we define \(A+B\) as the matrix \(C_{f+g}\) corresponding to the mapping \(f+g\): \[A_f+B_g:=C_{f+g}.\]

When we have the composition of homomorphisms we can calculate \(C_{gf}\) using \(A_f\) and \(B_g\), and we call this process matrix multiplication, denoted as \[B_g\cdot A_f=C_{gf}.\] How do we actually perform this operation? We can write out the matrices \(A_f=(a_{ij}),B_g=(b_{ij})\) as \[f(e_j)=\sum_i a_{ij}e'_{i}\] \[g(e'_i)=\sum_k b_{ki}e''_k\] Therefore, \[(g\circ f)(e_j)=g(f(e_j))=g\left(\sum_{i}a_{ij} e'_i\right)=\sum_k\left(\sum_{i} b_{ki} a_{ij}\right)e''_k.\] This shows that the coefficients of \(C_{gf}=(c_{ij})=B\cdot A\) should be \[c_{ij}=\sum_{k} b_{ik}a_{kj}.\] This is the formula for matrix multiplication. Note that \(B\) is \(n\times m\), \(A\) is \(m\times l\), and \(BA\) is \(n\times l\), which means that matrix multiplication gives a mapping \[M_{n\times m}(R)\times M_{m\times l}(R) \to M_{n\times l}(R).\] When \(m=n=l\), this multiplication operation gives multiplication on \(M_n(R)\), making \(M_n(R)\) a (usually non-commutative) ring.

Reduction Theory of Matrices over PID

In this section, we assume that \(R\) is a PID and consider an \(m\times n\) matrix \(M\in M_{m\times n}(R)\) over \(R\). Note that, by matrix multiplication, \(M_{m\times n}(R)\) has a \((M_{m}(R),R;M_{n}(R),R)\) multi-module structure, which means that it can be acted upon by \(m\)-order square matrices on the left and \(n\)-order square matrices on the right.

The group formed by the multiplicative inverses in the ring \(M_n(R)\) is called \(GL_n(R)\). We say that \(A, B \in M_{m \times n}\) are equivalent if there exist two invertible elements \(P \in GL_m(R)\), \(Q \in GL_n(R)\) such that \(A = PBQ\). Note that equivalence is an equivalence relation.

Elementary Transformations of Matrices

For the matrix multiplication \(C = BA\), we can interpret it as \(C\) being a recombination of the columns of \(B\) and the rows of \(A\), with the coefficients determined by another matrix. From the formula for matrix multiplication \[c_{ij} = \sum_k b_{ik}a_{kj}\] we can see that the \(j\)th column of \(C\) is obtained by multiplying the first column of \(B\) by \(a_{1j}\), adding the second column of \(B\) multiplied by \(a_{2j}\), and so on until the \(k\)th column multiplied by \(a_{kj}\). Similarly, the \(i\)th row of \(C\) is obtained by multiplying each \(k\)th row of \(A\) by the corresponding \(b_{ik}\) and then adding them together. Thus, left multiplication by a matrix corresponds to row operations, while right multiplication corresponds to column operations.

The so-called elementary transformation refers to a class of simple and basic reversible operations on matrices. These transformations can be applied to a matrix by left and right multiplying with some simple invertible matrices. There are several types of elementary transformations:

1. Multiplying one row (or column) of the matrix by a non-zero element in \(R\), and then adding it to another row (or column). For example, multiplying the first row of \(A\) by \(r\) and adding it to the second row: \[\left(\begin{array}{cc} 1 & 0 \\ r & 1 \\ \end{array}\right) \left( \begin{array}{cc} a_{11} & a_{12}\\ a_{21} & a_{22}\\ \end{array} \right) = \left( \begin{array}{cc} a_{11} & a_{12}\\ ra_{11}+a_{21}& ra_{12}+a_{22}\\ \end{array} \right).\]

2. Rearranging the rows or columns of the matrix. Let \(A=(a_{ij})\in M_{m\times n}(R)\), if we want to rearrange the rows of the matrix using the permutation \(\sigma\in S_m\), we left multiply with an \(m\)-dimensional matrix \(P=(\delta_{\sigma(i)j})\). Here, \(\delta_{ij}=1_{i=j}\) is a function that equals \(1\) when \(i=j\) and \(0\) otherwise. We have \[(PA)_{ij}=\sum_k \delta_{\sigma(i)k}a_{kj} = a_{\sigma(i)j}.\] Such a matrix is called a permutation matrix. Similarly, to rearrange the columns of the matrix, we right multiply with an \(n\)-dimensional permutation matrix.

3. Multiplying a row or column of the matrix by a unit \(u\in R^\times\). This can be achieved by left or right multiplying the matrix with a diagonal matrix \[\left( \begin{array}{ccccc} 1 & & & & \\ & u & & & \\ & & 1 & & \\ & & & \dots & \\ & & & & 1\\ \end{array} \right).\] The row (or column) containing \(u\) is the one that needs to be multiplied.

4. Adding \(a\) times the \(i\)th row (or column) of the matrix to \(b\) times the \(j\)th row (or column) to create a new \(i\)th row (or column), and adding \(c\) times the \(i\)th row (or column) to \(d\) times the \(j\)th row (or column) to create a new \(j\)th row (or column), where \(ad-bc=1\). This is also a reversible transformation, which is equivalent to left multiplying with the following matrix (for the column case: right multiply and swap \(b\) and \(c\)): \[\left( \begin{array}{ccccc} \dots & & & & \\ & a & & b & \\ & & \dots & & \\ & c & & d & \\ & & & & \dots\\ \end{array} \right)\] where the omitted parts are all diagonal \(1\)s. Its inverse is \[\left( \begin{array}{ccccc} \dots & & & & \\ & d & & -b & \\ & & \dots & & \\ & -c & & a & \\ & & & & \dots\\ \end{array} \right).\]

It is worth noting that these elementary transformations are all reversible, and their inverses are also elementary transformations. Moreover, a series of elementary transformations can be obtained by left-multiplying a matrix and right-multiplying another matrix. This is because performing a series of row and column elementary transformations can be viewed as multiplying a series of \(P_i\) and \(Q_i\) in a certain order. By the associative law, the result can be written as \[(P_k\dots P_1)A (Q_1\dots Q_k)\] Of course, this is equivalent to saying that \(M_{m\times n}(R)\) is a multi-module of \((M_m(R);M_n(R))\).

Equivalent Canonical Form

1. Suppose \(A\) is not necessarily invertible. Prove that the kernel of \(A\), denoted by \(\ker A\), can be generated by \(Qe_{r+1},\dots,Qe_n\), where \(Q\) is the matrix that transforms \(A\) into its equivalent standard form, and \(r={\rm rank}A\) is the number of nonzero \(d_1|\dots|d_r\).

2. Obtain the following algorithm for computing the submodule \(\ker A\subset R^n\): Write the two matrices \((A|I)\) side by side, where \(I\) is the identity matrix. Apply elementary transformations to \(A\) and perform the same column operations on \(I_n\), but do not perform any row operations. When \(A\) is transformed into standard form, the submodule generated by the last \(n-r\) columns of the right matrix is \(\ker A\).

Let \(\varphi:V\to W\) be a linear map. Under a certain basis of \(V\) and \(W\), the corresponding matrix is \(A\in M_{m\times n}(k)\). Prove that \({\rm rank}A=\dim_k {\rm Im}\varphi\).

Structure of Finite-Generated Modules on PID

Using the results established in this chapter, we will prove two important conclusions. The first is that the rank of a (finite-generated) free module on a PID is determined, that is, \(R^m\cong R^n\Rightarrow m=n\). The second is that a submodule of a finite-generated free module on a PID is still a finite-generated free module.

Rank of Finite-Generated Free Modules

In fact, this holds for all integral domains.

Submodules of finitely generated free modules

Noetherian Modules

A Noetherian module is a module in which all submodules are finitely generated (and hence the module itself is also finitely generated).

Similar to Noetherian rings, we have the following equivalent statements:

In order to show that all common modules are Noetherian modules, we construct other Noetherian modules starting from \(R\).

As a conclusion, if \(R\) is a Noetherian ring, \(R^n\) is Noether, so all finitely generated \(R\)-modules are Noether, because they are all homomorphic images of some \(R^n\).

Finite generated free modules over PID

Let \(R\) be a PID, then \(R\) is obviously a Noetherian ring, so \(R^n\) is a Noetherian module, so all its submodules are finitely generated. Let \(N \subset R^n\) be a submodule, since it is finitely generated, there is a surjection \(R^m \to N\), which can be composed with the natural map \(N \to R^n\) to obtain a map \(f: R^m \to R^n\), whose image is \(N\). So we can write this map as an \(n \times m\) matrix \(A\), consider the equivalent standard form of \(A\), there are invertible \(n\)-order and \(m\)-order square matrices \(P, Q\) such that \(PAQ = D\), where \(D\) is a diagonal matrix. Translating back to the language of maps, this means that there are two isomorphic maps \(p: R^n \to R^n\) and \(q: R^m \to R^m\) such that \(p \circ f \circ q = \delta: R^m \to R^m \to R^n \to R^n\). Obviously \({\rm Im}(f) = {\rm Im}(f \circ q) \cong {\rm Im}(p \circ f \circ q) = {\rm Im}\delta\), where the matrix corresponding to \(\delta\) is \(D\), which is of the following form \[\left( \begin{array}{ccccc} d_1 & & & & \\ & d_2 & & & \\ & & \dots & & \\ & & & d_r & \\ & & & & O \end{array} \right).\] Here \(d_i \in R\), \(r \le n\). So we know that there is a basis \(e_1', e_2', \dots, e_n'\) of \(R^n\) such that \({\rm Im}\delta = d_1Re_1' \oplus d_2Re_2' \oplus \dots \oplus d_rRe_r'\), where the direct sum is an internal direct sum. This \({\rm Im}\delta\) is already isomorphic to \(N\), if you want to change back to the original form of \(N\), then since \(p^{-1}\) is an isomorphism, \[N = p^{-1}({\rm Im}\delta) = \bigoplus_{i \le r} d_iR p^{-1}(e_i').\] Here \(e_i = p^{-1}(e_i')\) still forms a basis of \(R^n\), because \(p^{-1}\) is an isomorphism. So there is a basis \(e_1, \dots, e_n\) of \(R^n\) such that \[N = d_1Re_1 \oplus \dots \oplus d_rRe_r.\]

Finite Generation Modules over PID

Any finite generation module \(M\) is the homomorphic image of a free module, and thus is the quotient of a free module by one of its submodules. We know that the submodules of a free module \(R^n\) over a PID are of the form \((d_1)e_1\oplus \dots \oplus (d_r)e_r\), where \(e_i\) is a basis of \(R^n\) (not necessarily the standard basis). Therefore, under the isomorphism \(R^n\cong Re_1\oplus \dots Re_n\), this quotient is isomorphic to \[R/(d_1)\oplus\dots\oplus R/(d_r)\oplus R^{n-r}\]

Standard Form of Linear Maps

In this section, we consider \(\varphi:V\to V\) as a linear map on a finite-dimensional \(k\)-vector space. Let \(B=\{e_1,\dots,e_n\}\) be a basis of \(V\) and write \(\varphi\) in matrix form \(A\). A problem arises here, as there is no explicit choice of basis in the vector space \(V\) and the definition of \(\varphi\). In fact, many linear spaces and maps can be defined without specifying a basis, i.e. without relying on the choice of basis. However, if we want to write it in matrix form, we must artificially choose a basis. This leads to the following questions:

1. How does the choice of different bases affect the matrix?

2. Is there a ’best’ or ’good’ special basis that simplifies the form of the matrix?

Similar Matrices

Let’s first look at the first question. Let \(B'=\{e_1',\dots,e_n'\}\) be another basis, with its matrix denoted as \(A'\). The so-called matrix is essentially a mapping from \(k^n\) to \(k^n\), and its relationship with the original mapping can be described using the basis mapping \(\rho:k^{(B)}\to V\), where \(\rho\) is the mapping determined by \(\{e_1,\dots,e_n\}\) and is an isomorphism. Viewing \(A\) as a linear mapping from \(k^n\) to \(k^n\), we have \(A=\rho^{-1}\circ\varphi\circ \rho\), as shown in the commutative diagram below (a commutative diagram refers to the fact that when mappings are composed along different paths, the resulting mappings are consistent). Similarly, if \(\rho'\) is the mapping determined by another basis, we have \(A'=\rho'^{-1}\circ\varphi\circ \rho'\). Therefore, \[A'=\rho'^{-1}\rho A \rho^{-1}\rho' = (\rho'^{-1}\rho) A (\rho'^{-1}\rho)^{-1}\] This story can be represented by the commutative diagram below. Note that \(\rho'^{-1}\circ \rho:k^{(B)}\to k^{(B')}\) is also an \(n\times n\) matrix and is also an isomorphism (thus an invertible matrix). Let’s denote this matrix as \(P\) and call it the coordinate transformation matrix. We then have \[A'=PAP^{-1}.\] This way, two matrices from the same mapping are connected. If there exists an invertible matrix \(P\) such that two square matrices \(A',A\) are connected by the above relationship, we call these two matrices similar. It can be easily verified that similarity is an equivalence relation on \(M_n(k)\).

Similar Standard Form

Now we need to answer the question, given two matrices \(A, B\), how do we determine if they are similar? This is essentially a classification problem. Generally speaking, we will study this problem from the following perspectives: first, we look for invariants, which are quantities that can be calculated from matrix \(A\) and are invariant under similarity transformations. Second, we can find a representative element in each similarity equivalence class, and then see if matrices \(A\) and \(B\) can be transformed into the same representative element, or if these representative elements can be calculated from the invariants. Either way, it inspires us to approach the problem from a coordinate-independent perspective. Let us assume that our matrix is the matrix representation of a linear mapping \(\varphi\) on \(V\) under a basis. We find that, in addition to being a \(k\)-module, \(V\) can also be acted upon by \(\varphi\). By repeatedly applying \(\varphi\) and their linear combinations, we can apply any \(k\)-polynomial \(p(\varphi)\) to \(V\), where \(p(t)\in k[t]\) is a polynomial. Thus, \(V\) becomes a \(k[t]\)-module, with the action defined as \[p(t)v:=p(\varphi)v.\] We consider, if we let \(\varphi\) represent the action of the matrix, is the similarity of matrices related to the corresponding \(V\)-module structure? In fact, we can find that

So, we found that classifying matrices or mappings by similarity is equivalent to classifying \(k[t]\) modules. Note that \(k[t]\) is a PID, and we know that the structure of finitely generated modules over a PID has been completely classified! It can be written as a direct sum of modules of the form \(R/(d)\) or quasi-prime modules \(R/(p^k)\). One idea is that we can use matrices corresponding to these forms as our representatives, so we only need to transform \(V_A\) into this form to transform the matrix into standard form. Let’s first discuss what the standard form looks like.

Rational Standard Form

In the cyclic decomposition of \(V_A\), we call the obtained \(d_i\) the invariant factors of the matrix \(A\) or \(\varphi\). In order to find a simpler form, we decompose the invariant factors into a product of prime factors, thus becoming a quasi-prime decomposition, that is, \(V\) becomes a direct sum of modules of the form \(R/(p^k)\) (\(R\) will not appear in the decomposition because \(V\) is a finite-dimensional \(k\)-vector space), where \(p\in R\) is an irreducible element of \(R\). When we write \[V_A\cong R/(p_1^{k_1})\oplus \dots\oplus R/(p_r^{k_r})\] (allowing for repetition of elements in the sequences \(p_i\) and \(k_i\)), we call all of these \(p_i(t)^{k_i}\) (which can be repeated) the elementary factors of \(A\) or \(\varphi\). It is easy to see that giving the elementary factors completely determines the module structure of \(V_A\). The above decomposition is not only a direct sum decomposition of \(R\) modules, but also a direct sum decomposition as \(k\) modules. Therefore, we only need to find a \(k\)-basis for \(R/(p_i^{k_i})\) to find a \(k\)-basis for \(V\). Let \(p_i(t)^{k_i}=t^{d_i}-a_{d_i-1}t^{d_i-1}-\dots -a_{0}\) be a polynomial with leading coefficient \(1\) (because in \(k[t]\), \(k-\{0\}\) are all units), we take the images of \(1,t,t^2,\dots, t^{d_i-1}\) in \(R/(p_i^{k_i})\) as a \(k\)-basis. Then the action of \(\varphi\) on this basis is just multiplication by \(t\), so we have \[t\cdot 1=t\] \[t\cdot t=t^2\] \[\dots\] \[t\cdot t^{d_i-1}=t^{d_i}=a_{d_i-1}t^{d_i-1}+a_{d_i-2}t^{d_i-2}+\dots +a_{0}\] This gives the matrix of \(\varphi\) on the subspace \(R/(p_i^{k_i})\) as \[A_{p_i^{k_i}}= \left( \begin{array}{ccccc} & & & & a_{0}\\ 1 & & & & a_1\\ & 1 & & & a_2\\ & & \dots & & \dots\\ & & & 1 & a_{d_i-1} \end{array} \right).\] Thus, in this basis, the matrix of \(\varphi\) is a matrix composed of such matrices arranged diagonally \[A= \left( \begin{array}{cccc} A_{p_1^{k_1}} & & & \\ & A_{p_2^{k_2}} & & \\ & & \dots & \\ & & & A_{p_r^{k_r}} \end{array} \right).\] Here, all elements in the matrix belong to \(k\), and we call it the rational standard form of \(\varphi\).

Jordan Normal Form

If our field \(k\) is algebraically closed, that is, all polynomials over \(k\) have roots in \(k\), which can be decomposed into a product of linear factors (such as \(k=\mathbb{C}\)), then the matrix can be reduced to a simpler form. In this case, the irreducible polynomials over \(k[t]\) are all of the form \((t-a)\), so \(p_i^{k_i}\) must be of the form \((t-\lambda_i)^{k_i}\). We consider a more convenient \(k\)-basis for \(R/((t-\lambda_i)^{k_i})\): \((t-\lambda)^{k_i-1},(t-\lambda)^{k_i-2},\dots,1\). In this basis, the action of \(t\) is as follows: \[t\cdot (t-\lambda)^{k_i-1} = \lambda\cdot (t-\lambda)^{k_i-1}+0\] \[t\cdot (t-\lambda)^{k_i-2} = \lambda\cdot (t-\lambda)^{k_i-2}+(t-\lambda)^{k_i-1}\] \[\dots\] \[t\cdot 1 = \lambda\cdot 1+(t-\lambda)\] This shows that in this basis, \(\varphi\) has the following matrix representation on this subspace: \[J_{p_i^{k_i}}= \left( \begin{array}{ccccc} \lambda_i & 1 & & & \\ & \lambda_i & 1 & & \\ & & \lambda_i & 1 & \\ & & & \dots & 1 \\ & & & & \lambda_i \end{array} \right).\] Here the matrix is of size \(k_i\times k_i\). So \(\varphi\) has the following matrix representation on \(V\) with this chosen basis: \[A= \left( \begin{array}{cccc} J_{p_1^{k_1}} & & & \\ & J_{p_2^{k_2}} & & \\ & & \dots & \\ & & & J_{p_r^{k_r}} \end{array} \right).\] This is called the Jordan normal form of \(\varphi\). In particular, if \(k_i=1\), then \(J_{(x-\lambda_i)}=(\lambda_i)\) is a first-order matrix with only diagonal elements.

The \(k[t]\)-decomposition of \(V\)

In this section, we denote \(R=k[t]\). How can we give a surjection from \(R^n\) to \(V\)? Or in other words, how can we find a set of generators? In fact, when we give a basis \(\alpha_1,\dots,\alpha_n\) of \(V\), \(\varphi\) has a matrix representation \(A\), and \(\alpha_1,\dots,\alpha_n\) are a set of \(k\)-generators of \(V\), which are also a set of \(R\)-generators. Therefore, we consider the \(R\)-surjection determined by \(\alpha_1,\dots,\alpha_n\in V\) \[\rho:R^n\to V.\] Now to find the kernel of this mapping, we consider the matrix representation \(A\), and obviously we have \[x_i:=te_i-(a_{1i}e_1+\dots+a_{ni}e_n)\in \ker\rho.\] Here \(e_i\in R^n\) is the standard basis, which gives us \(n\) generators \(x_1,\dots,x_n\) of \(\ker\rho\). Therefore, we can construct a mapping \(R^n\to R^n\) whose image corresponds to \(x_i\), and in fact, this mapping is described by the matrix \(tI-A\in M_n(R)\). Since \(te_i=x_i+(a_{1i}e_1+\dots)\), we find that \(N=\sum R x_i + \sum k e_i\) is an \(R\)-submodule of \(R^n\). Therefore, for any \(x=\sum p_i(t)e_i\in \ker\rho\), it belongs to \(N\), and can be written as \[x=\sum q_i(t)x_i + \sum c_i e_i.\] Note that \(0=\rho(x)=\sum c_i \alpha_i\), we know that all \(c_i=0\). This shows that \(x\) is an \(R\)-linear combination of \(x_i\), and we have proved that \(x_i\) are indeed a set of generators of \(\ker\rho\).

We also need to prove that \(R^n\to R^n\) is an injection, which means that \(x_i\) is a linearly independent set over \(R\). To do this, let \(\sum q_i(t)x_i=0\). We have \[\sum_{i}q_i(t)te_i - \sum_{i,j}q_ja_{ij}e_i=\sum_i \left(q_it-\sum_{j}q_ja_{ij}\right)e_i = 0\] This implies that \(tq_i=\sum_j a_{ij}q_j\). Then we find that \((q_1,\dots,q_n)=\sum Rq_i\subset \sum kq_i\). Since \(R\) is a PID, the left ideal is a principal ideal, let it be \((d)\). If \(d\neq 0\), since \(R\) is an integral domain, \((d)\) should contain polynomials of any degree, but the right side \(\sum kq_i\) is a finite dimensional \(k\)-space and only contains polynomials of finite degree, which is impossible. Therefore, \(d=0\), and we know that \(q_1=q_2=\dots =q_n=0\).

After having this basic exact sequence, we will examine how to specifically calculate the module structure of \(V_A\). Note that \(tI-A\) is a matrix over a PID, so there exist invertible matrices \(P,Q\in M_n(R)\) such that \[P(tI-A)Q=D={\rm diag}(d_1,\dots,d_r,0,\dots,0)\] where \(d_1|\dots|d_r\), and \({\rm diag}\) denotes a diagonal matrix with these elements on the diagonal and \(0\) elsewhere. Then we have the following commutative diagram Here we need the following simple lemma

Now, since \(P,Q\) are invertible, \(Q^{-1},P\) obviously define an isomorphic mapping. From this lemma, we know that an isomorphism can be constructed from \(V_A\) to \(V'\), where \[V'\cong R^n/DR^n=R/(d_1)\oplus \dots \oplus R/(d_r) \oplus R^{n-r}.\] Note that \(V'\cong V_A\) is also a \(k\)-module isomorphism, and is a finite-dimensional \(k\)-vector space, but \(R\) is not a finite-dimensional \(k\)-vector space, so \(n=r\), \(d_1|d_2|\dots |d_n\) is a nonzero element in \(R\) such that \[V_A\cong V'\cong R/(d_1)\oplus \dots \oplus R/(d_n).\] Of course, it is not necessary to prove that \(V_A\) is isomorphic to the above form, only the structure theorem for finitely generated \(R\)-modules is needed. However, the above process gives an explicit way to calculate the standard form of \(V_A\) using the form of \(A\).

Eigenvectors and Root Subspaces

In this section, we will discuss how to actually obtain a transition matrix \(P\) such that \(P^{-1}AP=D\) is our standard form, or equivalently, \(AP=DP\). Let \(k\) be a field (e.g. an algebraically closed field like \(k=\mathbb{C}\)) such that all elementary divisors of \(\varphi\) are products of linear factors \((x-\lambda_i)^{k_i}\). We call the \(\lambda\)’s that appear in these elementary divisors the eigenvalues of \(\varphi\). By arranging the eigenvalues in order of their corresponding elementary divisors, we have \[V_\varphi\cong \bigoplus_{\lambda} \left(\bigoplus_k (R/(t-\lambda)^{k})^{n_k}\right).\] For each eigenvalue \(\lambda\), the subspace \(\bigoplus_k (R/(t-\lambda)^{k})^{n_k}\) corresponds to a subspace of \(V_\varphi\) under this isomorphism, which we call the root subspace with respect to \(\lambda\). It is given by \[R_\lambda:=\bigcup_k \ker(\varphi-\lambda)^k.\] The subspace \(\ker(\varphi-\lambda)\) is called the eigenspace with respect to \(\lambda\), denoted by \(V_\lambda\). The vectors in this subspace are called the eigenvectors of \(\varphi\), and they are obviously subspaces of the root subspace corresponding to the eigenvalue. Note that when we discussed the Jordan canonical form, we chose a \(k\)-basis for a submodule of the form \(R/((t-\lambda)^k)\), and we know that the projection of \(1\in R\) onto this submodule generates it. In other words, it has a basis \((t-\lambda)^{k-1},\dots,(t-\lambda),1\), and we need to arrange the basis in this order to ensure that the matrix of \(\varphi\) is the Jordan form described earlier. Now if we find the image of \(1\in R/((x-\lambda)^k)\) under the isomorphism to \(V_\varphi\), denoted by \(\alpha\), then the \(k\)-basis for this subspace can be written as \((\varphi-\lambda)^{k-1}\alpha, \dots, (\varphi-\lambda)\alpha, \alpha\).

If \(\varphi\) is diagonalizable, then all elementary factors are linear, and the root subspaces are equal to the characteristic subspaces. By finding the eigenvectors, we can obtain \(P\). For a general \(\varphi\), we need to find a basis for the root subspaces \(\ker(\varphi-\lambda)^k\). Here are some examples to illustrate this.

Invariants of Linear Maps

An invariant is either a quantity whose definition does not depend on the choice of basis, or a quantity that remains unchanged for any choice of basis (i.e. a similarity invariant). In this section, we will look at several classical invariants of linear maps.

Determinant

Consider an \(n\)-dimensional \(k\)-vector space \(V\) and a linear map \(\varphi:V\to V\). We consider an \(n\)-linear alternating function on \(V\) \[D(v_1,v_2,\dots,v_n):V\times V\times\dots \times V\to k.\] Here, \(n\)-linear means that \(D\) is linear in each variable \(v_i\), i.e. when fixing all other elements, \[v_i\mapsto D(v_1,\dots, v_i,\dots,v_n): V\to k\] is a \(k\)-linear map. Alternating means that if two vectors are the same, e.g. \(v_i=v_j=v\), then the value of the function is \(0\). \[D(v_1,\dots,v,\dots,v,\dots,v_n)=0.\] As a consequence, this implies that when we swap the positions of two vectors \(v_i,v_j\), the value of the function becomes the negative of its original value \[D(v_1,\dots,v_i,\dots,v_j,\dots,v_n)=-D(v_1,\dots,v_j,\dots,v_i,\dots,v_n).\] This is because \(D(\dots,v_i+v_j,\dots,v_i+v_j,\dots)=0\), and using the \(n\)-linear expansion, we can obtain the above consequence. Now, we may ask, with all these strange conditions, can such a function even exist? We consider introducing a basis \(e_1,\dots,e_n\) for \(V\), and consider the decomposition of \(v_i\) in terms of this basis \[v_i=\sum a_{ji}e_j.\] Then, by \(n\)-linearity, we have \[\begin{aligned} D(v_1,\dots)&=\sum_{j_1} a_{j_11}D(e_{j_1},\dots)\\ &=\sum_{j_1}\sum_{j_2} a_{j_11}a_{j_22}D(e_{j_1},e_{j_2},\dots)\\ &=\dots\\ &=\sum_{j_1,\dots,j_n} a_{j_11}\dots a_{j_nn} D(e_{j_1},\dots,e_{j_n}) \end{aligned}\] Since \(D(e_{j_1},\dots,e_{j_n})\) requires no repeated elements in order to be non-zero, we only need to consider the case where \(k\mapsto j_k\) forms a permutation of \(\{1,\dots,n\}\). Let us denote this permutation as \(\sigma\). In this case, the permutation \(\sigma\) can be decomposed into a product of transpositions, and each transposition produces a negative sign for \(D\). Therefore, \[D(e_{\sigma(1)},\dots,e_{\sigma(n)})={\rm sgn}(\sigma)D(e_1,\dots, e_n)\] Thus, \[D(v_1,\dots,v_n)=\left(\sum_{\sigma\in S_n} {\rm sgn}(\sigma) a_{\sigma(1)1}\dots a_{\sigma(n)n} \right) D(e_1,\dots,e_n).\] It is easy to verify that the above expression defines a function that satisfies \(n\)-linearity and alternativity. Therefore, the desired function \(D\) exists. However, its definition seems to depend on the choice of the value of \(D(e_1,\dots,e_n)\) and a basis for \(V\). In order to avoid the meaningless zero function, we choose \(D(e_1,\dots,e_n)\neq 0\). For any mapping \(\varphi\), we consider \[\det(\varphi):=\frac{D(\varphi(e_1),\dots,\varphi(e_n))}{D(e_1,\dots,e_n)}\] which is called the determinant of \(\varphi\). If we write the matrix decomposition as \(\varphi(e_i)=\sum a_{ji}e_j\), according to the above formula, we know that this definition does not depend on the choice of the value of \(D(e_1,\dots,e_n)\) (as long as it is non-zero). Therefore, we can write the definition of the determinant for a matrix \(A\) as \[\det A = \sum_{\sigma\in S_n} {\rm sgn}(\sigma) a_{\sigma(1)1}\dots a_{\sigma(n)n}.\] This is equivalent to assuming that the value of \(D(\alpha_1,\dots,\alpha_n)\), where \(\alpha_i\) are the columns of \(A\), is equal to \(1\) when \(D(e_1,\dots,e_n)=1\). Interestingly, the definition of the determinant for \(\varphi\) also does not depend on the choice of the basis \(e_1, \dots, e_n\)! To prove this, we only need to show that similar matrices have the same determinant. This is because the determinant is a multiplicative homomorphism:

Tensor product

Let \(M\) and \(N\) be a right \(A\)-module and a left \(A\)-module, respectively. We can define an abelian group \(M\otimes_A N\), where the elements are generated by symbols of the form \(m\otimes n\). The zero element is \(0\otimes 0\), and it satisfies the following three constraints:

1. (Coefficient balance) \((ma)\otimes n = m\otimes (an)\),

2. (Left linearity) \((m+m')\otimes n = m\otimes n + m'\otimes n\),

3. (Right linearity) \(m\otimes (n+n') = m\otimes n+ m\otimes n'\).

That is, it is required that the symbol \(\otimes\) has bilinearity, and the elements in \(A\) can freely pass through this symbol. Strictly speaking, this definition means that \(M\otimes_A N\) is a free \(\mathbb{Z}\)-module generated by all symbols \(m\otimes n\), modulo all relations generated by elements such as \((ma)\otimes n - m\otimes (an), (m+m')\otimes n-m\otimes n-m'\otimes n\), etc. When we do not write out \(A\), either the context is clear about which base ring is taking the tensor product, or we are taking the tensor product over \(A=\mathbb{Z}\). Since any module can be viewed as a bi-module over \(\mathbb{Z}\), \(\otimes_\mathbb{Z}\) can always be defined.

Although in general, the \(M\otimes_A N\) we define is just an Abelian group, similar to \({\rm Hom}\), when either \(M\) or \(N\) has a bimodule structure, we can give \(M\otimes_A N\) a module structure. Let’s give an example of how \({}_SM_R\otimes_R {}_RN\) has a left \(S\)-module structure. This is because we can define, for \(s\in S\), \[s(m\otimes n):= (sm)\otimes n.\]

Similarly, there are four possible cases, which we list in the following table:

According to the definition, \(M\otimes N=F/I\), where \[F=\bigoplus_{(m,n)\in M\times N}\mathbb{Z}(m\otimes n)\] is the free module generated by all abstract symbols \(m\otimes n\), and \(I\) is the submodule generated by all bilinear relations, \[I=\langle (m+m')\otimes n - m\otimes n - m'\otimes n, m\otimes (n+n')-m\otimes n - m\otimes n'\rangle_{m,n}.\] Given a bilinear map \(B:M\times N\to P\), we can define a \(\mathbb{Z}\)-linear map \[f\in {\rm Hom}_\mathbb{Z}(F, P) = \prod_{M\times N} {\rm Hom}(\mathbb{Z}(m\otimes n), P)\] that satisfies \(m\otimes n \mapsto B(m,n)\) uniquely. Its existence is guaranteed by the property of free modules. Since \(B\) is bilinear, it is obvious that \(f(I)=0\) (because \(f\) is \(0\) on all generators of \(I\), we have \(I\subset \ker f\)), so we can make a quotient map \(\overline{f}:F/I\to P: a+I\mapsto f(a)\), which is the \(B':M\otimes N\to P\) we need. The second part of the proposition is similar, and only requires minor modifications.

Dual Space

For an \(A\)-module \(M\), we can define a dual module \(M^* := {\rm Hom}_A(M,A)\). Its module structure is given by the bi-module structure of \(A\), i.e. if \(M\) is a left \(A\)-module, then \(M^*\) is a right \(A\)-module, and vice versa. In the case where \(A\) is a commutative ring, or a field, we do not need to distinguish between left and right modules, and \(M^*\) is naturally an \(A\)-module.

In the simple case of a \(k\)-vector space \(V\), \(V^*={\rm Hom}_k(V,k)\) is called the dual space of \(V\). It can be understood as the vector space of all linear functions \(f:V\to k\) on \(V\). The interesting thing about the dual space is that it is a contravariant functor.

Dual basis

If \(M\) has a basis, i.e. \(M\cong A^{(I)}\) is a free module, then its dual module is \({\rm Hom}_A(A^{(I)},A)={\rm Hom}_A(A,A)^I=A^I\). The latter is usually a larger module than \(A^{(I)}\), but if \(I\) is finite, then \(A^{(I)}\) and \(A^I\) are isomorphic. In the case of vector spaces, this shows that the dual space \(V^*\) of a finite-dimensional vector space \(V\) has the same dimension as \(V\). However, this isomorphism is not canonical, i.e. we cannot give this isomorphism without specifying a basis, and it depends on the choice of basis, it is not a natural isomorphism. Nevertheless, we can still discuss the concept of a dual basis corresponding to a given basis.

Let \(V\) be generated by a basis \(\{b_1,\dots,b_n\}\). Then this basis is equivalent to an isomorphism \(\varphi:k^n\to V\), which maps the standard basis \(\{e_i\}\) of \(k^n\) to \(\varphi(e_i) = b_i\). Taking the dual functor of this mapping, we obtain \[k^n \cong (k^n)^*\xleftarrow{\varphi^*} V^*\] By functoriality, \(\varphi^*\) is also an isomorphism. If we reverse the direction of \(\varphi^*\), we get an isomorphism \(k^n\cong (k^n)^*\xrightarrow{(\varphi^*)^{-1}} V^*\), which gives a basis for \(V^*\), called the dual basis of \(\{b_i\}\) and denoted by \(\{b_i^*\}\).

Specifically, \(e_i^*\) is defined such that its image under \(\varphi^*\) is the function on \(k^n\) that takes the \(i\)th coordinate, i.e. \(e_i^*:k^n\to k\). This satisfies \[b_i^*\circ \varphi = e_i^*\] Substituting \(e_j\) gives \[b_i^*(b_j) = e_i^*(e_j) = \delta_{ij}\] Here, \(\delta_{ij}=1_{i=j}\) is a symbol that equals \(1\) when \(i=j\) and \(0\) otherwise. This last line is also commonly used as an equivalent definition of the dual basis, since it can be linearly extended to all vectors by satisfying \(b_i^*\circ \varphi = e_i^*\) for all \(e_j\in k^n\).

Matrix Representation of Dual Linear Mapping: Transpose

Let \(f:V\to W\) be a linear mapping between finite-dimensional vector spaces. After choosing bases \(v_i\) and \(w_i\) for \(V\) and \(W\), respectively, we can represent \(f\) as a matrix \(A=(a_{ij})\) such that \(f(v_j)=\sum_i a_{ij}w_i\). Then, what is the matrix representation \(B=(b_{ij})\) of the corresponding dual mapping \(f^*:V^*\xleftarrow{} W^*\) under the dual bases \(v_i^*\) and \(w_i^*\)? We can calculate \[\sum_{i'} b_{i'j} v_{i'}^* = f^*(w_j^*) = w_j^*\circ f,\] and substituting \(v_i\) gives \[b_{ij} = w_j^*(f(v_i)) = w_j^*\sum_{j'} a_{j'i}w_{j'} = a_{ji}.\] This matrix is actually obtained by flipping all elements of \(A\) along the main diagonal, i.e. rows become columns and columns become rows. This operation is called the transpose of \(A\), denoted as \(A^T\). Therefore, we have the following corollary:

It is worth noting that the above reasoning does not require \(V\) and \(W\) to have the same dimension, and the transpose of a matrix can be applied to matrices of any shape.

Double Dual

Although \(V\) and \(V^*\) are not naturally isomorphic when the vector space is finite-dimensional, it is remarkable that \(V\) and \(V^{**}\) are naturally isomorphic.

If \(V\) is not finite-dimensional, \(V^{**}\) is usually very large, but we still have the natural monomorphism \(\mathrm{ev}:V\to V^{**}\) mentioned above.

Field Extensions and Galois Theory

---

1. Most books only write this definition from the beginning, which can be difficult for beginners. They may think that a group is just a set with an operation that satisfies some definition without knowing why. It takes them a long time to realize that groups actually represent symmetries.↩︎

2. It is also denoted as \(C_n\) or \(\mathbb{Z}/n\mathbb{Z}\).↩︎

3. We will mainly discuss finite groups.↩︎

4. Strictly speaking, \(D_3\) is isomorphic to a subgroup of \(D_6\)↩︎

5. A relation \(\sim\) is called an equivalence relation if it satisfies reflexivity \(a \sim a\), symmetry \(a \sim b \Leftrightarrow b \sim a\), and transitivity \(a \sim b, b \sim c \Rightarrow a \sim c\).↩︎

6. Right cosets can also be defined. However, for convenience, this book uses left cosets.↩︎

7. i.e. elements that commute with all other elements↩︎

8. Some books also use \(S_X\)↩︎

9. It is said that Frobenius discovered this result before Burnside.↩︎

10. For \(S\subset G\), we use the notation \(C_G(S)\) to represent \(\{g\in G|gs=sg,\forall s\in S\}\), which is called the centralizer of \(S\).↩︎

11. We can also define the right regular representation \[\begin{aligned} \alpha: G &\to {\rm Sym}(G)\\ g &\mapsto (a\mapsto ag^{-1}) \end{aligned}\]↩︎

12. It is called induced representation because it is actually \({\rm Ind}_H^G V_0=\bigoplus_{g\in G/H}gV_0\), where \(V_0\) is the trivial one-dimensional representation of \(H\).↩︎