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 , with the number of 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 , will bring the circle back to its original state. Reflecting an (equilateral) triangle about a symmetry axis, or rotating it by 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 is a rotation, while is an axis symmetry.
Essential Properties of Symmetry
We now use mathematical notation to write our previous discussion. We first have an object that may have some symmetry, which is some transformations acting on to keep it unchanged, that is, A natural principle is that every object has a type of symmetry, which is doing nothing. This do-nothing transformation is denoted as 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 (In the following, we will omit the composition symbol and write it as directly.) This simple equation shows how to "create" new symmetries using two symmetries: the composition of them must still be a symmetry of ! 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, , which is, in fact, a rotation of 240 degrees. Applying it three times is, in fact, doing nothing. Let’s use to represent the transformation of rotating (counterclockwise) 120 degrees. We have found that , which is the identity mapping, that is, 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, is not necessarily true. Symmetry also has another essential property. That is, every type of symmetry can be reversed! That is, for any symmetry , there is a corresponding inverse symmetry, denoted as , called the inverse of , such that . The inverse is a mutual relationship, you are my inverse, and I am also your inverse, so it must also satisfy . For example, the reverse operation of is rotating 120 degrees clockwise. This is, in fact, the same as , which can be seen by simultaneously composing both sides of the equation with : If we use to represent the set of all symmetry transformations on , the above discussion can be summarized as follows:
.
there exists an inverse for , such that
In fact, we call such a set a group, namely the symmetric group of .
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 . There are also two different rotations (one rotates 120 degrees counterclockwise, and the other rotates 120 degrees clockwise), and a symmetry 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 from to . Don’t forget, as a symmetry, needs to have an inverse, so must be a bijection. How many such are there? We only need to determine the values of . 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 a symmetry of the triangle? Indeed it is! We will use the following notation to represent the mapping that maps 1 to , 2 to , and 3 to . It is easy to see that Don’t forget what we said, symmetric transformations can be composed. Let’s try to compose and and see what happens. Calculate and give the result as
Interestingly, this composition did not produce anything new. is another type of symmetry, a reflection that keeps vertex 2 fixed. It is worth noting that , 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}.) 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 , called the dihedral group. The term dihedral group actually includes a whole series of groups , where refers to the group of all symmetries acting on a regular n-gon. (Note: Some books use to refer to what we call 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 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 , called the n-permutation group. The elements in it are called permutations. It is easy to see that . Permutation groups are of fundamental importance, so it is important to introduce simple and convenient notation for them. We still use to represent a permutation. In particular, we call a permutation with the following shape a cycle: We denote it as . There can be cycles with length less than n, such as 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 to , to , and so on until it maps some back to , then we have found a cycle . Starting from an element not yet included in any cycle, we let act on it repeatedly until it cycles, obtaining another cycle , and so on. Eventually, we exhaust all elements of the permutation and obtain 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: Simply by observing that , .
Exercise 1.1. Compute and write it as a product of disjoint cycles.
Exercise 1.2. Permutation:
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 , denoted as . This set satisfies the following properties:
.
.
Multiplication is associative, .
there exists an inverse such that .
In fact, when we abstractly consider a group, we can see that its operation structure has nothing to do with , 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:
Definition 1.1. A group is a set with an associated binary operation called multiplication, satisfying:
There exists an element (called the identity element) such that for any element , we have .
For any , there exists an element (called the inverse of ) such that .
Multiplication is associative, meaning that for any , we have .
In particular, if this operation also satisfies the commutative law, , it is called an Abelian group.
Exercise 1.3. Verify that in a group, the identity element is unique. The inverse of an element is also unique.
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 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 and that we have already introduced, there are some simple groups. The simplest example of a group is probably , 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 forms a group under addition (since it is closed under addition).
If we take all the rotations in , , 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 , calling it the th cyclic group, which is an Abelian group.
Regarding cyclic groups, there is actually another arithmetic description: all integers are divided into different residue classes according to the modulus , which are divided into classes with remainders . Addition can be performed between residue classes, for example, in modulus , . In this way, these different residue classes form a group under addition, which seems different from the previous because one is a rotation transformation and the other is a residue class . However, it can be seen that these two groups have no essential difference in structure, that is, if we identify residue class with , any group operation on both sides is the same. This means that under a correspondence 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.
Exercise 1.4. Consider all th roots of unity and verify that they form a group under the usual complex multiplication, that is, verify that they satisfy the definition of a group. Is this group isomorphic to ?
In this chapter, we will explore the basic structure of groups using a simple approach.
Structural Information on Elements
Order of Elements
Let . If there exists a positive integer such that , then we say that is of finite order and we call the smallest such positive integer the order of . Otherwise, we say that is of infinite order. For a finite group , for any element , we can keep multiplying it to get the sequence . Since is finite, this sequence will eventually repeat. Suppose , then we have . This means that every element in a finite group is of finite order.
Exercise 1.5. Let be an -order element in and . Prove that is a multiple of .
Proposition 1.1. Let be an -order element in a group . Then the order of is , where denotes the greatest common divisor of and .
Proof. First, from , we know that the order of is . And if , then must be a multiple of , which means must be a multiple of . This shows that the order of is exactly . ◻
In an Abelian group, if the orders of and are known, then the order of is constrained.
Exercise 1.6. Let be an Abelian group, and let have orders and respectively. Then the order of is a factor of .
Exercise 1.7 (). In the above exercise, if and are relatively prime, prove that the order of is .
It is worth noting that for non-Abelian groups, knowing only the orders of and does not provide any information about the order of . It can be proven that there exist groups where the order of can take on any given positive integer. As an example, in , let , then is of order five.
Exercise 1.8 (). Prove that if a group only has elements of order and , then it is an Abelian group.
Exercise 1.9 (). Let be a group of even order, then the equation has an even number of solutions. Hence, there must be elements of order two in the group .
Subgroups and Quotient Structures
It is not difficult to see that , the symmetry group of a regular hexagon, also contains all the symmetries of an equilateral triangle! For example, the rotation of 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 is a subgroup of . The history of mathematics tells us that studying the substructures of a structure is important: we make the following definition
Definition 1.2. Let be a group, and let be a subset. If satisfies the defining properties of a group under the multiplication operation of , then is called a subgroup of . We denote this as .
We have many examples of subgroups, for example, the additive group of all even numbers is a subgroup of . Another example is has subgroups and , which are actually and .
Example 1.1. forms a subgroup of , called the Klein four-group, sometimes denoted as or . This group is abelian, but is not isomorphic to the abelian group of the same order, .
Exercise 1.10. Prove that the intersection of (any) subgroups is still a subgroup.
Cosets and Lagrange’s Theorem
Let be a group and let be a subgroup. We can define an equivalence relation on as follows: It can be easily verified that this indeed defines an equivalence relation, and according to this relation, the group is partitioned into disjoint equivalence classes. It can be observed that the set of all elements equivalent to is , since . Thus, all the equivalence classes are of the form , and they all have the same size, which is . We call such subsets of cosets of , and we refer to them as left cosets. We denote the number of cosets, or the index of the subgroup , by . We have Since the different cosets are disjoint, we have obtained
Theorem 1.1 (Lagrange’s Theorem). Let be a subgroup of the group . Then,
By continuously applying the coset decomposition, we can obtain
Exercise 1.11 (). Let . Then we have
This theorem also shows that the order of a subgroup must be a factor of . For example, using Lagrange’s theorem, we can see that a group of order cannot have a subgroup of order .
Example 1.2. For the group and its subgroup , we have the following coset decomposition: In this case, .
Exercise 1.12. Let . Prove that , and hence .
Theorem 1.2. Let be an -order element in a finite group . Then is a factor of .
Proof. Since is an -order element, it is easy to verify that forms an -order subgroup of . Therefore, by Lagrange’s theorem, we know that must be a factor of . ◻
Quotient Groups and Normal Subgroups
Just like how a subspace can be constructed from a vector space, groups also have quotient structures.
Given , we try to view the set of cosets as a group, and the desired group operation is defined as: Unfortunately, for some subgroups , this equation does not hold. In other words, not all subgroups can be used to construct the quotient group . We reason as follows: , and for all , is equivalent to for all . Therefore, in order to construct the quotient group , the subgroup must satisfy the condition: , which leads to the following definition:
Definition 1.3. Let , if then is a normal subgroup of , denoted as . If a group has no other normal subgroups except for and , it is called a simple group.
Example 1.3. If is an Abelian group, then any subgroup of is a normal subgroup.
Example 1.4. We have , which can be verified by showing . It is easy to see that is a subgroup of , but it is not a normal subgroup of because .
Example 1.5. We have . This point can be immediately obtained after we talk about the concept of conjugation in permutation groups.
It is worth noting that normal subgroups do not have transitivity, that is, does not imply . A counterexample will be given in the later study.
Exercise 1.13. Let and . Prove that .
Exercise 1.14. Proof: is equivalent to saying that for any , .
Exercise 1.15 (). Assume and . Prove that the elements of and commute with each other. That is, for any and , .
Exercise 1.16 (). Let and . Prove that .
Exercise 1.17 (). Find all finite simple groups.
Product of Subgroups
Let . We define the set Under the operation defined on the larger group , can this set form a group? The answer is not always. However, this is true when at least one of or is a normal subgroup. Without loss of generality, let . We calculate The associativity of the group is inherited from the associativity of the larger group, so in this case, forms a subgroup.
In addition, even if neither nor is a normal subgroup, we can still calculate the number of elements in the set by using the method of coset decomposition.
Proposition 1.2. Let , then
Exercise 1.18 (). Let . Prove that In particular, if and are coprime, prove that the equality must hold and .
Exercise 1.19 (). Let be subsets (note that it is not said that they are subgroups). If , prove that .
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.
Definition 1.4 (Group Homomorphism). Let be groups, and be a mapping. If then is called a group homomorphism or group mapping, and is simply called a homomorphism. If is an injection, it is called a monomorphism. If is a surjection, it is called an epimorphism. If is both a monomorphism and an epimorphism, it is called an isomorphism, and and are called isomorphic, denoted by .
It is worth noting that in the equation , the multiplication operation used for is from the group , while the multiplication operation used for is from the group .
Example 1.6. As in Chapter 1, by numbering the vertices of a triangle, we find that in fact . However, for , is not the same as .
Example 1.7. A group is isomorphic to itself. This can be achieved by taking . Interestingly, a group can have isomorphisms other than the identity map, such as the map . This is an isomorphism, but it is different from the identity map. We call these (including ) the automorphisms of . In fact, the existence of such (non-trivial) isomorphisms shows that the structure of the group itself has a certain symmetry, and all automorphisms of , which are all the symmetries acting on , also form a group, called the automorphism group of , denoted by .
Exercise 1.20. Verify that a homomorphism must map in to in , and map to , i.e. and .
Exercise 1.21. Verify that has a subgroup of order , and prove that the quotient group of this subgroup is isomorphic to .
Exercise 1.22. Let be an -order element, prove that must be a finite-order element, and its order is a factor of .
Definition 1.5 (Kernel and Image). Let be a group homomorphism. We define the set as the kernel of , and the set as the image of .
It is worth noting that and are subgroups of and , respectively, and in fact .
Exercise 1.24. Prove that
.
Find all groups with order . Including the trivial group with only one element, there are a total of groups with order not exceeding . (Isomorphic groups are considered the same)
Simple, important and typical group homomorphisms
Monomorphism
The simplest group homomorphism should belong to monomorphism. A monomorphism essentially maps to a subgroup , and is isomorphic to . In other words, a monomorphism is a way to "insert" into in an isomorphic way.
Example 1.8. Consider the monomorphism of groups It is easy to see that this homomorphism is completely determined by the value of , since and . Since is a 3-order element, must be a 1-order or 3-order element. The 3-order elements in are only and . Therefore, we know that can only take . Since we only consider monomorphisms, there are only two possible choices left: or .
If , then we have , and the entire group is mapped to . If we choose , then we have , and the entire group . We know that is a subgroup of isomorphic to , but there are two different ways to embed into . However, in either case, this monomorphism establishes an isomorphism between and . Although there is only one subgroup isomorphic to in , there are multiple ways to embed into because there exists an automorphism from to mapping to . In other words, this phenomenon occurs because of the symmetry inherent in itself. 
Projection and Homomorphism Decomposition
Another simple and important mapping is projection. As we have mentioned, for a normal subgroup of a group , we can construct the quotient group . We can consider a natural mapping that maps an element in to the coset in that contains : This mapping is obviously a homomorphism, since . It is also a surjective homomorphism. What is its kernel? Recall that the identity element in is , which is the coset containing the identity element in . Therefore, , and we conclude that .
The importance and fundamentality of homomorphisms lies in considering the kernel of any homomorphism . One thing worth noting is that is equivalent to saying . In other words, if we take the quotient group of by (also known as the coset decomposition), every element in the coset is mapped to the same element by , and different cosets are mapped to different elements (since if two cosets and are mapped to the same element, then ). Since all elements in are mapped to the same element (which seems like a waste), we can define a new mapping that considers as an element in the quotient group and maps it to .
In other words, we find that any homomorphism with kernel can be decomposed into the composition of two mappings:
This diagram means that we can map to in two steps: . The first step is to map to the coset it belongs to (i.e. the natural projection from to ), and the second step is to map to . 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: , which first maps to the subgroup of , and then maps to through the trivial injective mapping.
Thus, the second step is a homomorphism and a bijection, and therefore an isomorphism. From this, we obtain the following important theorem:
Theorem 1.3 (Fundamental Homomorphism Theorem). If is a homomorphism, then , , and there exists an isomorphism
Proof. As above, we construct a mapping It is easy to verify that this mapping is well-defined, since whenever . Now we prove that this is a homomorphism: The first equality holds because is normal. is injective, since . Moreover, is surjective, so is an isomorphism. ◻
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.
Theorem 1.4 (Second Isomorphism Theorem). Let and . Then and , and
Proof. Since and , it is easy to see that . For any and , we have Therefore, . Now, we construct a mapping We first prove that this mapping is a homomorphism. Since , we have This is clearly a surjective homomorphism. Now, we calculate . Let , then Hence, . By the first isomorphism theorem, we have ◻
The following corresponding theorem is fundamental, it describes the correspondence between subgroups of and subgroups of that contain .
Theorem 1.5 (Corresponding Theorem). Let , and let be the natural projection. Then there exists a one-to-one correspondence between all subgroups of that contain and all subgroups of : This maps to all coset sets of the form . The inverse map is , where is a subgroup of .
Proof.
Note that the image of is , which is the image of a homomorphism, and therefore is a subgroup of . Similarly, for any subgroup , the preimage is also a subgroup.
Now we only need to verify that these two mappings are inverse mappings, i.e. and . The latter is obvious since is surjective. For the former, suppose there is a coset decomposition , then
◻
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 can be described in various ways, such as the rotation transformation group of a regular -gon, or the additive group of residue classes modulo . 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 , and by repeatedly taking inverses and multiplying , we can obtain all elements in the group . To make this clearer:
Definition 1.6. Let be a group, and be a subset of . The intersection of all subgroups of that contain , also known as the smallest subgroup containing , is called the subgroup generated by , denoted by . If , then is called a group generated by , and is called a set of generators for . If a group can be generated by a single element, i.e. there exists such that , then it is called a cyclic group.
According to this definition, in addition to the finite cyclic group , there can be infinite cyclic groups, which are essentially .
Therefore, the cyclic group can be imagined as a group generated by the abstract letter , satisfying the relation . This method of describing a group using generators and constraints is called group presentation. In this example, we write it as
Example 1.9. Similarly, we can imagine that the group can be abstractly described as a group generated by the abstract letters and , satisfying the constraints and . Let’s try to list a series of elements generated by these two letters: In the special case of the group , any element generated by abstract letters, such as , can be written in the above form, i.e. in the form of . This is because We write this as (The condition can be simplified to ). This can be easily generalized to the definition of This definition is abstract, it does not involve symmetry, but it clearly determines the structure of the group!
Exercise 1.25. Continuing with the example, please calculate
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 -order cyclic group have? The answer to this question is obvious. Let be a generator, then is a generator if and only if is coprime to . In other words, there are a total of generators, where represents the number of numbers coprime to in the range of to , also known as the Euler’s totient function in number theory. There is an interesting identity about this Euler’s function: where means divides , and the summation symbol represents the sum of all positive divisors of . This identity can be derived from the following observation: for each , there is only one -order subgroup in the cyclic group , and this subgroup has generators. Every element is exactly a generator of some .
There is an important proposition that characterizes the properties of cyclic groups:
Theorem 1.6. Let be a finite group. If for any factor of , there is at most one -order subgroup in , then is a cyclic group. The converse is also true.
Proof. Note that any has a cyclic subgroup generated by it. By assumption, there is at most one subgroup of this order. For , if there is a cyclic subgroup of order , then let its set of generators be denoted as , otherwise, let be the empty set. Since any is a generator of some cyclic group of order , we have and a cyclic group of order has generators, thus We find that the equality holds, so for each it has exactly one cyclic subgroup of order , which is also true for , so it is a cyclic group. ◻
Exercise 1.26 (). (For those who have not heard of fields, you can skip this) Prove that any finite subgroup of the multiplicative group of a field is cyclic.
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.
Proposition 1.3. Every can be written as a product of disjoint cycles : Moreover, this decomposition is unique up to the order of the cycles.
Proof. Assume that has two disjoint cycle decompositions If moves , then will appear in one of the cycles in the other decomposition, let’s say . By repeatedly applying to , we get , It is clear that the first cycles in both decompositions must be equal. Multiplying both equations by the inverse of this cycle, we get a decomposition with fewer cycles. Repeating this process, we can easily prove the proposition. ◻
So each permutation has a unique cycle structure, for example and have the same cycle structure, only the numbers are different. We say their cycle structure is . Similarly, if the cycle decomposition of has cycles of length , we say its cycle structure is .
Having the same cycle structure is like matrices having exactly the same Jordan blocks, and can be achieved by "change of basis", for example where . This phenomenon is called conjugation:
Definition 1.7. For , if there exists such that we say and are conjugate in . It can be verified that conjugation is an equivalence relation. Elements that are only conjugate to themselves are called central elements, and all central elements are denoted by or , and are called the center of the group .
Exercise 1.27. Prove that the number of conjugacy classes of a group is equal to if and only if is an Abelian group.
Exercise 1.28. Let be a fixed element. Verify that the conjugation map is an automorphism of the group .
Exercise 1.29 (). Continuing from the previous exercise, we have a mapping from to : Verify that this is also a group homomorphism. Prove that , and thus conclude that is a normal subgroup of .
Let , and call it the inner automorphism group of . By the fundamental homomorphism theorem, we have:
As an example for everyone to see, we prove a useful proposition.
Proposition 1.4. If is a cyclic group, then is an Abelian group.
Proof. Let be a generator of the cyclic group in , and we can construct a coset decomposition of with respect to as follows: Thus, every element can be written as , and it is obvious that . ◻
Exercise 1.30 (). Prove that if is a cyclic group, then is an Abelian group.
Exercise 1.31 (). Let , where is a prime number. Prove that is an Abelian group.
Exercise 1.32 (). Let , and let . Prove that if then is an Abelian group.
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 .
Exercise 1.33 (). Find the number of conjugacy classes in .
Exercise 1.34 (). Let be a prime number. Find the number of conjugacy classes in .
It is easy to see that if a subgroup of a group is a normal subgroup, then 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.
Exercise 1.35. Think carefully about the above statement and prove that
Exercise 1.36 (). Observe Explain why normal subgroups do not have transitivity.
Exercise 1.37 (). We call a characteristic subgroup of if every automorphism of maps elements of to elements of . Prove that if and is a characteristic subgroup of , then . In other words, the characteristic subgroup of a normal subgroup is still a normal subgroup.
Exercise 1.38 (). Let be the smallest prime factor of . Prove that if there exists a -subgroup , then .
Parity of Permutations
Permutations can be classified as odd or even, denoted by the symbol : odd permutations are , while even permutations are . The symbol 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: Any permutation can be decomposed into a product of transpositions, as any cycle can be decomposed into a product of transpositions, i.e. . 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 is an odd permutation, while transpositions of odd length, such as and , are even permutations.
We will give another definition, and we will explain how this definition is derived. We know that every permutation has a unique disjoint cycle decomposition. If we consider the fixed element as a cycle of length , denoted as , we can use to represent the number of cycles in the disjoint cycle decomposition of the permutation, including the cycles of length . Then we define Firstly, for the identity permutation, , so . For the cycle , , so . And is actually the sum of the length of each cycle minus , 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 , we have .
Lemma 1.1. For any transposition , we have .
Proof. If and any of the disjoint cycle decompositions of are not disjoint, the equation is obvious. Otherwise, if there is an intersecting element, it is easy to calculate that The length of increases by relative to , so the sign changes. If there are two intersecting elements, consider The sum of the lengths of the cycles decreases by , and the right side has one less than the left side. For the other case, The sum of the lengths of the cycles decreases by , and the right side has one less than the left side. Therefore, we immediately obtain the proposition. ◻
Theorem 1.7. is a homomorphism.
Proof. By Chapter 1, let be the decomposition of into transpositions. Then The kernel of the homomorphism is denoted as , called the -element alternating group, which is the group of all even permutations. As a corollary, .
Exercise 1.39. Determine the parity of the permutation and the permutation
◻
Exercise 1.40. Prove that the order of a permutation is equal to the least common multiple of the lengths of all the cycles in its disjoint cycle decomposition.
Exercise 1.41 (). Classify all elements in into conjugacy classes and find all its normal subgroups.
Exercise 1.42 (). Prove that has a subgroup isomorphic to .
Direct Product
We can construct new groups using old groups, and one very simple construction is the direct product. Let and be groups, and we want to give the Cartesian product the structure of a group. The simplest way to do this is to define the multiplication as component-wise multiplication, that is, This way, the identity element in the group is , and the inverse of is . We will denote this group as . If and are both abelian groups, this construction is sometimes denoted as the direct sum , with the group operation denoted by addition.
Exercise 1.43. Investigate the group (also denoted as ) and prove that it is isomorphic to
Exercise 1.44 (). Prove that In fact, for any odd number , we have
Exercise 1.45 (). Prove that when are coprime, we have
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: where the generator of is mapped to a unit rotation. This action can also be described as follows: interpreting the rotation of a regular -gon as a permutation on the set of vertices , we get a (mono)morphism: where the generator of is mapped to the cycle . To study the most general actions of a group, we consider a homomorphism from the group 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 by , which consists of all bijective mappings, and is called the symmetric group of . Then, we define an action of a group on a set as a homomorphism (not necessarily injective or surjective): This is also known as a permutation representation of the group , or simply a representation. In other words, becomes a transformation (permutation) on the set , which is bijective, i.e. . This transformation can act on an element to give . This notation is more rigorous, but it is too long. After defining the homomorphism , we can imagine as a set of "operators", and simply use to represent .
Let us first give some basic terminology for group actions. If 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 , the set is called the orbit of . It can be easily shown that if belong to the same orbit, i.e. there exists such that , then this is an equivalence relation, closely related to the fact that is a group. As a result, the elements in are partitioned into disjoint classes, i.e. the union of disjoint orbits. If has only one orbit, we say that the action is transitive, meaning that any can be mapped to any given by some element in .
Orbit Formula
Definition 2.1. Given a group acting on a set , we define to be the subgroup of that keeps fixed. This is called the stabilizer of .
Exercise 2.1 (). There is a stronger concept than transitivity, called doubly-transitive, which means that for any , there exists such that Prove: is doubly-transitive on if and only if for all , is transitive on .
Since is a subgroup, we can make a coset decomposition where each coset acts on in the same way, i.e. . Moreover, different cosets give different actions on , otherwise . We immediately obtain the following simple but fundamental orbit formula (for calculating the length of an orbit)
Theorem 2.1 (Orbit formula).
Since is partitioned into some orbits, we denote each orbit’s representative element as . It is obvious that we must have Do not underestimate this orbit formula, with it, we have a method to calculate the order of some symmetric groups, because .
Example 2.1. We calculate . Take a vertex of a regular -gon, since the action is transitive, . And there are only two transformations in that keep unchanged, the identity transformation and a reflection (axisymmetric) transformation. Therefore,
Exercise 2.2 (). Calculate the order of the symmetry group of a regular tetrahedron.
Example 2.2. Let , we calculate the number of elements in the following double coset set Consider the following action of on : It is easy to see that is the orbit of under this action. Therefore, by the orbit formula, We consider . Hence,
In addition, we can immediately obtain the following formula for calculating the number of orbits. For any subset of , we introduce the notation Then we have
Theorem 2.2 (Burnside). The number of orbits has the following formula
Exercise 2.3 (). If acts transitively on and , then there exists without a fixed point.
Exercise 2.4 (). Let be a group of order . Prove that if acts on a set , then
Kernel of Representation
We will find , which is generally important, because by the first isomorphism theorem, is isomorphic to a subgroup of the permutation group .
What is ? It is the set of all elements that fix every element, so If this action is transitive, then There is a natural relationship between and . The transformations that fix can also be used to fix by slightly modifying them. This only requires composing with , applying , and then composing with . In other words, we find that Similarly, we have Therefore, we find that Thus, when the action is transitive, we have This is a normal subgroup. This fact also suggests the following trivial proposition: for , we have
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 acts on itself by conjugation, i.e.
Exercise 2.5 (). Can we define the conjugation action as Why is this definition not valid?
The orbit of this action is the conjugacy class, it is easy to see that the kernel of the action . For , its stabilizer is denoted as , which is a subgroup of . We call the orbit equation in this case the class equation of the group . It is worth noting that some elements may have orbit length of , which means they are only conjugate to themselves, central elements, . If we let , where is a prime number, then we have It is easy to see that must be a multiple of . Therefore, in this case, must be a multiple of , which means . In other words, we have the following conclusion:
Proposition 2.1. If , then has a non-trivial center .
Exercise 2.6 (). If we denote the number of conjugacy classes of a group by , prove that
Exercise 2.7 (). With the notation as above, suppose is a non-Abelian group. Prove that
Exercise 2.8 (). Can the equality hold? Furthermore, prove that if is the smallest prime factor of , then
Regular Representation (Action)
The group acts (on the left) by multiplication on the group , i.e. This naturally views as a permutation on , . This is a faithful representation.
Exercise 2.9. Prove that this is a faithful and transitive action.
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.
Proposition 2.2. Let be a group of order . Then it must have a normal subgroup of index .
Proof. Consider the left regular action of the group Since this is a faithful representation, we can identify with . Then, each is a permutation on , and due to the existence of inverses in group multiplication, this permutation cannot fix any element in the group (.) Therefore, we can write as a product of some disjoint cycles of length greater than . Now, take to be an element of order in the group, which we know exists in groups of even order. Thus, decomposes into a product of disjoint transpositions, and is therefore an odd permutation. This proves that there is an odd permutation in , and thus all even permutations in form a normal subgroup of index . ◻
Corollary 2.1. Let , then a group of order is not a simple group.
Induced Representation (Action on Cosets)
Given a subgroup of a group , there is a (left) coset set , and can naturally act on . This is called the (left) induced representation. It is obviously transitive. Its kernel is and note that . Using this representation, we can obtain many powerful (actually simple) conclusions.
Example 2.3. Let be a proper subgroup of an infinite group with finite index, then must have a proper normal subgroup with finite index.
Proof. Consider the induced representation of on the coset : Since is finite, we have completed the proof of the proposition. ◻
Here is another typical application:
Proposition 2.3. Let be the smallest prime factor of . If and , then .
Proof. Consider the induced representation on the coset set . Since is isomorphic to a subgroup of , it must be that is a factor of . Now, since , we have which is a multiple of . Since is the smallest prime factor of , we know that is a multiple of or . If it is not , then , which is impossible. Therefore, ◻
Exercise 2.10 (). Let be a non-Abelian group of order greater than , and . Prove that .
Proof. Let be a prime factor of . Then, by the orbit-stabilizer theorem, we have that , where is the orbit of and is the stabilizer of . Since is divisible by , we have that divides . Since is prime, this implies that divides either or . If divides , then by Lagrange’s theorem, there exists an element of order in . If divides , then by the induction hypothesis, there exists an element of order in . In either case, we have that contains an element of order , as desired. ◻
Before we start looking at the proof, let’s understand the idea. The case of has already been done as an exercise, do you remember the method? Your method is probably to pair the elements in , pairing with , the second-order elements and are the same, so they cannot be paired. Finally, because the order of the group is a multiple of , the number of paired elements is also a multiple of , and we conclude that there are an even number of elements that satisfy . Since , 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 . 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 on the set of all ordered pairs . This is the action of the group on this set. So can be decomposed into a union of orbits. And the length of the orbit under this action is if and only if , that is, . From the orbit equation the orbit formula shows that the length of the orbit can only be or , and we immediately conclude that is a multiple of . Now, I think it is obvious how to generalize this proof.
Proof. Let , and let be a generator of the group . Consider the following action of the group on : Where is a mapping that maps to .
We need to verify that , which can be obtained from . Now, from the orbit equation We can conclude that is a multiple of , and since , we immediately know that there exists a -order element in the group , and there are at least of them. In fact, we can obtain a stronger conclusion: -order element count is a multiple of . ◻
Exercise 2.11 (). Let where is a prime number. Prove that .
Exercise 2.12 (). Let be an Abelian group of order . Prove that using the following hints. (By Cauchy’s theorem, has elements of order and . Hence, .)
Exercise 2.13 (). Let be a non-Abelian group of order . Prove that using the following hints. Hence, there are only two groups of order : and .
First prove that .
Prove that has exactly elements of order .
Consider the conjugation action of on the set , where are all elements of order . (You need to prove that this is an action on first.)
Prove that generates , and hence the above action is faithful. The first isomorphism theorem gives .
Conjugation on Subgroups
Let be a subgroup. It is easy to see that is also a subgroup. This is because the mapping is an automorphism, and when restricted to a subgroup, it remains an isomorphism, thus its image must be a group. We say that subgroups and are conjugate if . It is clear that can act on some of its subgroups by conjugation. A subgroup can have many conjugate subgroups, and the normal subgroups of are those that are invariant under the conjugation action of , meaning they are only conjugate to themselves. In this case, they form a conjugacy class on their own.
For , we use the notation to denote , which is called the normalizer of . It is easy to see that the stabilizer of is , and thus the size of the conjugacy class is
Exercise 2.14 (). Let . Prove that the number of non-normal subgroups of is a multiple of .
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 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 , using 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 and let act on this space in the following way:
.
It is easy to see that since all elements in can be represented in the form of , it is only necessary to define the actions of and on . It can be easily verified that the above definition indeed gives an action of on (it is necessary to verify that the actions of are trivial). Therefore, our problem is now equivalent to calculating the number of orbits in , denoted by . By Burnside’s theorem, Now let’s consider the size of . First, can be viewed as a subgroup of , and it actually acts on in the same way as the permutation with subscripts. Therefore, we can assume that has a disjoint cycle decomposition in : where are disjoint cycles with lengths . For example, , .
If fixes an , i.e. , we can obtain i.e. . From , it naturally follows that , thus . This means that in all components of the cycle , the corresponding positions must have the same color. Similarly, the same result can be obtained for all cycles, thus , note that when considering cycles, the identity cycle must be included.
Note that the cycle decomposition shape of elements in the same conjugacy class of is the same. In general, it is only necessary to find all conjugacy classes of and calculate their cycle decomposition. In this example, we can consider Note that , thus when is odd, all are conjugate, and like , they have cycles. When is even, it may be divided into two conjugacy classes and , which have and cycles, respectively, just like and .
For elements in , is a cycle of length when and are coprime. When their greatest common divisor , it is a product of cycles of length . Recall that in the section on cyclic groups, we mentioned that for factors of , the number of generators of the subgroup of order , , which are elements satisfying , is equal to the Euler’s totient function . Therefore, we can now derive the formula for :
Exercise 2.15 (). Assuming that on a necklace of length , only two colors are allowed and each color must use exactly beads. How many different coloring methods are there?
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.
Theorem 2.3 (Sylow). Let be a group with , where is a prime and . Then:
There exists a subgroup of order , called a Sylow- subgroup of .
Let denote the number of subgroups of of order , for . Then
All Sylow- subgroups are conjugate to each other, so .
It is worth noting that general -subgroups may not be conjugate to each other.
Proof. Let (without the requirement that and are coprime, i.e. is not necessarily maximal). We consider all -element subsets of , denoted by , with . Now we can consider the left action of on : We decompose into a union of orbits: with . Since , we can decompose which implies and . Note that must be a power of , and if and only if is of the form , where is a -element subgroup of and . Thus if and only if contains exactly one -element subgroup, which implies Hence
Now we only need to calculate the remainder of the left number . First, it is equal to , so it is equal to the coefficient of the th term of the expression . Considering this expression in the formal power series ring modulo , we have We conclude that the desired coefficient modulo is , and thus we obtain the desired proposition. Of course, this number can also be calculated by other methods, such as direct calculation, or considering the special case where is a cyclic group, in which case we know that . However, the left side of the equation is independent of the group and only depends on the order of the group, which directly gives the desired result.
Now we prove that all Sylow- subgroups are conjugate to each other. First, acts on all Sylow- subgroups by conjugation, and the order of each orbit must be coprime to . Let be a Sylow- subgroup of , and consider the conjugation action of on all Sylow- subgroups. Then is fixed by the action of if and only if . In this case, consider the projection . Since the order of the quotient group does not contain , and all elements of have order , we know that the image of this projection must be , which implies that . Therefore, . This shows that only is fixed by this conjugation action, and all other orbits have length a power of . However, under the conjugation action of , each orbit is not divisible by , so when each orbit is restricted to act on , there must be an orbit of length . We have already proved that only is fixed by the conjugation action, so there can only be one -orbit. ◻
Corollary 2.2. If , where and are coprime, and there exists a unique Sylow- subgroup, then this subgroup is a normal subgroup.
Corollary 2.3. If , where and are coprime, then is a factor of and has the form of .
Example 2.4. We will prove that a group of order must be cyclic. According to Sylow’s theorem, we can consider two Sylow subgroups and of orders and , respectively. We have and is a factor of . However, the only number that satisfies the congruence is . Similarly, we find that . Therefore, for all factors of , there is only one subgroup of order , which must be cyclic.
Exercise 2.16. Let be a group of order . Prove that it has a normal subgroup of order .
Exercise 2.17 (). Let be a Sylow- subgroup of . Prove that if or , then is a Sylow- subgroup of .
Exercise 2.18 (). Prove that if and is a Sylow- subgroup of , then there exists such that is a Sylow- subgroup of .
Exercise 2.19. Find all Sylow- subgroups and Sylow- subgroups of .
Exercise 2.20 (). Try to find all Sylow subgroups of .
As we have seen, Sylow’s theorem is often used in conjunction with conjugation, because there is a natural relationship between them: Sylow -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 where and are coprime, and calculate the possible number of Sylow -subgroups , which satisfies
If , then by Sylow’s theorem we know that .
If , consider each prime with and the minimum number of elements that each can contribute to . This may help to show that there cannot be so many Sylow subgroups.
If , consider the intersection of two Sylow subgroups. If , then (since ) and , so and .
Consider the conjugation action of on , and its kernel , which may be a non-trivial normal subgroup of .
Example 2.5. We prove that the group of order is not a simple group. Consider the number of -order subgroups of , denoted by . We have or . If , consider the conjugation action of on these four Sylow- subgroups: Since , cannot be injective. Moreover, by the transitivity of Sylow subgroups under the conjugation action of , we know that this action is non-trivial. Therefore, forms a non-trivial normal subgroup of .
There is another proof. If , consider . Since , we know that . But , so contains the group generated by and . Hence, is a non-trivial normal subgroup of .
Exercise 2.21 (). Prove that the group of order is not a simple group.
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.
Lemma 2.1. Let be a -subgroup acting on all Sylow -subgroups, then forms a single orbit
Proof. One side is obvious, we prove the other side. Suppose and is a -order element, then . Since , consider the projection of under Since is coprime to , its projection can only be the identity element, so . This is enough to prove the proposition. ◻
Proposition 2.4. Every -power order subgroup of is contained in some Sylow- subgroup.
Proof. Consider the action of by conjugation on all Sylow- subgroups of . The orbit lengths are either or multiples of . Since the number of Sylow- subgroups is , we know that there must be one that forms its own orbit, thus by Lemma, . ◻
Proposition 2.5. Let be a -subgroup. Then the number of Sylow- subgroups containing , , is .
Proof. Let act on all Sylow- subgroups, is equivalent to the orbit length of being . Since the number of all Sylow- subgroups is , we have ◻
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, cannot be generated by a finite number of elements. The simplest example of a finitely generated abelian group is the so-called -element free abelian group , which is generated by elements: . It can also be called a free -module: -modules and abelian groups are the same concept.
Let be an Abelian group that can be generated by a finite number of elements . Then we can define a surjective homomorphism as follows: According to the fundamental homomorphism theorem, we have . Therefore, our goal is to study what kind of subgroups has, which will allow us to determine all possible quotient groups.
Let’s first consider the simple case of . We know that the only subgroups of are and for . Therefore, all non-trivial subgroups of are isomorphic to .
For the case of , let be a subgroup. Consider and . We can think of and as subgroups of , so they must be and . This means we can find two elements in such that the first component of each element is divisible by and the second component is divisible by . So we can write . Now, note that and We will prove the following important result (essentially linear algebra) in Chapter 4:
Theorem 2.4. Subgroups of are necessarily free Abelian groups, isomorphic to with . In fact, if , then there exists a set of and a set of non-negative integers such that and
Corollary 2.4. All finitely generated Abelian groups are isomorphic to some
Corollary 2.5. All finite Abelian groups are direct sums of finite cyclic groups.
Semidirect Product
Semidirect product is an important concept commonly used in group theory. If , then we can construct the quotient group . One might wonder if holds? In most cases, this is not true. For example, consider the case of and , it is obvious that .
If can be naturally realized as a subgroup of , i.e. there exists such that the natural projection is an isomorphism, then we can assert a weaker proposition: is the semidirect product of and , i.e. . Let us explain this, we can reconstruct from and : for each , there exists an image in , so , which means , and this representation is unique. Since , the multiplication operation on can also be recovered from the conjugation action of on : This inspires us to define a group structure on the set from , , and the (conjugation action) homomorphism as follows: The identity element in the group is , and the inverse element is . It can be verified that this definition satisfies the associative law, so forms a group under the above multiplication, which we denote as , called the semidirect product of and .
Exercise 2.22 (). Verify the associative law in the above definition.
Example 2.6. has two possibilities depending on the choice of :
If is the trivial homomorphism, then .
If is the homomorphism that maps to the unique non-trivial automorphism where , then we have
Verify that , what is the homomorphism ? We give the following simple criterion:
Proposition 2.6. If , , , and , then where is the conjugation action of on .
Proof. From and , we can see that each element can be uniquely represented in the form of . Therefore, by the construction of the semidirect product, we know that we can define an obvious homomorphism which is obviously a surjective homomorphism. ◻
Exercise 2.23 (). Verify that implies .
It is worth noting that although there are many possible choices for in the semi-direct product , 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 .
Proposition 2.7 (Symmetry of ). If there exists such that for all , or equivalently, there exists a commutative diagram
then .
Proof. Construct a homomorphism Firstly, we verify that it is a homomorphism, we have It is obviously a surjection. ◻
Similarly, we have the following proposition:
Proposition 2.8 (Symmetry of ). If there exists such that for all , or equivalently, there exists a commutative diagram
then .
Exercise 2.24 (). Prove the above proposition.
Exercise 2.25 (). Prove the group isomorphism
Exercise 2.26 (). Find all -order groups, where and are both prime numbers. Prove that there are at most two different isomorphism classes.
Exercise 2.27 (). If , where is a prime number, prove that the number of conjugacy classes satisfies Here, represents the order of , i.e. the smallest number such that .
Exercise 2.28 (). If is a cyclic group and and are conjugate in , prove that (Hint: Prove that there exist and such that .)
All Groups with
This section will contain quite a few examples: we will classify all groups with order not exceeding , that is, we will find all non-isomorphic groups in this range. First, it should be noted that when is a prime, the only -order group is the cyclic group . Therefore, we are left with orders . We have already proven that there are only two groups of order , and . Now consider the following proposition:
Proposition 2.9 ( case). Let be two primes, and be a group of order . Then,
If , then or .
If , then .
Proposition 2.10. By Sylow’s theorem, the -order cyclic subgroup, denoted by , is a normal subgroup of . Let be a Sylow- subgroup of . Since and , we have , where This implies that if , the above mapping is trivial, so . If , consider the non-trivial choice of , so that becomes a monomorphism. However, the embedding image of in is unique, so these non-trivial homomorphisms differ only by an automorphism of . Therefore, the use of the symmetry lemma tells us that the groups they induce are isomorphic.
So the main difficulty to be discussed is concentrated on the orders .
Classification of -order groups
The commutative -order groups are only , , and . Now we will study the non-commutative -order groups. By Sylow’s theorem, we know that has subgroups of order . It is impossible to have subgroups, otherwise it will occupy at least elements. Therefore, there can only be or subgroups.
If there is only one subgroup of order , , then must hold, otherwise if , there will be no elements of order in , which leads to all elements of being of order or , making abelian, which is not relevant to our discussion. So now we have . Let , then we must have , and there is only one non-trivial choice for the conjugate action. However, in reality, has subgroups of order :
If there are th-order subgroups, note that all subgroups with an index of are normal. By Cauchy’s theorem, we can choose an element of order . If it does not belong to any of the th-order subgroups, then must be a semidirect product, which could be , which is the same as mentioned above. If it is the case of , then choosing shows that this is also .
Now, let’s assume that all elements of order belong to all th-order subgroups. Since at least one of these subgroups must be (otherwise, would be abelian with only elements of order ), we can conclude that there is only one element of order in . This means that all th-order subgroups are isomorphic to . Let be the generators of these subgroups, then we have . Now, consider the element , it cannot belong to or , otherwise if , we would have , which is impossible. Therefore, we must have . If , then . If , we can choose to be and reduce it to the previous case. These relations determine the group , which we will denote as , known as the quaternion group. In fact, this group is generated by in the quaternion field: Now, we will show that is not isomorphic to , as has element of order while has .
Classification of Groups of Order
For groups of order , it is easy to see that the only Abelian groups are and . Now we only need to consider the case of non-Abelian groups. By the Sylow theorem, we know that has either or normal subgroups of order , and either or subgroups of order . We can see that , where or and 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 has a normal subgroup of order . If , then considering , we can see that must be trivial.
If , we know that is the permutation group of the three -order elements in . Consider the map that maps to the unique subgroup in . Thus, can be seen as an isomorphism from to , and different choices of differ only by an element in . By the symmetric lemma of , we know that the groups induced by them are isomorphic. In fact, this group is not a new and unfamiliar group.
Exercise 2.29 (). It can be seen that the above group is .
Now let’s consider the case where it has subgroups of order . Since these subgroups must occupy elements, it is impossible to have subgroups of order , because subgroups of order would occupy at least elements. We conclude that there can only be one subgroup of order , which makes it normal. If , there is only one non-trivial semidirect product .
If , then . It is easy to see that there are only three non-trivial mappings that can be chosen. But these three choices only differ by an automorphism of , which determines the same group . In fact, it is .
Exercise 2.30 (). Prove that it is .
Now we will prove that is neither nor . Since does not have any normal subgroup of order , cannot be isomorphic to . Also, does not have any element of order , 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 :
Order |
Abelian |
Non-Abelian |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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, 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:
Definition 3.1 (Ring). A set with two operations and is called a ring if forms an abelian group under the operation , and for any , the following properties hold:
(Associativity)
(Distributivity) ,
There exists a multiplicative identity such that .
Here, as usual, we agree that the multiplication operation has a higher priority than addition, and we omit the multiplication symbol between letters. In a ring, we use to represent the additive identity and to represent the multiplicative identity.
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 a commutative ring.
Definition 3.2 (Field). If is a ring and every non-zero element has a multiplicative inverse such that then we call a field. If the multiplication in is commutative, then is called a commutative field.
In a ring, non-zero elements may not have a multiplicative inverse. If a non-zero element has a multiplicative inverse, we call it a unit.
Exercise 3.1. Find all units in the ring .
The concepts of rings and fields have many examples in algebra, here are a few common ones.
Example 3.1. The set of all integers forms a ring under the usual addition and multiplication.
Example 3.2. The set of all rational numbers , real numbers , and complex numbers form fields under the usual operations.
Example 3.3. The set of all polynomials with integer coefficients, denoted by , forms a ring under the usual polynomial multiplication and addition, where Similarly, for any ring , we can define the polynomial ring as This is also a ring, with addition defined in the usual way and multiplication defined as It is easy to verify that this satisfies the associative and distributive properties.
Example 3.4. Let be a set consisting of all finite strings. Define as a ring that consists of all finite forms and combinations of strings (and ), for example Addition is given in the natural way, and multiplication is given by concatenation of strings: Under this definition, forms a non-commutative ring, for example while .
Exercise 3.2. Is the set of all natural numbers a ring under the usual integer operations?
Exercise 3.3 (). Verify that the set forms a ring under the usual operations.
Exercise 3.4 (). Consider the set Is it a ring? Is it a field?
Exercise 3.5 (). Let be a ring defined by the following rules, with multiplication given by Prove that is a field. (Hint: Consider )
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.
Definition 3.3 (Ring Homomorphism). A mapping between rings is called a ring homomorphism if satisfies
(Abelian group homomorphism)
(Preserves multiplication)
(Preserves identity element) .
If is still an injection, it is called a monomorphism. If is also a surjection, it is called an epimorphism. If has a homomorphic inverse, it is called an isomorphism. Homomorphisms between fields are also understood as homomorphisms between rings.
Example 3.5. Let be a field, , and define a polynomial valuation homomorphism that maps a polynomial to its value at , .
Exercise 3.6. Verify that this is a ring homomorphism and also a surjective homomorphism.
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 , we can consider the set of all multiples of , denoted as , which is called the ideal generated by . The essential characteristic of this set of multiples is its "absorption" property, which means that for any , we have . This leads to the concept of an ideal as follows:
Definition 3.4 (Ideal). An Abelian subgroup of a ring is called a left ideal if for any , we have . If the condition is changed to , it is called a right ideal. If is both a left ideal and a right ideal, it is called a two-sided ideal. Note that in a commutative ring, we do not need to consider the concepts of left and right ideals, and all ideals are two-sided. In a commutative ring, left and right ideals are simply referred to as ideals. itself is an ideal, called the trivial ideal, and any ideal that is not equal to is called a proper ideal.
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 and a two-sided ideal , we can define the set of cosets This is first and foremost an Abelian group, the quotient group of by the subgroup , with elements being cosets or understood as representatives of the equivalence relation on determined by . Its multiplication is inherited from the larger ring , defined as It can be easily verified that due to the absorption property of ideals, as a subset of , the product . Therefore, the above multiplication is well-defined (independent of the choice of representatives).
Example 3.6. Consider the ideal of the ring . The quotient ring with respect to this ideal is called the ring of residue classes modulo : As an additive group, this is a cyclic group of order . As a ring, it is a finite ring, with the additive identity element being and the multiplicative identity element being . The number-theoretic meaning of this ring is that it consists of residue classes of all integers modulo . It is worth noting that when is a prime number , is in fact a finite field with elements.
Exercise 3.7. For a sequence of ideals , we can define their sum: as the following ideal Prove that this is an ideal. For a finite number of ideals , we can define their product as Prove that this is also an ideal.
Exercise 3.8. Prove Fermat’s little theorem in number theory by following steps:
Let . Prove that for any , .
From this, it follows that has a multiplicative inverse, i.e. is a field, sometimes denoted as , called the -element finite field.
Prove that is a multiplicative group, hence for any , .
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 is a prime number and , then and must hold. From the perspective of ideals, is the set of multiples of , which is an ideal of . In this case, we have We can generalize this concept to any ring. If a proper ideal satisfies the above property, then is called a prime ideal. That is, if then is a prime ideal. For a commutative ring , the set of all prime ideals is usually denoted by . Note that the trivial ideal is not a prime ideal. This is a convention, similar to the convention that is not a prime number. The reason is that is a unit, and should not be called a prime number.
Exercise 3.9 (). We call a ring an integral domain if implies or in . Prove that is an integral domain if and only if is a prime ideal.
Exercise 3.10. Let be a ring homomorphism. Prove that the preimage of a prime ideal is always a prime ideal. That is, if is a prime ideal, then is a prime ideal of .
Another useful concept is the maximal ideal. A proper ideal of a ring is a maximal ideal (left, right, two-sided) if there is no proper ideal (left, right, two-sided) of that contains . We state a few simple properties of maximal ideals.
Proposition 3.1 (Maximal ideals are always prime ideals). Let be a maximal ideal (two-sided) of . Then is also a prime ideal (two-sided) of .
Proof. Otherwise, suppose but . Consider Since are strictly larger than , according to the assumption, they can only be equal to the trivial ideal . Thus, we have This contradicts the fact that is a maximal ideal (by definition, it must be a proper ideal). ◻
Proposition 3.2. Any non-unit element is necessarily contained in some maximal ideal.
Proof. Consider the (left) ideal generated by . Since is not a unit, we know that . Therefore, is a proper ideal. Using Zorn’s lemma on the set of all ideals containing , we can find a maximal (left) ideal that contains it. ◻
Exercise 3.11 (). Prove: Let be a two-sided ideal of , prove that is a field if and only if is a maximal ideal.
Exercise 3.12 (). Let be contained in all maximal ideals, prove that is a unit.
Kernels and Images of Homomorphisms
Just like the kernels and images of group homomorphisms, for a ring homomorphism , we can define and
Exercise 3.13. Verify that the kernel is a two-sided ideal in and the image is a subring in .
We have an obvious isomorphism theorem.
Theorem 3.1 (First Isomorphism Theorem). Given a ring homomorphism , it induces a ring isomorphism
Proof. This isomorphism is defined by It is obviously well-defined, since the image of is 0. If , then , so it is injective. Surjectivity is also obvious. ◻
Theorem 3.2 (Corresponding Theorem). Let be a bilateral ideal, be the natural projection. Then all ideals of correspond one-to-one with ideals of that contain .
Exercise 3.14. Prove that the only ideals of a field are the trivial ideal and the zero ideal . Explain that a homomorphism from a field to any ring can only be a monomorphism or the zero homomorphism.
Noetherian Property
If all ideals in the ring are finitely generated, i.e. any ideal can be expressed as (where for right ideals, we replace with ), where , then we say that 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:
Theorem 3.3 (Noetherian Property). The following three statements are equivalent (each with a corresponding theorem for left, right, and two-sided, respectively):
is a Noetherian ring.
Any ascending chain of ideals in , must eventually stabilize, i.e. there exists such that .
Any non-empty set consisting of ideals in must have a maximal element, i.e. there exists such that .
Proof.
Assume , it is easy to prove that this is an ideal. Therefore, is finitely generated. Let it be generated by . By definition, we can assume , then when , , so the chain stops here.
Otherwise, there exists a strictly increasing infinite chain, which contradicts .
Let be an arbitrary ideal. Suppose is the set of all finitely generated ideals contained in . Then we can choose a maximal element . If , there exists but . Consider , which is a finitely generated ideal strictly larger than . This contradicts the definition of . Therefore, . ◻
Exercise 3.15. Prove that a finite ring is necessarily Noetherian.
Exercise 3.16. Prove that if is Noetherian, then is also, where is a two-sided ideal. Hence, it follows that any homomorphic image of is also Noetherian.
The following fundamental theorem shows that many rings are Noetherian.
Theorem 3.4 (Hilbert’s Basis Theorem). If is Noetherian, then is also.
Proof. Let be an ideal in (assume it is a left ideal). Define There is an ascending chain of ideals By the Noetherian property of , each is finitely generated and this chain must stop. Let Then take the polynomials corresponding to the generators of , where . We will prove that , it can be generated by . Suppose its leading coefficient appears in , where , then we have with degree strictly less than . If it is not , we can continue by taking some , where , and define with degree strictly less than . If it is not , we can continue this process. But since the degree is a non-negative integer, this process must stop, and we can finally get This proves the proposition. ◻
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 , we define the ideal notation to represent the ideal generated by . If an ideal can be generated by a single element , i.e. , then we call it a principal ideal. If all ideals of an integral domain are principal, then we call it a principal ideal domain (PID).
Theorem 3.5 (Greatest Common Divisor Theorem). is a PID.
Proof. Let be a nonzero ideal of , and let . If , the proof is complete. Otherwise, let such that does not divide . Consider the division with remainder Thus, we have . If all elements in are divisible by , then and the proof is complete. Otherwise, we can continue to take out an element that is not divisible by and repeat this process, obtaining a positive integer smaller than that belongs to . However, since is a positive integer, this process cannot continue infinitely and there must be a step where is an element of and all elements in are divisible by . Therefore, is a principal ideal. ◻
Corollary 3.1. Let be the greatest common divisor of . Then there exist integers such that
Proof. According to the theorem, is a principal ideal. Obviously, . But since , we also have , so divides the greatest common divisor of , . This shows that . Therefore, , and there exist such that ◻
Let be a general integral domain. Similar to how we define prime numbers, we call a non-unit element irreducible if implies that either or is a unit. We also call a prime element if is a prime ideal, meaning that implies or . We know that in the case of the integer ring , 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.
Exercise 3.17 (). Prove that in a PID, irreducible elements and prime elements are equivalent.
We will now show that principal ideal domains have very good properties in terms of arithmetic.
Theorem 3.6 (PIDUFD). We call an integral domain a Unique Factorization Domain (UFD) if every non-zero element can be written uniquely as a product of irreducible elements (without considering order, and assuming units). We have: is a PID is a UFD. As a corollary, irreducible elements and prime elements are also equivalent in a UFD.
We first prove a lemma, which is equivalent to the existence of decomposition.
Lemma 3.1. In a Noetherian ring, for any non-zero ideal , there exist a finite number of non-zero prime ideals such that .
Proof. Let be the set of ideals for which the proposition does not hold. Then we choose a maximal element . Since is not a prime ideal, there exists such that . We have Note that and are strictly larger than . By the definition of , they have decompositions. Therefore, their product also has a decomposition, which contradicts the definition of . Hence, is an empty set.
As for uniqueness, we can assume that there are two decompositions where are units and are prime ideals. From , we can conclude that , which means they differ by a unit and can be cancelled from both sides. Repeating this process until one side becomes a unit, the other side cannot possibly have any prime elements left. This proves that and the prime factors appearing in the decomposition are exactly the same up to order and units. ◻
Exercise 3.18 (). Explain why in PID, all non-zero prime ideals are maximal.
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 , we have These are two distinct factorizations of . The interesting thing is that the factors appearing in these factorizations are irreducible but not prime.
Exercise 3.19 (). Prove that are irreducible elements in , but not prime. Hence, the unique factorization property does not hold in .
Interesting Example: Gaussian Integers
A Gaussian integer is defined as . We will use a method similar to to prove that is a PID and therefore a UFD. We define a norm in the ring : It describes the ’size’ of elements in the ring. It is easy to see that this norm is multiplicative, i.e. . This also has implications in arithmetic.
Exercise 3.20. Prove that if both and can be written as the sum of two squares, then can also be written as the sum of two squares.
Exercise 3.21. Prove that in , if and only if is a unit.
Lemma 3.2 (Euclidean division in Gaussian integers). Let . Then there exist such that and .
Proof. Consider the quotient of complex numbers , where and are the two integers closest to and , respectively. Then, where , and Thus, ◻
Corollary 3.3. is a PID, and therefore also a UFD.
Proof. Following the proof that is a PID, for any non-zero non-unit element , if , we can choose and repeatedly use Euclidean division to make the norm of the remainder smaller. Since this is a positive integer, the process must eventually stop, and we can obtain such that divides all elements in . ◻
Let’s see the powerful application of the fact that is a UFD.
Proposition 3.3. We prove that the equation has only one unique integer solution, .
Proof. Consider the equation in : Let be their greatest common divisor in . Then . It is easy to factor as , where is a unit and are irreducible elements, hence prime elements. If contains or as prime factors, then would be even, which means is divisible by , and thus is a number of the form . However, this is impossible since the remainder of any integer squared divided by can only be or . Therefore, is a unit, which means and are coprime. In a UFD, if the product of two coprime numbers is a cube, then both numbers are cubes up to a unit, so we can assume: where is a unit. Since the only units in are , and , , we can multiply into the parentheses of the cube, so we can assume . Then: This implies , which means . Therefore, , which can only be satisfied if and . Thus, the only integer solution to the equation is . ◻
Exercise 3.22 (). Prove that is a PID.
Exercise 3.23 (). Find all integer solutions to
Exercise 3.24 (). Prove that is not a UFD, but the ring which is slightly larger than it is a PID.
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.
Theorem 3.7. Let be two polynomials, where the degree of , . Then there exist polynomials such that where
Proof. Let , . Then take We have The th term is cancelled. If its degree is not less than that of , let be its next highest non-zero term, we can take We have If its degree is not less than that of , we can continue this process until its degree is less than that of , and we denote this as . ◻
Exercise 3.25 (). Is the polynomial ring generated by two variables and still a PID? Why?
Fractionalization and Fraction Field of Rings
This section discusses only commutative rings. For an integral domain , we can take a multiplicative subset , that is, a subset satisfying . Without loss of generality, we can assume that . The fractionalization of the ring with respect to is defined as This set can be naturally equipped with addition and multiplication structures Two fractions are considered equivalent if and only if . It can be easily verified that this forms a ring. If we take , then the resulting fractionalization is denoted as and is called the fraction field of .
Definition 3.5 (Integrally Closed). Let be an integral domain and let . If there exists an element satisfying a monic polynomial equation with coefficients in then is said to be integral over . The set of all elements in that are integral over is called the integral closure of in , denoted as . If the integral closure of in is equal to , then is said to be integrally closed (or normal).
Example 3.7. The integral closure of in is , because if is a reduced fraction satisfying a monic -coefficient equation, we can multiply both sides by to get which implies that every prime factor of divides . By the assumption of being reduced, can only have no prime factors, which means is a unit and is an integer. Therefore, is integrally closed.
Example 3.8. Let be a square-free number, then This is because, The denominator is not equal to , because is square-free.
Exercise 3.26. Prove that UFDs are integrally closed.
Exercise 3.27. Verify that is integral over , thus proving that is not a UFD.
Exercise 3.28 (). Find the integral closure of .
Exercise 3.29 (). Let’s examine an example of how localization affects prime ideals.
For the ring , list all of its prime ideals.
Take and consider the localization of the ring . List all of its prime ideals.
Take the prime ideal and let . Prove that this is a multiplicative subset and list all of the prime ideals in .
By following the prompts below, prove that is a UFD. Hence, it can be concluded that a UFD is not necessarily a PID.
Let be the field of fractions of . Then is a polynomial ring over the field , and thus a PID.
Place any polynomial into to obtain a factorization.
Examine this factorization in some , where is some irreducible polynomial. Note that is a field, and thus is also a PID.
Prove that is a UFD.
Elementary Number Theory in Cryptography
is an abelian group, representing the residue classes modulo , and forms a group under addition. If we consider , the set of all residue classes coprime to , this set forms a group under multiplication, and its order is . According to Lagrange’s theorem, for any , we have , which means that for any integer coprime to , we have 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 as a one-time key that only they know. Before communication, the key is added to the plaintext to obtain the ciphertext . Since is completely random and independent of , the distribution of is also completely random, i.e. it has a trivial uniform distribution. Therefore, anyone who only obtains without knowing cannot gain any information about . The recipient only needs to calculate to obtain the original message. However, this key can only be used once, as 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 formed by multiplying two large prime numbers, then is a group of order . That is, for , . In fact, the corresponding congruence holds for all . This means that if we take a pair of exponents such that , we will have for all . Therefore, we can use to encrypt the message , obtaining the ciphertext , and then use to decrypt it, obtaining . Note that the key used for encryption and the key used for decryption are different, and their relationship needs to be obtained by solving (according to ideal theory, it is only necessary to ensure that and are coprime to exist ). If are large, it will be difficult to factor , and without factoring , it is impossible to know the value of (it can be easily proved that, given , knowing is equivalent to knowing and ). Therefore, we can construct the following encryption system without the need for key distribution:
First, generate two random, large prime numbers .
Calculate .
Randomly generate an integer that is coprime to , and use Euclidean division to calculate such that .
Publicly announce as your public key, keep as private (secret) information, and keep or discard information such as .
When someone needs to send an encrypted message to you, they can calculate and send it to you through a channel.
A third party who obtains cannot know because they do not know and cannot factor .
You only need to calculate 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:
Definition 4.1 (-module, multiple module, bimodule). Let be a ring, an -module is defined as an abelian group with a (left) action of on , which means for , , we can define an action of on , denoted as . This can be understood as a mapping from to , and this action satisfies the following properties:
(Identity)
(Associativity)
(Left Distributivity of )
(Right Distributivity of )
We say that is a left -module, also denoted as . Similarly, if defines a right action , satisfying similar properties, note that the associativity should be changed to . We say that is a right -module, also denoted as .
If we compare the definition made for group actions, that is, a group action is a group homomorphism , then we can also understand the above definition as a left -module is the action of on an abelian group , that is, a ring homomorphism . Here, represents the ring formed by group homomorphisms from to itself, and its multiplication is the composition of abelian group homomorphisms . So each can be imagined as an operator on , an endomorphism, that is, . Because is an abelian group homomorphism, the distributive law of is automatically satisfied. The existence of identity element, associativity, and the distributive law of are guaranteed by the fact that is a ring homomorphism.
It is worth noting that a right -module is a contrahomomorphism , which reverses the direction of multiplication, .
If a group has multiple module structures defined on it, and a family of rings has left module structures defined on it, and another family of rings has right module structures defined on it, then we say that their actions are commutative, or that their actions are compatible, if , and and . If these module structures are compatible with each other, then we call a multi-module, which can be denoted as -module, or -module, or written as , and sometimes also written as . If is a multi-module, i.e. it is both a left -module and a right -module and the two module structures are compatible with each other, i.e. , then is called a bi-module over . In the case where is a commutative ring, left -modules and right -modules are collectively referred to as -modules.
Exercise 4.1. Verify that the left multiplication of a ring on itself can be seen as a left -module. Similarly, the right multiplication is a right -module, so is a bi-module over .
Exercise 4.2. Let be a bilateral ideal of . Verify that is a bilateral -module under the natural left and right multiplication.
Exercise 4.3. Explain that every Abelian group is a -module, and that a -module is also an Abelian group. Show the equivalence of these two concepts.
Exercise 4.4. For a commutative ring , the structure of a right -module can be defined for a left -module as follows: Why does this definition not hold when is not a commutative ring?
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
Definition 4.2. Let and be two -modules. A homomorphism of -modules is defined as an Abelian group homomorphism satisfying for all and . For right modules, the condition is modified to . A homomorphism of -modules is also called an -linear map.
For homomorphisms between multiple modules, must be compatible with all module structures.
The meanings of monomorphism, epimorphism, and isomorphism are obvious and will not be repeated here. If there exists a module homomorphism , we say that and are isomorphic and denote it as . Since the theory of right modules is completely similar, we will mostly consider left modules by default.
For a subset of , if it satisfies , we call a submodule of . For any submodule, we can construct a quotient module , whose elements are cosets , and the action is defined as It can be easily verified that this definition does not depend on the choice of coset representatives and satisfies the definition of an -module.
Exercise 4.5. Assume that is an -module homomorphism. Prove that is a submodule of , and is a submodule of . Prove the first isomorphism theorem
Exercise 4.6. Let be a family of submodules of . Prove that and are both submodules of .
The following two theorems are essentially the same as the isomorphism theorem in group theory.
Theorem 4.1 (Second Isomorphism Theorem). Let be submodules of some -module. Then and are also submodules and
Theorem 4.2 (Corresponding Theorem). Let be a submodule of . Then the submodules of correspond to the submodules of such that .
Exact Sequence
When we have a sequence of modules and homomorphisms
if , we say that the sequence is exact at . 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.
Exercise 4.7.
is an exact sequence if and only if is a monomorphism.
Exercise 4.8.
is an exact sequence if and only if is an epimorphism.
Example 4.1.
is a short exact sequence of -modules, where is the multiplication by map and is the projection. Here, .
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.
Functor
Given two left -modules and , we can define the set of all -module homomorphisms from to as . For a collection of multiple module homomorphisms , we denote the set as . Sometimes, to distinguish the direction of module homomorphisms, we use the notation to denote the set of left -module homomorphisms from to . For two homomorphisms and , we can define their sum as which is also a homomorphism. Therefore, , showing that is an Abelian group. It is worth noting that if both and are either left or right -modules without any multiple structure, then their does not have a natural -module structure and is only an Abelian group (a -module). However, if at least one of and has a multiple structure, the functor can be naturally endowed with a module structure, which we will demonstrate.
Module Structure of
Let and be two rings. If has a left -module structure and a right -module structure, we write it as when we need to specify the module structure.
We will give an example to show that has a left -module structure. This is because we can define, for and , Then is clearly a left -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 satisfies the definition of a left -module, all other properties are obvious, the only one that needs careful checking is the associativity: The left homomorphism is , the right homomorphism is , so this is true, which means that becomes a left -module under this definition.
There are a total of eight similar cases, and we list all cases in the following table:
Group |
Natural module structure |
Definition of -module structure |
|
-module |
none |
|
Left -module |
|
|
Right -module |
|
|
Right -module |
|
|
Left -module |
|
In summary, the direction of the -module structure on determines the direction of the -module structure on . If the bimodule structure appears on , the action will be reversed by composing functions from the inside out, causing a change in the direction of the module.
Exercise 4.9 (). Confirm that you understand all the cases in the table.
Endomorphism Ring
When , is denoted as , and it has a natural ring structure, where multiplication is the composition of homomorphisms from to .
Exercise 4.10 (). Prove that if is an -module, then it has a natural left bimodule structure.
Functoriality of
What does the 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:
To correspond the object to the object .
To correspond the map to another map or . If it satisfies the former, it is called a covariant functor, and if it satisfies the latter, it is called a contravariant functor.
The functor must preserve composition, i.e. .
We also require the functor to correspond the identity map to the identity map, i.e. .
As an example, we will explain in detail how forms a functor.
For a fixed -module , we find that is a contravariant functor, sometimes denoted as . This functor maps the -module to the Abelian group , and maps the -module homomorphism to the group homomorphism It is clear that it preserves composition and identity maps.
Similarly, for a fixed module , we find that is a covariant functor, which maps the module homomorphism to the group homomorphism It also preserves composition and identity maps.
Direct Sum
Given two left -modules , their direct sum is defined as the set as an Abelian group, with addition defined as component-wise addition, and -action defined as It can be easily verified that this definition gives an -module structure. Direct sums are not limited to finite sums, for any family of -modules indexed by a set , , we can define the direct sum as If we take a sequence of identical modules , we denote this direct sum as .
Exercise 4.11 (). Verify that if are two submodules of , satisfying then there exists an isomorphism . In this case, we call the internal direct sum of .
Exercise 4.12. Prove that we have the following obvious exact sequence:
Here, let be a submodule. Then is a natural exact sequence.
Direct Product
Similar to direct sum, a direct product of a family of modules is obtained by giving the set 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 is allowed as an element. Similarly, if we take a sequence of the same module , we denote this direct product as .
Example 4.2. Consider , and are two -modules, then is an element of , but not in . There is a natural inclusion , and is a submodule of .
Exercise 4.13. The finite direct sum of modules is isomorphic to the finite direct product.
Exercise 4.14. Prove the following universal properties of direct sums and direct products, and the natural isomorphisms: Explain their equivalence with the following statements:
For any mapping , there exists a unique mapping such that . Here, is the natural inclusion mapping.
For any mapping , there exists a unique mapping such that . Here, is the projection onto the component.
Free Module
A module obtained from an arbitrary number of direct sums (possibly infinite) of , or a module isomorphic to it, is called a free -module. For example, ( direct sums of ).
The importance of free modules lies in their good properties. Any homomorphism starting from can be easily determined by specifying where each (the -th position is ) is mapped to. The entire homomorphism is completely determined by this. Because every element can be written as we have It is worth noting that there is no restriction on how to choose the value of . In other words, the determination of depends entirely on the arbitrary choice of values , or, it depends on an arbitrary element . This gives the following natural isomorphism
Exercise 4.15. Prove the basic property of free modules Note that may be infinite, and note the difference between direct sums and direct products.
Generators and Basis
For a (left) -module , after selecting a family of elements , we can define a map from . We temporarily denote this map as . The image of this map is called the -linear combination of . We say that is a set of generators of if is surjective. In other words, any can be written as a finite linear combination of : If there exists a finite family of that generates , then is called finitely generated. We say that is a set of -linearly independent elements, or simply independent, if the corresponding map is injective. In other words, if any finite subset of , has any -linear relation then all coefficients . If a set of elements is both a set of generators and independent, then it is called a basis of .
Exercise 4.16. Show that having a basis is equivalent to being isomorphic to a free module.
Exercise 4.17. Give an example of a non-free module, so it has no basis, although it must have generators, but they must not be linearly independent.
Exercise 4.18 (). Consider as a field. Since is a commutative ring, -modules are not distinguished between left and right. We call -modules -vector spaces or -linear spaces. -module homomorphisms are called -linear maps or -linear transformations.
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 -module. This makes linear space very easy to study, and we will explain this. Next, we assume that is a -vector space.
Theorem 4.3 (Basis Extension Theorem). Let be an independent set of and be a generating set of , satisfying . Then there exists a basis of such that .
Proof. If there is a series of increasing independent sets such that , then obviously is also an independent set and satisfies . Therefore, by Zorn’s lemma, there exists a maximal independent set that satisfies . We will prove that can generate , that is, the corresponding mapping is an isomorphism. Otherwise, there exists that cannot be represented as a linear combination of elements in . Since is a generating set, there exists a finite sum , where is a finite set. Therefore, there must be an element that is independent of , otherwise all are linearly dependent on , and since is an independent set, it can be deduced that all can be generated by , which leads to the conclusion that can also be generated by , which is impossible. However, in this case, is a larger independent set contained in , which contradicts the assumption that is a maximal independent set. Therefore, is a basis. ◻
Example 4.3. Consider , is the set of all vectors on the plane. Under component-wise addition, forms an Abelian group. Then naturally becomes a -vector space under -multiplication: It is easy to verify that satisfies the four definitions of a -vector space (-module) under this action. is a basis for .
Exercise 4.19 (). Prove that the following statements are equivalent for a vector space :
is a basis for .
is a maximal linearly independent set in .
is a minimal generating set for .
Exercise 4.20. Let , find out which of the following are bases of and which are not?
Dimension Theory
If has two different bases , we hope to prove that and are equipotent, that is, there exists a bijection between them.
Finite Case
If are both finite, let have fewer elements. We use induction on to prove that . If , , then any element in can be written as a nonzero -coefficient multiple of , and they cannot be linearly independent unless .
Now assuming that the proposition holds for , we consider the case where . Let , by the basis extension theorem, there exists a basis such that , so , and has (as the projection image) as a basis, with elements. Similarly, also has as a basis, so .
Infinite case
Now assuming that has an infinite basis , so , if is another basis, for each , there exists a finite expression where only finitely many are non-zero. Then for any , consider the finite set , since can generate the entire space, for each there must be some with non-zero coefficient for , so we have Since is infinite, this implies , and since is infinite, we can use the same reasoning to show that .
Definition 4.3. We define the dimension of to be the cardinality of any basis of .
Exercise 4.21 (). Let there be a family of exact sequences of -vector spaces Using the basis extension theorem, prove that From this, deduce the following dimension formulas
Let , then
Let be a subspace, then
.
Let be two subspaces, then
Matrices over Commutative Rings
Finitely Generated Free Modules
In this section, we assume that is a commutative ring. It is worth noting that in the free module , there exists a standard basis, where each element can be uniquely written in the form .
If an -module is isomorphic to , we say that has rank . However, we have not yet proven the uniqueness of rank, that is, we need to prove . 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 -module homomorphisms from to . Since we know that to determine a homomorphism , it is essentially enough to know where each is mapped to in . We use to denote the standard basis of . If we denote the th component of the image of as , then we can write Here are the elements in that we want. We can arrange these elements into a matrix Matrices are usually represented by capital letters , etc. Here our matrix is the matrix of , which we also denote as . When we need to emphasize that the matrix elements are , we write . This matrix has rows and columns, and we say it is an matrix over , denoted as . When , this notation is simply written as .
Exercise 4.22. Make sure you understand: giving an matrix is equivalent to giving a homomorphism . That is, any matrix consisting of elements of represents a homomorphism. So any matrix can be (uniquely) written in the form of , where is some homomorphism.
Composition of mappings and multiplication of matrices
For , and , we can define the homomorphisms and . Similarly, we can define scalar multiplication and addition of matrices, i.e. we define multiplied by as the matrix corresponding to the mapping : Let and be the matrices corresponding to the homomorphisms and , respectively. Then we define as the matrix corresponding to the mapping :
Exercise 4.23. Prove that the elements of are , and the elements of are . Thus, prove that forms an -module.
When we have the composition of homomorphisms
we can calculate using and , and we call this process matrix multiplication, denoted as How do we actually perform this operation? We can write out the matrices as Therefore, This shows that the coefficients of should be This is the formula for matrix multiplication. Note that is , is , and is , which means that matrix multiplication gives a mapping When , this multiplication operation gives multiplication on , making a (usually non-commutative) ring.
Exercise 4.24. The necessary condition for a ring is that multiplication satisfies the associative law. From the fact that composition of mappings satisfies the associative law, we can deduce that matrix multiplication also satisfies the associative law.
Exercise 4.25. Let be the identity mapping. Write its matrix as . This matrix is called the -dimensional identity matrix. It is the multiplicative identity in .
Exercise 4.26. Let .
Show that if we view elements in as matrices (called column vectors), then the mapping corresponding to is the matrix multiplication where .
Show that the image of as a linear mapping, , is a submodule of generated by all the columns of .
Reduction Theory of Matrices over PID
In this section, we assume that is a PID and consider an matrix over . Note that, by matrix multiplication, has a multi-module structure, which means that it can be acted upon by -order square matrices on the left and -order square matrices on the right.
The group formed by the multiplicative inverses in the ring is called . We say that are equivalent if there exist two invertible elements , such that . Note that equivalence is an equivalence relation.
Elementary Transformations of Matrices
For the matrix multiplication , we can interpret it as being a recombination of the columns of and the rows of , with the coefficients determined by another matrix. From the formula for matrix multiplication we can see that the th column of is obtained by multiplying the first column of by , adding the second column of multiplied by , and so on until the th column multiplied by . Similarly, the th row of is obtained by multiplying each th row of by the corresponding 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:
Multiplying one row (or column) of the matrix by a non-zero element in , and then adding it to another row (or column). For example, multiplying the first row of by and adding it to the second row:
Rearranging the rows or columns of the matrix. Let , if we want to rearrange the rows of the matrix using the permutation , we left multiply with an -dimensional matrix . Here, is a function that equals when and otherwise. We have Such a matrix is called a permutation matrix. Similarly, to rearrange the columns of the matrix, we right multiply with an -dimensional permutation matrix.
Multiplying a row or column of the matrix by a unit . This can be achieved by left or right multiplying the matrix with a diagonal matrix The row (or column) containing is the one that needs to be multiplied.
Adding times the th row (or column) of the matrix to times the th row (or column) to create a new th row (or column), and adding times the th row (or column) to times the th row (or column) to create a new th row (or column), where . This is also a reversible transformation, which is equivalent to left multiplying with the following matrix (for the column case: right multiply and swap and ): where the omitted parts are all diagonal s. Its inverse is
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 and in a certain order. By the associative law, the result can be written as Of course, this is equivalent to saying that is a multi-module of .
Equivalent Canonical Form
Theorem 4.4 (Equivalent Canonical Form in PID). Let , where is a PID. Then there exists a unique (up to units in ) set of such that and is equivalent to the following diagonal form: Here, represents a zero matrix (which may not exist), and the empty positions are all . We call the obtained the rank of , denoted as .
Proof.
Consider the top left element of the matrix. By performing row and column swaps, we can move the element with the least number of prime factors to this position. We define to have infinitely many prime factors. If the entire matrix is , we can consider it as already completed. Otherwise, we can assume that has a finite number of prime factors.
If divides all elements in the first column, we can use elementary row operations to eliminate all remaining elements in the first column. Otherwise, we move the that is not divisible by to the position of . Let . We have . Here, it must be that , otherwise if both and are divisible by some prime factor , we have , which is impossible. Therefore, we can assume that there exist such that . Then, by multiplying the original first row by and adding it to the second row multiplied by as the new first row, and multiplying the original first row by and adding it to the second row multiplied by as the new second row, we obtain a new top left element , which is a proper factor of the original and has fewer prime factors.
We continue this operation until all elements in the first column are divisible by . At this point, the other elements in the first column can be eliminated by through elementary operations, and we perform a similar operation on the first row until all elements except are .
If divides all elements in the matrix, we let and continue the above induction operation on the matrix starting from the second row and second column. Otherwise, we repeat the first step and move the element with the least number of prime factors in the matrix to . This operation will eventually stop, because the number of prime factors of will continue to decrease until it either divides all elements in the matrix or all its prime factors are removed and it becomes a unit, in which case it still divides all elements in the matrix.
By repeating this operation, the matrix can eventually be transformed into the desired form.
◻
Exercise 4.27 (). In this problem, is a PID. And let be viewed as an -linear transformation from to . Follow the hints below to discover the Gaussian elimination method.
Prove that is invertible if and only if it is equivalent to the identity matrix , and hence conclude that is invertible if and only if and .
Show that any invertible matrix can be written as a product of elementary matrices (i.e. the matrices used in elementary transformations). In other words, elementary matrices generate .
Prove that if is invertible, then it can be transformed into the equivalent standard form by using only row transformations.
Consider the following algorithm for finding the inverse matrix , and write down the two matrices side by side, where is an matrix. Use only row transformations (or column transformations if is also an -order square matrix) to perform the same operations on both and . Prove that when is transformed into the identity matrix, is transformed into .
Consider the cases where and is a column vector, and obtain an algorithm for finding the inverse matrix and solving the equation when is invertible. Here is an unknown column vector.
Suppose is not necessarily invertible. Prove that the kernel of , denoted by , can be generated by , where is the matrix that transforms into its equivalent standard form, and is the number of nonzero .
Obtain the following algorithm for computing the submodule : Write the two matrices side by side, where is the identity matrix. Apply elementary transformations to and perform the same column operations on , but do not perform any row operations. When is transformed into standard form, the submodule generated by the last columns of the right matrix is .
Let be a linear map. Under a certain basis of and , the corresponding matrix is . Prove that .
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, . 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.
Theorem 4.5. If is an integral domain, then .
Proof. We use the field of fractions of the integral domain and consider "vectorizing" this problem. This may allow us to use the fact that vector spaces have a well-defined dimension to prove the proposition.
In fact, the mapping defines an matrix over . Since is an integral domain, the inclusion mapping is injective, and we can view as a matrix over , denoted as . This matrix defines a mapping , and since has an inverse, we can see that also has an inverse. Therefore, is also an isomorphism. By the uniqueness of dimension for vector spaces, we have .
Thus, we can define the rank of a finitely generated free module as . ◻
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).
Example 4.4. Let be a Noetherian ring. Then, as a submodule of itself, is a module whose submodules are all ideals of . By the Noetherian property, these ideals are finitely generated, so is a Noetherian module.
Similar to Noetherian rings, we have the following equivalent statements:
Theorem 4.6. The following statements about -module are equivalent:
is a Noetherian module.
Any ascending chain of submodules of must terminate.
The set of all submodules of has a maximal element.
Exercise 4.28 (). Using the proof of Noetherian ring, explain the equivalence relation mentioned above.
In order to show that all common modules are Noetherian modules, we construct other Noetherian modules starting from .
Theorem 4.7.
If is a Noetherian module, then all homomorphic images of are also Noetherian modules.
is a Noetherian module if and only if there exists a submodule such that and are also Noetherian modules.
Finite sums and direct sums of Noetherian modules are also Noetherian modules.
Proof.
The image of any homomorphism is isomorphic to . By the Correspondence Theorem, all ascending chains of submodules of can be corresponded to ascending chains of submodules of , and thus must terminate.
: Clearly holds.
: Consider a family of ascending chains of submodules of , denoted by . Then and are two ascending chains of submodules of and , respectively. Since they are both Noetherian, these two sequences must terminate. Therefore, it suffices to prove that if , , and , then . Suppose , then there exists such that . Since , we have .
From , we can see that finite direct sums are Noetherian. Moreover, for a general finite sum , it is the image of the homomorphism .
◻
As a conclusion, if is a Noetherian ring, is Noether, so all finitely generated -modules are Noether, because they are all homomorphic images of some .
Finite generated free modules over PID
Let be a PID, then is obviously a Noetherian ring, so is a Noetherian module, so all its submodules are finitely generated. Let be a submodule, since it is finitely generated, there is a surjection , which can be composed with the natural map to obtain a map , whose image is . So we can write this map as an matrix , consider the equivalent standard form of , there are invertible -order and -order square matrices such that , where is a diagonal matrix. Translating back to the language of maps, this means that there are two isomorphic maps and such that . Obviously , where the matrix corresponding to is , which is of the following form Here , . So we know that there is a basis of such that , where the direct sum is an internal direct sum. This is already isomorphic to , if you want to change back to the original form of , then since is an isomorphism, Here still forms a basis of , because is an isomorphism. So there is a basis of such that
Finite Generation Modules over PID
Any finite generation module 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 over a PID are of the form , where is a basis of (not necessarily the standard basis). Therefore, under the isomorphism , this quotient is isomorphic to
Theorem 4.8. Let be a PID and be a finite generation -module. Then there exists a sequence of elements in and a non-negative integer such that This is called the ’cyclic decomposition’ of .
Exercise 4.29 (). Prove that all finitely generated abelian groups are isomorphic to the following form where is a sequence of integers.
Exercise 4.30 (). Using prime factorization in PID, transform the above structure theorem for finitely generated modules into the following "quasi-prime decomposition" form.
If , where is a unit, are distinct primes, and are non-negative integers, prove (this can be seen as a special case of the Chinese Remainder Theorem. Essentially, you only need to prove the case where , where are coprime)
Show that .
Prove that all finitely generated -modules are direct sums of modules of the form and . More precisely, there is the following decomposition where , .
Conversely, show how to transform quasi-prime decomposition into cyclic decomposition.
Standard Form of Linear Maps
In this section, we consider as a linear map on a finite-dimensional -vector space. Let be a basis of and write in matrix form . A problem arises here, as there is no explicit choice of basis in the vector space and the definition of . 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:
How does the choice of different bases affect the matrix?
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 be another basis, with its matrix denoted as . The so-called matrix is essentially a mapping from to , and its relationship with the original mapping can be described using the basis mapping , where is the mapping determined by and is an isomorphism. Viewing as a linear mapping from to , we have , 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 is the mapping determined by another basis, we have . Therefore, This story can be represented by the commutative diagram below.
Note that is also an matrix and is also an isomorphism (thus an invertible matrix). Let’s denote this matrix as and call it the coordinate transformation matrix. We then have This way, two matrices from the same mapping are connected. If there exists an invertible matrix such that two square matrices are connected by the above relationship, we call these two matrices similar. It can be easily verified that similarity is an equivalence relation on .
Exercise 4.31. Let , and choose to be the unique linear mapping that satisfies and . What is the matrix corresponding to ? If we choose a new basis , calculate the transformation matrix and .
Similar Standard Form
Now we need to answer the question, given two matrices , 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 and are invariant under similarity transformations. Second, we can find a representative element in each similarity equivalence class, and then see if matrices and 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 on under a basis. We find that, in addition to being a -module, can also be acted upon by . By repeatedly applying and their linear combinations, we can apply any -polynomial to , where is a polynomial. Thus, becomes a -module, with the action defined as We consider, if we let represent the action of the matrix, is the similarity of matrices related to the corresponding -module structure? In fact, we can find that
Lemma 4.1. Let be the -module structure of under the action , and be the -module structure of under the action . Then and are similar if and only if, as -modules, .
Proof.
If is similar to , then the transition matrix is the required isomorphism mapping, noting that its action on is different on its range and domain. Since it is an invertible matrix, it is obviously a -module isomorphism. To verify that it is a -module homomorphism, it is sufficient to show that it commutes with : Note that conceptually, , although as vector spaces and are identical, their -module structures are different.
Conversely, if there exists a -module isomorphism , then we have which implies .
◻
So, we found that classifying matrices or mappings by similarity is equivalent to classifying modules. Note that 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 or quasi-prime modules . One idea is that we can use matrices corresponding to these forms as our representatives, so we only need to transform 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 , we call the obtained the invariant factors of the matrix or . 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, becomes a direct sum of modules of the form ( will not appear in the decomposition because is a finite-dimensional -vector space), where is an irreducible element of . When we write (allowing for repetition of elements in the sequences and ), we call all of these (which can be repeated) the elementary factors of or . It is easy to see that giving the elementary factors completely determines the module structure of . The above decomposition is not only a direct sum decomposition of modules, but also a direct sum decomposition as modules. Therefore, we only need to find a -basis for to find a -basis for . Let be a polynomial with leading coefficient (because in , are all units), we take the images of in as a -basis. Then the action of on this basis is just multiplication by , so we have This gives the matrix of on the subspace as Thus, in this basis, the matrix of is a matrix composed of such matrices arranged diagonally Here, all elements in the matrix belong to , and we call it the rational standard form of .
Exercise 4.32 (). Let be a linear transformation on an -dimensional -vector space. Thus, makes into a module .
Prove that in the invariant factors of is the least common multiple of all elementary factors.
For a module over a ring , define and prove that it is an ideal of .
Show that has a minimal polynomial, that is, and the polynomial is , with degree .
Jordan Normal Form
If our field is algebraically closed, that is, all polynomials over have roots in , which can be decomposed into a product of linear factors (such as ), then the matrix can be reduced to a simpler form. In this case, the irreducible polynomials over are all of the form , so must be of the form . We consider a more convenient -basis for : . In this basis, the action of is as follows: This shows that in this basis, has the following matrix representation on this subspace: Here the matrix is of size . So has the following matrix representation on with this chosen basis: This is called the Jordan normal form of . In particular, if , then is a first-order matrix with only diagonal elements.
Exercise 4.33. Prove that can be diagonalized over the field if and only if all elementary divisors are of first order. This is equivalent to the minimal polynomial of being able to be factored into a product of first-order polynomials over and having no repeated roots.
Exercise 4.34 (). Let be a finite field. How many -similarity equivalence classes are there in ?
The -decomposition of
In this section, we denote . How can we give a surjection from to ? Or in other words, how can we find a set of generators? In fact, when we give a basis of , has a matrix representation , and are a set of -generators of , which are also a set of -generators. Therefore, we consider the -surjection determined by Now to find the kernel of this mapping, we consider the matrix representation , and obviously we have Here is the standard basis, which gives us generators of . Therefore, we can construct a mapping whose image corresponds to , and in fact, this mapping is described by the matrix . Since , we find that is an -submodule of . Therefore, for any , it belongs to , and can be written as Note that , we know that all . This shows that is an -linear combination of , and we have proved that are indeed a set of generators of .
We also need to prove that is an injection, which means that is a linearly independent set over . To do this, let . We have This implies that . Then we find that . Since is a PID, the left ideal is a principal ideal, let it be . If , since is an integral domain, should contain polynomials of any degree, but the right side is a finite dimensional -space and only contains polynomials of finite degree, which is impossible. Therefore, , and we know that .
Corollary 4.2. We have the following short exact sequence of -modules where is the map determined by .
After having this basic exact sequence, we will examine how to specifically calculate the module structure of . Note that is a matrix over a PID, so there exist invertible matrices such that where , and denotes a diagonal matrix with these elements on the diagonal and elsewhere. Then we have the following commutative diagram
Here we need the following simple lemma
Lemma 4.2. Let be a (not necessarily commutative) ring, and let and be (let’s assume) left -modules. If we are given the following commutative diagram with -modules and -module homomorphisms (except for )
and both rows are exact, then we can uniquely construct an -module homomorphism such that the entire diagram commutes. Furthermore, if and are isomorphisms, then is also an isomorphism. (Essentially, this homomorphism is induced by .)
Proof. In fact, let and consider its preimage in . We map it to and define . It is necessary to verify that this definition does not depend on the choice of preimage . In fact, another preimage differs from by an element in , which is equivalent to an element in . Thus, we can denote the other preimage as , and its image in is . Therefore, the definition of does not depend on the choice of preimage . Here we use commutativity. It is easy to verify that is indeed an -module homomorphism. Uniqueness is obvious, since is uniquely determined by the commutativity of the diagram.
Now let us consider the case when and are isomorphisms, and show that is also an isomorphism. In fact, we can construct and , and define a commutative diagram as follows:
Then by the first part of the lemma, we can uniquely construct that commutes with the diagram. Note that is obviously a map that commutes with the first and third rows. Therefore, by uniqueness, , which implies that is an isomorphism. ◻
Now, since are invertible, obviously define an isomorphic mapping. From this lemma, we know that an isomorphism can be constructed from to , where Note that is also a -module isomorphism, and is a finite-dimensional -vector space, but is not a finite-dimensional -vector space, so , is a nonzero element in such that Of course, it is not necessary to prove that is isomorphic to the above form, only the structure theorem for finitely generated -modules is needed. However, the above process gives an explicit way to calculate the standard form of using the form of .
Exercise 4.35 (). Prove that, when the following commutative diagram of -module homomorphisms is given (where the rows are all short exact sequences)
a unique mapping can be constructed to make the diagram commute. If are both isomorphisms, then is also.
Exercise 4.36 (). Let be two fields, where is a subfield of . Prove that are similar over if and only if they are similar over .
Eigenvectors and Root Subspaces
In this section, we will discuss how to actually obtain a transition matrix such that is our standard form, or equivalently, . Let be a field (e.g. an algebraically closed field like ) such that all elementary divisors of are products of linear factors . We call the ’s that appear in these elementary divisors the eigenvalues of . By arranging the eigenvalues in order of their corresponding elementary divisors, we have For each eigenvalue , the subspace corresponds to a subspace of under this isomorphism, which we call the root subspace with respect to . It is given by The subspace is called the eigenspace with respect to , denoted by . The vectors in this subspace are called the eigenvectors of , 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 -basis for a submodule of the form , and we know that the projection of onto this submodule generates it. In other words, it has a basis , and we need to arrange the basis in this order to ensure that the matrix of is the Jordan form described earlier. Now if we find the image of under the isomorphism to , denoted by , then the -basis for this subspace can be written as .
If 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 . For a general , we need to find a basis for the root subspaces . Here are some examples to illustrate this.
Example 4.5. We consider the following matrix over the field : By performing elementary transformations on , we get: Thus, the rational canonical form of over is . In other words, there exists an invertible matrix over such that is similar to the above form. If we consider or (in fact, we only need ), then from , we obtain its elementary factors, and thus it is similar to the following diagonal matrix over : This is the Jordan canonical form of over any field that contains .
To find , consider its eigenspaces for the two eigenvalues , and . Using the algorithm for calculating described in the previous sections (or solving the equations directly), we can compute the generators of these two spaces, which are the eigenvectors , where for the corresponding eigenvalues. Therefore (note that does not need to be unique), satisfies , i.e. .
Example 4.6. Consider the following matrix over , transform it into Jordan canonical form , and find the corresponding such that . By performing elementary transformations on , we can calculate its invariant factors Thus, the elementary factors are , and . We then calculate and obtain the root subspace with the following basis (the basis is not unique and may differ from what others calculate) By applying to these vectors, we find that the first two vectors fall into , while the last one belongs to . Therefore, we let , which corresponds to the generator in , and its Jordan block corresponds to the basis . We also need another eigenvector that does not belong to the space generated by to correspond to the other elementary factor . It is clear that we can take .
Finally, by simply calculating the feature vector , we find an eigenvalue of and its corresponding eigenvector By arranging them in the order of and putting them into the matrix , we obtain the desired transition matrix
Exercise 4.37 (). In fact, in the calculation process of in the above example, we can also reduce the amount of calculation by the following means.
Let be a general linear map on an -dimensional space, and its minimal polynomial is of the form , where the two eigenvalues are distinct. Prove that
Here, returns to the in the previous example. By calculating the matrix and , find the eigenvector of , and use to show that is directly generated by the columns of , so there is no need to calculate and its kernel.
Exercise 4.38 (). The Fibonacci sequence is a unique sequence of positive integers determined by the initial conditions and the recurrence relation We can convert the above recurrence relation into matrix form Let the matrix be denoted as . By converting this matrix into Jordan canonical form over , we can easily calculate and derive the general formula for .
Exercise 4.39 (). Is there a matrix such that
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 -dimensional -vector space and a linear map . We consider an -linear alternating function on Here, -linear means that is linear in each variable , i.e. when fixing all other elements, is a -linear map. Alternating means that if two vectors are the same, e.g. , then the value of the function is . As a consequence, this implies that when we swap the positions of two vectors , the value of the function becomes the negative of its original value This is because , and using the -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 for , and consider the decomposition of in terms of this basis Then, by -linearity, we have Since requires no repeated elements in order to be non-zero, we only need to consider the case where forms a permutation of . Let us denote this permutation as . In this case, the permutation can be decomposed into a product of transpositions, and each transposition produces a negative sign for . Therefore, Thus, It is easy to verify that the above expression defines a function that satisfies -linearity and alternativity. Therefore, the desired function exists. However, its definition seems to depend on the choice of the value of and a basis for . In order to avoid the meaningless zero function, we choose . For any mapping , we consider which is called the determinant of . If we write the matrix decomposition as , according to the above formula, we know that this definition does not depend on the choice of the value of (as long as it is non-zero). Therefore, we can write the definition of the determinant for a matrix as This is equivalent to assuming that the value of , where are the columns of , is equal to when . Interestingly, the definition of the determinant for also does not depend on the choice of the basis ! To prove this, we only need to show that similar matrices have the same determinant. This is because the determinant is a multiplicative homomorphism:
Theorem 4.9 (Determinant is a multiplicative homomorphism). Fix a choice of basis for the vector space , and let be two matrices. Then,
Proof. Let the columns of from left to right be , then the th column of is . By using a similar alternating sum expansion as before, we have ◻
Proof. It is easy to see that , so for an invertible matrix , we have Therefore, for two similar matrices , their determinants are equal: In fact, the determinant has a clear meaning: it is a kind of signed volume function in -dimensional space, which describes the volume of the parallelotope formed by the vectors . The definition of this volume ultimately depends on the value of the "base volume" . Therefore, the determinant of is the "amplification factor" of the volume of the parallelotope formed by the base under the mapping of . This factor does not depend on the value of the "base volume". In other words, it describes the "size" of the linear mapping in a signed manner, which is independent of the choice of the base.
Exercise 4.40. Explain why the determinant can actually be defined for matrices in , where is a commutative ring.
◻
Exercise 4.41 (). In this problem, let be a matrix over a PID.
is invertible if and only if is a unit.
defines an injection if and only if .
if and only if .
Exercise 4.42 (). Let be a -linear map on an -dimensional vector space, and let be its matrix with respect to some basis. Prove the equivalence of the following statements:
.
The columns of span .
, i.e. is injective.
.
is not an eigenvalue of .
has no non-zero solutions.
is an invertible matrix and is an isomorphism.
Exercise 4.43 (). Let be a linear map on an -dimensional vector space over a field . Define the polynomial .
is an invariant of under similarity, and its roots are all eigenvalues of . Therefore, it is called the characteristic polynomial of .
Prove that is equal to the product of all invariant factors of , i.e. the product of all elementary factors.
Prove the Cayley-Hamilton theorem .
Tensor product
Let and be a right -module and a left -module, respectively. We can define an abelian group , where the elements are generated by symbols of the form . The zero element is , and it satisfies the following three constraints:
(Coefficient balance) ,
(Left linearity) ,
(Right linearity) .
That is, it is required that the symbol has bilinearity, and the elements in can freely pass through this symbol. Strictly speaking, this definition means that is a free -module generated by all symbols , modulo all relations generated by elements such as , etc. When we do not write out , either the context is clear about which base ring is taking the tensor product, or we are taking the tensor product over . Since any module can be viewed as a bi-module over , can always be defined.
Example 4.7. Let and be two -modules. Consider . This group is generated by all symbols of the form , where represents the residue class of the integer .
When , we have , so , which is the zero element in .
Similarly, when , .
When , we have , so .
Therefore, in this example, the tensor product . In fact, for coprime, we have .
Exercise 4.44. Observe the above example and answer: Is equivalent to at least one of being in ?
Although in general, the we define is just an Abelian group, similar to , when either or has a bimodule structure, we can give a module structure. Let’s give an example of how has a left -module structure. This is because we can define, for ,
Similarly, there are four possible cases, which we list in the following table:
Group |
Natural module structure |
Definition of -module structure |
|
-module |
none |
|
Left -module |
|
|
Right -module |
|
Exercise 4.45. Confirm that you understand all the situations in the table.
Example 4.8. Let be a left -module, and let be a coefficient extension homomorphism. Here, you can think of as a ring with larger coefficients, such as . Then, since can be viewed as a left -right -module, we can use tensor product to extend the -coefficients of to -coefficients, resulting in a left -module: The balancing relation can be understood as , since the right -module structure of is given by .
Theorem 4.10 (Universal Property of Tensor Product).
Let and be two -modules. Then any bilinear map can be decomposed as the composition of maps
where is a canonical map that depends only on and , and is the unique map that makes the above diagram commute.
Let and be two modules with right and left -module structures, respectively. Then similarly, any -bilinear map that is -balanced can be uniquely decomposed as .
According to the definition, , where is the free module generated by all abstract symbols , and is the submodule generated by all bilinear relations, Given a bilinear map , we can define a -linear map that satisfies uniquely. Its existence is guaranteed by the property of free modules. Since is bilinear, it is obvious that (because is on all generators of , we have ), so we can make a quotient map , which is the we need. The second part of the proposition is similar, and only requires minor modifications.
Corollary 4.3. Here, the left side corresponds to in the proposition, and the right side corresponds to the -balanced bilinear map .
Lemma 4.3. If are -vector spaces, then in , or .
Proof. is obvious. For , if are both non-zero, we can construct -linear functions such that . Then it is easy to verify that is a -balanced bilinear map, so it can be decomposed as . But is not , so . ◻
Exercise 4.46. Generalize the proposition to the case where are right and left -modules respectively. Here we need to add the appropriate assumption: and satisfy that any non-zero element has an -linear function that does not take zero on that element.
Example 4.9. Let be a field, and be two -vector spaces. Obviously, they are two bi--modules, so we can define a -linear space . If and are generated by bases and respectively, then is generated by the basis . It is obvious that this basis can generate the entire , the difficulty lies in showing that is linearly independent. Suppose there is a finite sum This implies that for any -balanced bilinear map , we have . Since is obviously a -balanced bilinear map, where represents the unique linear function on that takes the value on the basis and on all other bases, applying this function to gives us . Since and are arbitrary, this shows that all coefficients of are .
Exercise 4.47 ().
Can a natural linear mapping be defined if there are two linear mappings and ?
Let have bases respectively, and let have matrix representations with respect to the bases. Find the matrix representation of with respect to the natural bases of and respectively. You should be able to obtain the following form by arranging the bases in the appropriate order: If you change the order of the bases, you can obtain the following matrix form: As a corollary, these two matrices must be similar. Usually, we define the former as the matrix .
Dual Space
For an -module , we can define a dual module . Its module structure is given by the bi-module structure of , i.e. if is a left -module, then is a right -module, and vice versa. In the case where is a commutative ring, or a field, we do not need to distinguish between left and right modules, and is naturally an -module.
In the simple case of a -vector space , is called the dual space of . It can be understood as the vector space of all linear functions on . The interesting thing about the dual space is that it is a contravariant functor.
Theorem 4.11. The dual functor is a contravariant functor from left -modules to right -modules, meaning it maps a left -module to a right -module , and maps a left -module homomorphism to a right -module homomorphism . This correspondence satisfies the law of composition, meaning that the composition is preserved by the dual functor (but because it is a contravariant functor, the direction of composition is reversed):
Proof. In fact, this is a special case of the property of the Hom functor that we discussed earlier. Recall that it maps to , i.e. it pulls back the linear function on to the linear function on through . ◻
Dual basis
If has a basis, i.e. is a free module, then its dual module is . The latter is usually a larger module than , but if is finite, then and are isomorphic. In the case of vector spaces, this shows that the dual space of a finite-dimensional vector space has the same dimension as . 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 be generated by a basis . Then this basis is equivalent to an isomorphism , which maps the standard basis of to . Taking the dual functor of this mapping, we obtain By functoriality, is also an isomorphism. If we reverse the direction of , we get an isomorphism , which gives a basis for , called the dual basis of and denoted by .
Specifically, is defined such that its image under is the function on that takes the th coordinate, i.e. . This satisfies Substituting gives Here, is a symbol that equals when and 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 for all .
Matrix Representation of Dual Linear Mapping: Transpose
Let be a linear mapping between finite-dimensional vector spaces. After choosing bases and for and , respectively, we can represent as a matrix such that . Then, what is the matrix representation of the corresponding dual mapping under the dual bases and ? We can calculate and substituting gives This matrix is actually obtained by flipping all elements of along the main diagonal, i.e. rows become columns and columns become rows. This operation is called the transpose of , denoted as . Therefore, we have the following corollary:
Theorem 4.12. The matrix representation of the dual mapping under the dual bases is the transpose of the matrix representation of the original mapping under the original bases.
Corollary 4.4. Transposition reverses the direction of matrix multiplication, i.e. .
It is worth noting that the above reasoning does not require and to have the same dimension, and the transpose of a matrix can be applied to matrices of any shape.
Exercise 4.48 (). Let be a finite-dimensional vector space. Discuss how the dual basis changes when the basis changes. That is, if we have a basis and a new basis given by a coordinate transformation, , where is an invertible matrix. How can the corresponding dual basis be expressed in terms of ?
Double Dual
Although and are not naturally isomorphic when the vector space is finite-dimensional, it is remarkable that and are naturally isomorphic.
Theorem 4.13. Let be a finite-dimensional vector space. Then the map is a natural isomorphism that does not depend on the choice of basis. Here, represents the linear map that maps a function in to , i.e. the value of at .
Proof. It is easy to see that is an element of . We will prove that this mapping is an isomorphism. Firstly, is obviously a linear mapping, since it calculates the value of linear functions. To prove this, we only need to show that is an injection, because in the case of finite dimension, we know that .
If , we can always find a linear function such that (for example, by extending to a basis and then taking the dual basis ). In this case, , so as an element of , . This proves that is an injection, and thus proves the proposition. ◻
If is not finite-dimensional, is usually very large, but we still have the natural monomorphism mentioned above.
Field Extensions and Galois Theory