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 (x,y)(x,y), will bring the circle back to its original state. Reflecting an (equilateral) triangle about a symmetry axis, or rotating it by 120 degrees, will not change the triangle.

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

Essential Properties of Symmetry

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

  1. 1S(X).

  2. a,bS(X)abS(X).

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

  4. aS(X)there exists an inverse bS(X) for a, such that ab=ba=1.

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

Symmetric Group of an Equilateral Triangle

The symmetry of an equilateral triangle includes rotation and reflection. In fact, it has three different axes of symmetry, and we can take the reflection transformation with the vertical axis as the axis of symmetry as τ. There are also two different rotations σ,σ2=σ1 (one rotates 120 degrees counterclockwise, and the other rotates 120 degrees clockwise), and a symmetry 1 that does nothing. As before, we use 1, 2, 3 to denote the three vertices of the triangle (we can place the equilateral triangle flat, with the top vertex as 1, the bottom right vertex as 2, and the bottom left vertex as 3). So each symmetry is actually a mapping f from {1,2,3} to {1,2,3}. Don’t forget, as a symmetry, f needs to have an inverse, so f must be a bijection. How many such f are there? We only need to determine the values of f(1),f(2),f(3). There are 6 possible permutations, so there can be at most 6 symmetries on the triangle! How many does it actually have? Is each of these f a symmetry of the triangle? Indeed it is! We will use the following notation (123abc) to represent the mapping that maps 1 to a, 2 to b, and 3 to c. It is easy to see that σ=(123312)τ=(123132) 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 στ=(123312)

(123132)=(123321) 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}.) 1,σ,σ2,τ,τσ,τσ2 This group has good operational properties: it has an identity element 1, every element has an inverse, and the composition of any two elements (also known as the product of elements) still belongs to this group, meaning that the multiplication operation is closed. In fact, we generally refer to this group as D3, called the dihedral group. The term dihedral group actually includes a whole series of groups Dn, where Dn refers to the group of all symmetries acting on a regular n-gon. (Note: Some books use D2n to refer to what we call Dn here, this is just a difference in notation, unfortunately both notations are widely used.)

Another simple but important example of a group: permutation group

We consider the set {1,2,,n} and study its symmetries. What are the transformations acting on it? They are all the surjective maps from it to itself (must be surjective because symmetry transformations require an inverse). We denote this group as Sn, called the n-permutation group. The elements in it are called permutations. Sn={surjective map f:{1,2,,n}{1,2,,n}}. It is easy to see that |Sn|=n!. Permutation groups are of fundamental importance, so it is important to introduce simple and convenient notation for them. We still use f=(12nf(1)f(2)f(n)) to represent a permutation. In particular, we call a permutation with the following shape a cycle: (a1a2anb1bka2a3a1b1bk) We denote it as (a1a2a3an). There can be cycles with length less than n, such as (12) which represents a cycle that maps 1 to 2, 2 to 1, and leaves other elements unchanged.

Cycle Representation of Permutations

An interesting fact is that every permutation can actually be represented as a product (composition) of cycles! To obtain the cycle representation from a permutation, we simply do the following: it may map a1 to a2, a2 to a3, and so on until it maps some ak back to a1, then we have found a cycle (a1a2ak). Starting from an element not yet included in any cycle, we let f act on it repeatedly until it cycles, obtaining another cycle (b1b2bl), and so on. Eventually, we exhaust all elements of the permutation and obtain f=(a1a2ak)(b1b2bl) 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: (12344321)=(14)(23)=(23)(14) Simply by observing that 141, 232.

Exercise 1.1. Compute (12)(34)(13)(24) and write it as a product of disjoint cycles.

Exercise 1.2. Permutation: (1234534152)

Write as a disjoint cycle product.

The Essential Framework of Symmetry: Groups

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

  1. 1S(X).

  2. a,bS(X)abS(X).

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

  4. aS(X) there exists an inverse bS(X) such that ab=ba=1.

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

Definition 1.1. A group is a set G with an associated binary operation :G×GG called multiplication, satisfying:

  1. a,bGabG

  2. There exists an element eG (called the identity element) such that for any element aG, we have ea=ae=a.

  3. For any aG, there exists an element bG (called the inverse of a) such that ab=ba=e.

  4. Multiplication is associative, meaning that for any a,b,cG, we have (ab)c=a(bc).

In particular, if this operation also satisfies the commutative law, ab=ba, 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 for1, and it may be thought of as a set closed under some operation. Indeed, a group can also represent such a set closed under an operation, such as the set of all integers under addition. (In fact, such a set closed under an operation, such as the group of all integers under addition, is also a kind of symmetry transformation: it is all the translation transformations acting on the set of integers.) But please remember the origin of groups, and the most essential property of groups is symmetry. In this way, by studying all groups, we are essentially studying all possible symmetries that can act on any possible object.

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

Some Examples of Groups

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

If we take all the rotations in Dn, {1,σ,σ2,,σn1}, 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 Zn, calling it the nth cyclic group2, which is an Abelian group.

Regarding cyclic groups, there is actually another arithmetic description: all integers are divided into n different residue classes according to the modulus n, which are divided into n classes with remainders 0,1,2,,n1. Addition can be performed between residue classes, for example, in modulus 5, 2+4=1. In this way, these different residue classes form a group under addition, which seems different from the previous Zn because one is a rotation transformation {1,σ,σ2,,σn1} and the other is a residue class {0,1,2,3,,n1}. However, it can be seen that these two groups have no essential difference in structure, that is, if we identify residue class k with σk, any group operation on both sides is the same. This means that under a correspondence f f:{0,1,2,3,,n1}{1,σ,σ2,,σn1}kσk 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 nth roots of unity {1,e2πin,e4πin,,e2(n1)πin} 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 Zn?

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

Structural Information on Elements

Order of Elements

Let gG. If there exists a positive integer n such that gn=1, then we say that g is of finite order and we call the smallest such positive integer n the order of g. Otherwise, we say that g is of infinite order. For a finite group G, for any element gG, we can keep multiplying it to get the sequence g,g2,g3,. Since G is finite, this sequence will eventually repeat. Suppose gk=gl,k>l, then we have gkl=1. This means that every element in a finite group is of finite order.

Exercise 1.5. Let g be an n-order element in G and gN=1. Prove that N is a multiple of n.

Proposition 1.1. Let g be an n-order element in a group G. Then the order of gm is n(m,n), where (m,n) denotes the greatest common divisor of m and n.

Proof. First, from (gm)n(m,n)=gmn(m,n)=1, we know that the order of gm is n(m,n). And if (gm)k=1=gmk, then mk must be a multiple of n, which means k must be a multiple of n(m,n). This shows that the order of gm is exactly n(m,n). ◻

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

Exercise 1.6. Let G be an Abelian group, and let a,bG have orders m and n respectively. Then the order of ab is a factor of [m,n].

Exercise 1.7 (). In the above exercise, if m and n are relatively prime, prove that the order of ab is mn.

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

Exercise 1.8 (). Prove that if a group only has elements of order 1 and 2, then it is an Abelian group.

Exercise 1.9 (). Let G be a group of even order, then the equation g2=1 has an even number of solutions. Hence, there must be elements of order two in the group G.

Subgroups and Quotient Structures

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

Definition 1.2. Let G be a group, and let SG be a subset. If S satisfies the defining properties of a group under the multiplication operation of G, then S is called a subgroup of G. We denote this as SG.

We have many examples of subgroups, for example, the additive group of all even numbers 2Z is a subgroup of Z. Another example is Z6={1,σ,σ2,σ3,σ4,σ5} has subgroups {1,σ2,σ4} and {1,σ3}, which are actually Z3 and Z2.

Example 1.1. {1,(12)(34),(13)(24),(14)(23)} forms a subgroup of S4, called the Klein four-group, sometimes denoted as V or Z22. This group is abelian, but is not isomorphic to the abelian group of the same order, Z4.

Exercise 1.10. Prove that the intersection of (any) subgroups is still a subgroup.

Cosets and Lagrange’s Theorem

Let G be a group and let HG be a subgroup. We can define an equivalence relation on G as follows: aba1bH. It can be easily verified that this indeed defines an equivalence relation5, and according to this relation, the group G is partitioned into disjoint equivalence classes. It can be observed that the set of all elements equivalent to b is bH, since bab1aHabH. Thus, all the equivalence classes are of the form bH, and they all have the same size, which is |bH|=|H|. We call such subsets of G cosets of H, and we refer to them as left cosets6. We denote the number of cosets, or the index of the subgroup H, by [G:H]. We have G=i=1[G:H]biH Since the different cosets are disjoint, we have obtained

Theorem 1.1 (Lagrange’s Theorem). Let H be a subgroup of the group G. Then, |G|=[G:H]|H|

By continuously applying the coset decomposition, we can obtain

Exercise 1.11 (). Let ABG. Then we have [G:A]=[G:B][B:A].

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

Example 1.2. For the group D3={1,σ,σ2,τ,τσ,τσ2} and its subgroup H={1,σ,σ2}, we have the following coset decomposition: D3=HτH. In this case, [D3:H]=2.

Exercise 1.12. Let HG. Prove that gHgH=H, and hence abaH=bH.

Theorem 1.2. Let gG be an n-order element in a finite group G. Then n is a factor of |G|.

Proof. Since g is an n-order element, it is easy to verify that H={1,g,g2,,gn1} forms an n-order subgroup of G. Therefore, by Lagrange’s theorem, we know that n must be a factor of |G|. ◻

Quotient Groups and Normal Subgroups

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

Given HG, we try to view the set of cosets G/H={H,b1H,,bk1H} as a group, and the desired group operation is defined as: a,bG(aH)(bH)=(ab)H Unfortunately, for some subgroups H, this equation does not hold. In other words, not all subgroups can be used to construct the quotient group G/H. We reason as follows: (aH)(bH)=(ab)HHbH=bH(b1Hb)H=Hb1HbH, and for all b, b1HbH is equivalent to b1Hb=H for all b. Therefore, in order to construct the quotient group G/H, the subgroup H must satisfy the condition: bG,b1Hb=H, which leads to the following definition:

Definition 1.3. Let NG, if gGg1Ng=N then N is a normal subgroup of G, denoted as NG. If a group G has no other normal subgroups except for 1 and G, it is called a simple group.

Example 1.3. If G is an Abelian group, then any subgroup of G is a normal subgroup.

Example 1.4. We have Z3D3, which can be verified by showing τ1στ=σ1. It is easy to see that {1,τ} is a subgroup of D3, but it is not a normal subgroup of D3 because σ1τσ=σ2τ{1,τ}.

Example 1.5. We have {1,(12)(34),(13)(24),(14)(23)}=VS4. 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, ABC does not imply AC. A counterexample will be given in the later study.

Exercise 1.13. Let NHG and NG. Prove that NH.

Exercise 1.14. Proof: NG is equivalent to saying that for any gG, Ng=gN.

Exercise 1.15 (). Assume M,NG and MN={1}. Prove that the elements of M and N commute with each other. That is, for any mM and nN, mn=nm.

Exercise 1.16 (). Let HG and [G:H]=2. Prove that HG.

Exercise 1.17 (). Find all finite simple groups.

Product of Subgroups

Let N,HG. We define the set NH={nh|nN,hH}G. Under the operation defined on the larger group G, can this set form a group? The answer is not always. However, this is true when at least one of N or H is a normal subgroup. Without loss of generality, let NG. We calculate n1h1n2h2=n1(h1n2h11)h1h2NH (n1h1)1=(h11n11h1)h11NH 1NH The associativity of the group NH is inherited from the associativity of the larger group, so in this case, NH forms a subgroup.

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

Proposition 1.2. Let A,BG, then |AB|=|A||B||AB|

Exercise 1.18 (). Let A,BG. Prove that [G:AB][G:A][G:B]. In particular, if [G:A] and [G:B] are coprime, prove that the equality must hold and G=AB.

Exercise 1.19 (). Let A,BG be subsets (note that it is not said that they are subgroups). If |A|+|B|>|G|, prove that G=AB.

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 G,H be groups, and f:GH be a mapping. If f(ab)=f(a)f(b) then f is called a group homomorphism or group mapping, and is simply called a homomorphism. If f is an injection, it is called a monomorphism. If f is a surjection, it is called an epimorphism. If f is both a monomorphism and an epimorphism, it is called an isomorphism, and G and H are called isomorphic, denoted by GH.

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

Example 1.6. As in Chapter 1, by numbering the vertices of a triangle, we find that in fact S3D3. However, for n>3, Sn is not the same as Dn.

Example 1.7. A group is isomorphic to itself. This can be achieved by taking f(g)=g. Interestingly, a group can have isomorphisms other than the identity map, such as the map f:Z3Z3gg2. This is an isomorphism, but it is different from the identity map. We call these (including 1) the automorphisms of Z3. In fact, the existence of such (non-trivial) isomorphisms shows that the structure of the group G itself has a certain symmetry, and all automorphisms of G, which are all the symmetries acting on G, also form a group, called the automorphism group of G, denoted by Aut(G).

Exercise 1.20. Verify that a homomorphism must map 1 in G to 1 in H, and map g1 to f(g)1, i.e. f(1)=1 and f(g1)=f(g)1.

Exercise 1.21. Verify that Z4 has a subgroup of order 2, and prove that the quotient group of this subgroup is isomorphic to Z2.

Exercise 1.22. Let g be an n-order element, prove that f(g) must be a finite-order element, and its order is a factor of n.

Exercise 1.23. Find Aut(Z4).

Definition 1.5 (Kernel and Image). Let f:GH be a group homomorphism. We define the set kerf=f1(1)={gG|f(g)=1} as the kernel of f, and the set Imf={f(g)|gG} as the image of f.

It is worth noting that kerf and Imf are subgroups of G and H, respectively, and in fact kerfG.

Exercise 1.24. Prove that

  1. kerf={1}f is injective.

  2. kerfG.

Find all groups with order 5. Including the trivial group with only one element, there are a total of 6 groups with order not exceeding 5. (Isomorphic groups are considered the same)

Simple, important and typical group homomorphisms

Monomorphism

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

Example 1.8. Consider the monomorphism of groups f:Z3={1,a,a2}Z6={1,b,b2,b3,b4,b5} It is easy to see that this homomorphism is completely determined by the value of f(a), since f(1)=1 and f(a2)=f(a)2. Since a is a 3-order element, f(a) must be a 1-order or 3-order element. The 3-order elements in Z6 are only b2 and b4. Therefore, we know that f(a) can only take 1,b2,b4. Since we only consider monomorphisms, there are only two possible choices left: f(a)=b2 or f(a)=b4.

If f(a)=b2, then we have f(a2)=b4, and the entire group Z3={1,a,a2} is mapped to {1,b2,b4}. If we choose f(a)=b4, then we have f(a2)=(b4)2=b8=b2, and the entire group Z3={1,b4,b2}. We know that {1,b2,b4} is a subgroup of Z6 isomorphic to Z3, but there are two different ways to embed Z3 into Z6. However, in either case, this monomorphism establishes an isomorphism between H and f(H). Although there is only one subgroup isomorphic to H=Z3 in G=Z6, there are multiple ways to embed H into f(H) because there exists an automorphism from H to H mapping (1,a,a2) to (1,a2,a). In other words, this phenomenon occurs because of the symmetry inherent in H itself. rendering math failed o.o

Projection and Homomorphism Decomposition

Another simple and important mapping is projection. As we have mentioned, for a normal subgroup N of a group G, we can construct the quotient group G/N. We can consider a natural mapping that maps an element g in G to the coset in G/N that contains g: p:GG/NggN This mapping is obviously a homomorphism, since p(ab)=abN=aNbN=p(a)p(b). It is also a surjective homomorphism. What is its kernel? Recall that the identity element in G/N is N, which is the coset containing the identity element in G. Therefore, p(a)=aN=NaN, and we conclude that kerp=N.

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

In other words, we find that any homomorphism f:GH with kernel kerf can be decomposed into the composition of two mappings: rendering math failed o.o This diagram means that we can map a to f(a) in two steps: aakerff(a). The first step is to map a to the coset akerf it belongs to (i.e. the natural projection from G to G/kerf), and the second step is to map akerf to f(a). The only potential issue is whether the second step is a homomorphism. The answer is yes. It is easy to verify this. Any group mapping can be decomposed into the composition of two basic mappings: a projection and an injective homomorphism. By the way, we can add one more step, which is the most trivial one: aakerff(a)f(a), which first maps f(a) to the subgroup Imf of H, and then maps Imf to H through the trivial injective mapping. rendering math failed o.o Thus, the second step G/kerfakerff(a) 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 f:GH is a homomorphism, then kerfG, ImfH, and there exists an isomorphism G/kerfImf

Proof. As above, we construct a mapping h:G/kerfImfakerff(a) It is easy to verify that this mapping is well-defined, since f(b)=f(a) whenever bkerf=akerf. Now we prove that this is a homomorphism: h((akerf)(bkerf))=h(abkerf)=f(ab)=f(a)f(b) The first equality holds because kerf is normal. h is injective, since h(akerf)=f(a)=1akerf. Moreover, h is surjective, so h 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 NG and HG. Then NNH and NHH, and NH/NH/NH

Proof. Since NG and NNHG, it is easy to see that NNH. For any nNH and hH, we have h1nhNH Therefore, NHH. Now, we construct a mapping f:HNH/NhhN We first prove that this mapping is a homomorphism. Since NNH, we have f(ab)=abN=aNbN=f(a)f(b). This is clearly a surjective homomorphism. Now, we calculate kerf. Let hkerf, then hN=NhNhNH Hence, kerf=NH. By the first isomorphism theorem, we have H/NHNH/N. ◻

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

Theorem 1.5 (Corresponding Theorem). Let NG, and let ρ:GG/N be the natural projection. Then there exists a one-to-one correspondence between all subgroups of G that contain N and all subgroups of G/N: Hρ(H)=H/NG/N This maps H to all coset sets of the form hN. The inverse map is Tρ1(T), where T is a subgroup of G/N.

Proof.

  • Note that the image of HGG/N is H/N, which is the image of a homomorphism, and therefore is a subgroup of G/N. Similarly, for any subgroup TG/N, the preimage ρ1(T) is also a subgroup.

  • Now we only need to verify that these two mappings are inverse mappings, i.e. ρ1(ρ(H))=H and ρ(ρ1(T))=T. The latter is obvious since ρ is surjective. For the former, suppose there is a coset decomposition H=hN, then ρ1(ρ(H))=ρ1(ρ(h))=hN=H.

 ◻

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 Zn can be described in various ways, such as the rotation transformation group of a regular n-gon, or the additive group of residue classes modulo n. The essential characteristic of a cyclic group is that it can be generated by a single element. This means that we can find an element a, and by repeatedly taking inverses a1 and multiplying 1,a,a2,a3,, we can obtain all elements in the group G. To make this clearer:

Definition 1.6. Let G be a group, and SG be a subset of G. The intersection of all subgroups of G that contain S, also known as the smallest subgroup containing S, is called the subgroup generated by S, denoted by S. If G=S, then G is called a group generated by S, and S is called a set of generators for G. If a group can be generated by a single element, i.e. there exists aG such that G=a, then it is called a cyclic group.

According to this definition, in addition to the finite cyclic group Zn, there can be infinite cyclic groups, which are essentially Z.

Therefore, the cyclic group Zn can be imagined as a group generated by the abstract letter a, satisfying the relation an=1. This method of describing a group using generators and constraints is called group presentation. In this example, we write it as Zn=a|an=1.

Example 1.9. Similarly, we can imagine that the group D3 can be abstractly described as a group generated by the abstract letters σ and τ, satisfying the constraints σ3=τ2=1 and στ=τσ1. Let’s try to list a series of elements generated by these two letters: 1,σ,σ2,τ,τσ,τσ2 In the special case of the group D3, any element generated by abstract letters, such as στσ2, can be written in the above form, i.e. in the form of τiσj. This is because στσ2=τσ1σ2=τσ. We write this as D3=σ,τ|σ3=τ2=(στ)2=1 (The condition στ=τσ1 can be simplified to (στ)2=1). This can be easily generalized to the definition of Dn Dn=σ,τ|σn=τ2=(στ)2=1. 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 στσ1τστ1.

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

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

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

Theorem 1.6. Let G be a finite group. If for any factor d of |G|, there is at most one d-order subgroup in G, then G is a cyclic group. The converse is also true.

Proof. Note that any gG has a cyclic subgroup g generated by it. By assumption, there is at most one subgroup of this order. For d|n, if there is a cyclic subgroup of order d, then let its set of generators be denoted as gen(d), otherwise, let gen(d) be the empty set. Since any gG is a generator of some cyclic group of order d, we have G=d|ngen(d) and a cyclic group of order d has φ(d) generators, thus nd|n|gen(d)|d|nφ(d)=n We find that the equality holds, so for each d|n it has exactly one cyclic subgroup of order d, which is also true for d=n, 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 F× of a field F 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 αSn can be written as a product of disjoint cycles β1,,βk: α=β1βk. Moreover, this decomposition is unique up to the order of the cycles.

Proof. Assume that α has two disjoint cycle decompositions α=(α11α1k1)(α21α2k2) α=(β11β1l1)(β21β2l2) If α moves α11, then α11 will appear in one of the cycles in the other decomposition, let’s say β11=α11. By repeatedly applying α to α11, we get α11=β11, α12=β12 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 (123)(45) and (234)(15) have the same cycle structure, only the numbers are different. We say their cycle structure is 23. Similarly, if the cycle decomposition of α has mk cycles of length k, we say its cycle structure is 2m23m3kmk.

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

Definition 1.7. For a,bG, if there exists gG such that a=g1bg we say a and b are conjugate in G. It can be verified that conjugation is an equivalence relation. Elements that are only conjugate to themselves7 are called central elements, and all central elements are denoted by C(G) or Z(G), and are called the center of the group G.

Exercise 1.27. Prove that the number of conjugacy classes of a group G is equal to |G| if and only if G is an Abelian group.

Exercise 1.28. Let gG be a fixed element. Verify that the conjugation map fg(a)=gag1 is an automorphism of the group G.

Exercise 1.29 (). Continuing from the previous exercise, we have a mapping from G to Aut(G): i:GAut(G)gfg Verify that this is also a group homomorphism. Prove that keri=Z(G), and thus conclude that Z(G) is a normal subgroup of G.
Let Imi=Inn(G)Aut(G), and call it the inner automorphism group of G. By the fundamental homomorphism theorem, we have: Inn(G)G/Z(G).

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

Proposition 1.4. If G/Z(G) is a cyclic group, then G is an Abelian group.

Proof. Let a be a generator of the cyclic group G/Z(G) in G, and we can construct a coset decomposition of G with respect to Z(G) as follows: G=i=0n1aiZ(G) Thus, every element can be written as aiz, and it is obvious that aiz1ajz2=ajz2aiz1. ◻

Exercise 1.30 (). Prove that if Aut(G) is a cyclic group, then G is an Abelian group.

Exercise 1.31 (). Let |G|=p2, where p is a prime number. Prove that G is an Abelian group.

Exercise 1.32 (). Let αAut(G), and let I={gG|α(g)=g1}. Prove that if |I|>34|G| then G 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 Sn.

Exercise 1.33 (). Find the number of conjugacy classes in D5.

Exercise 1.34 (). Let p>2 be a prime number. Find the number of conjugacy classes in Dp.

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

Exercise 1.35. Think carefully about the above statement and prove that {1,(12)(34),(13)(24),(14)(23)}S4.

Exercise 1.36 (). Observe {1,(12)(34),(13)(24),(14)(23)}S4. Explain why normal subgroups do not have transitivity.

Exercise 1.37 (). We call HG a characteristic subgroup of G if every automorphism α of G maps elements of H to elements of H. Prove that if HNG and H is a characteristic subgroup of N, then HG. In other words, the characteristic subgroup of a normal subgroup is still a normal subgroup.

Exercise 1.38 (). Let p be the smallest prime factor of |G|. Prove that if there exists a p-subgroup AG, then AZ(G).

Parity of Permutations

Permutations can be classified as odd or even, denoted by the symbol sgnσ: odd permutations are 1, while even permutations are 1. The symbol sgnσ 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: 1ijn(Xσ(j)Xσ(i))=sgnσ1ijn(XjXi). Any permutation can be decomposed into a product of transpositions, as any cycle can be decomposed into a product of transpositions, i.e. (12k)=(1k)(1,k1)(13)(12). We can also define the parity of a permutation as the parity of the number of transpositions it can be decomposed into. It can be proven that the parity of the number of transpositions in a permutation remains unchanged. According to this definition, a transposition (12) is an odd permutation, while transpositions of odd length, such as (123) and (12345), are even permutations.

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

Lemma 1.1. For any transposition τ, we have sgn(τσ)=sgn(τ)sgn(σ)=sgn(σ).

Proof. If τ=(ab) 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 (ab)(ac..d)=(ac..db) The length of (ac..db) increases by 1 relative to (ac..d), so the sign changes. If there are two intersecting elements, consider (ab)(abc..d)=(ac..d) The sum of the lengths of the cycles decreases by 1, and the right side has one less (abc..d) than the left side. For the other case, (ab)(ac..dbe..f)=(ac..d)(be..f) The sum of the lengths of the cycles decreases by 1, and the right side has one less (ac..dbe..f) than the left side. Therefore, we immediately obtain the proposition. ◻

Theorem 1.7. sgn:Sn{1,1}Z2 is a homomorphism.

Proof. By Chapter 1, let α=τ1τ2τk be the decomposition of α into transpositions. Then sgn(αβ)=sgn(τ1τ2τkβ)=sgn(τ1)sgn(τ2τkβ)=sgn(τ1)sgn(τk1)sgn(τk)sgn(β)=sgn(τ1)sgn(τk1τk)sgn(β)=sgn(τ1τ2τk)sgn(β)=sgn(α)sgn(β). The kernel of the homomorphism sgn is denoted as An, called the n-element alternating group, which is the group of all even permutations. As a corollary, AnSn.

Exercise 1.39. Determine the parity of the permutation (132)(421)(12345) and the permutation (12n1nnn121)

 ◻

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 S4 into conjugacy classes and find all its normal subgroups.

Exercise 1.42 (). Prove that A2n has a subgroup isomorphic to Sn.

Direct Product

We can construct new groups using old groups, and one very simple construction is the direct product. Let G1 and G2 be groups, and we want to give the Cartesian product G1×G2 the structure of a group. The simplest way to do this is to define the multiplication as component-wise multiplication, that is, (g1,g2)(h1,h2):=(g1h1,g2h2). This way, the identity element in the group is (1,1), and the inverse of (g,h) is (g1,h1). We will denote this group as G1×G2. If G1 and G2 are both abelian groups, this construction is sometimes denoted as the direct sum G1G2, with the group operation denoted by addition.

Exercise 1.43. Investigate the group Z2×Z2 (also denoted as Z2Z2) and prove that it is isomorphic to V={1,(12)(34),(13)(24),(14)(23)}.

Exercise 1.44 (). Prove that D6D3×Z2. In fact, for any odd number n, we have D2nDn×Z2.

Exercise 1.45 (). Prove that when m,n are coprime, we have Zm×ZnZmn

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: Zn{rotation group of a regular n-gon} where the generator of Zn is mapped to a unit rotation. This action can also be described as follows: interpreting the rotation of a regular n-gon as a permutation on the set of vertices {1,2,,n}, we get a (mono)morphism: ZnSn where the generator of Zn is mapped to the cycle (123n). To study the most general actions of a group, we consider a homomorphism from the group G to the largest possible class of transformation groups. The two main classes of transformation groups that are usually considered are permutation groups and matrix groups. The study of homomorphisms to matrix groups is known as group representation theory. When studying the action of a group on a set, we mainly focus on homomorphisms to permutation groups. We denote the set of all permutations on a set X by Sym(X)8, which consists of all bijective mappings, and is called the symmetric group of X. Then, we define an action of a group G on a set X as a homomorphism (not necessarily injective or surjective): α:GSym(X). This is also known as a permutation representation of the group G, or simply a representation. In other words, α(g) becomes a transformation (permutation) on the set X, which is bijective, i.e. α(g):XX. This transformation can act on an element xX to give α(g)(x). This notation is more rigorous, but it is too long. After defining the homomorphism α, we can imagine G as a set of "operators", and simply use gx to represent α(g)(x).

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 xX, the set Gx={gx|gG} is called the orbit of x. It can be easily shown that if a,b belong to the same orbit, i.e. there exists g such that a=gb, then this is an equivalence relation, closely related to the fact that G is a group. As a result, the elements in X are partitioned into disjoint classes, i.e. the union of disjoint orbits. If X has only one orbit, we say that the action is transitive, meaning that any x can be mapped to any given y by some element in G.

Orbit Formula

Definition 2.1. Given a group G acting on a set X, we define Stab(x)={gG|gx=x} to be the subgroup of G that keeps x fixed. This is called the stabilizer of x.

Exercise 2.1 (). There is a stronger concept than transitivity, called doubly-transitive, which means that for any xy,zw, there exists gG such that (gx,gy)=(z,w). Prove: G is doubly-transitive on X if and only if for all xX, Stab(x) is transitive on G{x}.

Since Stab(x) is a subgroup, we can make a coset decomposition G=igiStab(x) where each coset acts on x in the same way, i.e. gix. Moreover, different cosets give different actions on x, otherwise ax=bxa1bStab(x)aStab(x)=bStab(x). We immediately obtain the following simple but fundamental orbit formula (for calculating the length of an orbit)

Theorem 2.1 (Orbit formula). |Gx|=[G:Stab(x)]

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

Example 2.1. We calculate |Dn|. Take a vertex x of a regular n-gon, since the action is transitive, |Gx|=n. And there are only two transformations in Dn that keep x unchanged, the identity transformation and a reflection (axisymmetric) transformation. Therefore, |Dn|=|Gx||Stab(x)|=2n.

Exercise 2.2 (). Calculate the order of the symmetry group of a regular tetrahedron.

Example 2.2. Let H,KG,aG, we calculate the number of elements in the following double coset set HaK={hak|hH,kK}. Consider the following action of H×K on G: ρ:H×KSym(G)(h,k)(ghgk1) It is easy to see that HaK is the orbit of a under this action. Therefore, by the orbit formula, |HaK|=[H×K:Stab(a)]. We consider (h,k)Stab(a)hak=ah=ak1a1HaKa1. Hence, |HaK|=|H||K||HaKa1|.

In addition, we can immediately obtain the following formula for calculating the number of orbits. For any subset SG of G, we introduce the notation XS={elements of X fixed by all elements of S}. Then we have

Theorem 2.2 (Burnside). The number of orbits N has the following formula9 N=1|G|gG|Xg|.

Proof. Let N=xX1|Gx|. N=xX1|Gx|=xX|Stab(x)||G|=1|G|xXgG1gx=x=1|G|gGxX1gx=x. ◻

Exercise 2.3 (). If G acts transitively on X and |X|>1, then there exists gG without a fixed point.

Exercise 2.4 (). Let G be a group of order pk. Prove that if G acts on a set X, then |XG||X|modp.

Kernel of Representation

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

What is kerα? It is the set of all elements g that fix every element, so kerα=xXStab(x). If this action is transitive, then kerα=gGStab(gx). There is a natural relationship between Stab(x) and Stab(gx). The transformations that fix x can also be used to fix gx by slightly modifying them. This only requires composing with g1, applying Stab(x), and then composing with g. In other words, we find that gStab(x)g1Stab(gx). Similarly, we have g1Stab(gx)gStab(x). Therefore, we find that Stab(gx)=gStab(x)g1. Thus, when the action is transitive, we have kerα=gGgStab(x)g1. This is a normal subgroup. This fact also suggests the following trivial proposition: for HG, we have gGgHg1G.

Common Actions

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

Conjugation Action

The group G acts on itself by conjugation, i.e. α:GSym(G)x(gxgx1)

Exercise 2.5 (). Can we define the conjugation action as α:GSym(G)x(gx1gx) 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 kerα=Z(G). For gG, its stabilizer Stab(g) is denoted as CG(g)={hG|gh=hg}10, which is a subgroup of G. We call the orbit equation in this case |G|=i[G:CG(gi)] the class equation of the group G. It is worth noting that some elements gG may have orbit length of 1, which means they are only conjugate to themselves, central elements, Z(G). If we let |G|=pn, where p is a prime number, then we have pn=|Z(G)|+i,giZ(G)[G:CG(gi)] It is easy to see that [G:CG(gi)] must be a multiple of p. Therefore, in this case, |Z(G)| must be a multiple of p, which means |Z(G)|>1. In other words, we have the following conclusion:

Proposition 2.1. If |G|=pn,n>1, then G has a non-trivial center Z(G).

Exercise 2.6 (). If we denote the number of conjugacy classes of a group G by c(G), prove that c(G×H)=c(G)c(H).

Exercise 2.7 (). With the notation as above, suppose G is a non-Abelian group. Prove that c(G)58|G|

Exercise 2.8 (). Can the equality hold? Furthermore, prove that if p is the smallest prime factor of |G|, then c(G)p2+p1p3|G|

Regular Representation (Action)

The group G acts (on the left)11 by multiplication on the group G, i.e. α:GSym(G)g(aga) This naturally views g as a permutation on G, α(g). 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 G be a group of order 4k+2. Then it must have a normal subgroup of index 2.

Proof. Consider the left regular action of the group α:GSym(G) Since this is a faithful representation, we can identify G with α(G). Then, each α(g) is a permutation on G, and due to the existence of inverses in group multiplication, this permutation cannot fix any element in the group (ga=ag=1.) Therefore, we can write α(g) as a product of some disjoint cycles of length greater than 1. Now, take g to be an element of order 2 in the group, which we know exists in groups of even order. Thus, α(g) decomposes into a product of 2n+1 disjoint transpositions, and is therefore an odd permutation. This proves that there is an odd permutation in G, and thus all even permutations in G form a normal subgroup of index 2. ◻

Corollary 2.1. Let k1, then a group of order 4k+2 is not a simple group.

Induced Representation (Action on Cosets)

Given a subgroup H of a group G, there is a (left) coset set G/H, and G can naturally act on G/H. α:GSym(G/H)g(aHgaH) This is called the (left) induced representation12. It is obviously transitive. Its kernel is kerα=gGgHg1 and note that kerαH. Using this representation, we can obtain many powerful (actually simple) conclusions.

Example 2.3. Let H be a proper subgroup of an infinite group G with finite index, then G must have a proper normal subgroup with finite index.

Proof. Consider the induced representation of G on the coset G/H: ρ:GSym(G/H) Since [G:kerρ]|Sym(G/H)|=[G:H]! is finite, we have completed the proof of the proposition. ◻

Here is another typical application:

Proposition 2.3. Let p be the smallest prime factor of |G|. If HG and [G:H]=p, then HG.

Proof. Consider the induced representation α:GSym(G/H) on the coset set G/H. Since G/kerα is isomorphic to a subgroup of Sym(G/H), it must be that |G/kerα| is a factor of [G:H]!. Now, since kerαH, we have |G/kerα|=|G||kerα|=|G||H|[H:kerα] which is a multiple of [G:H]=p. Since p is the smallest prime factor of |G|, we know that [H:kerα] is a multiple of 1 or p. If it is not 1, then p2|p!, which is impossible. Therefore, H=kerαG. ◻

Exercise 2.10 (). Let G be a non-Abelian group of order greater than 3, and HG. Prove that [G:H]>4.

Proof. Let p be a prime factor of |G|. Then, by the orbit-stabilizer theorem, we have that |G|=|Gx||Gx|, where Gx is the orbit of xG and Gx is the stabilizer of x. Since |G| is divisible by p, we have that p divides |Gx||Gx|. Since p is prime, this implies that p divides either |Gx| or |Gx|. If p divides |Gx|, then by Lagrange’s theorem, there exists an element of order p in Gx. If p divides |Gx|, then by the induction hypothesis, there exists an element of order p in Gx. In either case, we have that G contains an element of order p, as desired. ◻

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

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

Proof. Let X={(g1,g2,,gp)|g1g2gp=1}, and let a be a generator of the group Zp. Consider the following action of the group Zp on X: α:ZpSym(X)af Where f:XX is a mapping that maps (g1,g2,,gp) to (g2,g3,,gp,g1).

We need to verify that g2g3gpg1=1, which can be obtained from ab=1ba=1. Now, from the orbit equation |G|p1=|X|=|{gG|gp=1}|+|other orbits of length p| We can conclude that |{gG|gp=1}| is a multiple of p, and since 1p=1, we immediately know that there exists a p-order element in the group G, and there are at least p1 of them. In fact, we can obtain a stronger conclusion: (p-order element count+1) is a multiple of p. ◻

Exercise 2.11 (). Let |G|=mp,1<m<p, where p is a prime number. Prove that ZpG.

Exercise 2.12 (). Let G be an Abelian group of order 6. Prove that GZ6 using the following hints. (By Cauchy’s theorem, G has elements of order 2 and 3. Hence, GZ2×Z3Z6.)

Exercise 2.13 (). Let G be a non-Abelian group of order 6. Prove that GS3 using the following hints. Hence, there are only two groups of order 6: Z6 and S3.

  1. First prove that Z(G)=1.

  2. Prove that G has exactly 3 elements of order 2.

  3. Consider the conjugation action of G on the set X={a,b,c}, where a,b,c are all elements of order 2. (You need to prove that this is an action on X first.)

  4. Prove that {a,b,c} generates G, and hence the above action is faithful. The first isomorphism theorem gives GS3.

Conjugation on Subgroups

Let AG be a subgroup. It is easy to see that g1Ag is also a subgroup. This is because the mapping xg1xg is an automorphism, and when restricted to a subgroup, it remains an isomorphism, thus its image must be a group. We say that subgroups A and B are conjugate if A=g1Bg. It is clear that G can act on some of its subgroups by conjugation. A subgroup can have many conjugate subgroups, and the normal subgroups of G are those that are invariant under the conjugation action of G, meaning they are only conjugate to themselves. In this case, they form a conjugacy class on their own.

For SG, we use the notation NG(S) to denote {gG|gS=Sg}, which is called the normalizer of S. It is easy to see that the stabilizer of AG is NG(A), and thus the size of the conjugacy class is [G:NG(A)].

Exercise 2.14 (). Let |G|=pn. Prove that the number of non-normal subgroups of G is a multiple of p.

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 (62)=6×52=15 ways to do so. However, many of these ways are actually the same, differing only by a rotation. In other words, when painting a symmetric object, we only need to consider its symmetry group and let this group act on all possible sets of colors. To determine if two ways of painting are the same, we just need to see if they are in the same orbit. Therefore, to find the number of essentially different ways to paint, we just need to count the number of orbits! Burnside’s theorem provides a method for doing so.

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

  1. σ(a1,a2,,an1,an)=(a2,a3,,an,a1)

  2. τ(a1,a2,,an1,an)=(an,an1,,a2,a1).

It is easy to see that since all elements in Dn can be represented in the form of σiτj, it is only necessary to define the actions of σ and τ on X. It can be easily verified that the above definition indeed gives an action of Dn on X (it is necessary to verify that the actions of σn=τ2=(στ)2=1 are trivial). Therefore, our problem is now equivalent to calculating the number of orbits in X, denoted by N. By Burnside’s theorem, N=1|Dn|gDn|Xg|. Now let’s consider the size of Xg. First, Dn can be viewed as a subgroup of Sn, and it actually acts on X in the same way as the permutation with subscripts. Therefore, we can assume that gDn has a disjoint cycle decomposition in Sn: g=c1c2ck=(c11c12c1l1)(c21c22c2l2) where ci=(ci1ci2cili) are disjoint cycles with lengths li. For example, σ=(123n), τ=(1,n)(2,n1).

If g fixes an xX, i.e. gx=x, we can obtain x=(a1,a2,,an)=(ag(1),ag(2),,ag(n)) i.e. ai=ag(i). From gx=x, it naturally follows that gkx=x, thus ac11=ac12==ac1l1. This means that in all components of the cycle c1, the corresponding positions must have the same color. Similarly, the same result can be obtained for all cycles, thus |Xg|=cgnumber of cycles, note that when considering cycles, the identity cycle 1 must be included.

Note that the cycle decomposition shape of elements in the same conjugacy class of Dn is the same. In general, it is only necessary to find all conjugacy classes of Dn and calculate their cycle decomposition. In this example, we can consider Dn={1,σ,σ2,,σn1,τσ,τσ2,,τσn1} Note that σj(τσi)σj=σjτσij=τσi2j, thus when n is odd, all τσi are conjugate, and like τ, they have n12+1=n+12 cycles. When n is even, it may be divided into two conjugacy classes τσ2k+1 and τσ2k, which have n2 and n2+1 cycles, respectively, just like τσ and τ.

For elements in ZnDn, σk is a cycle of length n when k and n are coprime. When their greatest common divisor (k,n)=d, it is a product of d cycles of length nd. Recall that in the section on cyclic groups, we mentioned that for factors of n, the number of generators of the subgroup of order nd, dZnZn, which are elements σk satisfying (k,n)=d, is equal to the Euler’s totient function φ(nd). Therefore, we can now derive the formula for N: N=1|Dn|gDn|Xg|=12n(k=1nc(k,n)+12|nn2cn2+12|nn2cn2+1+12|n+1ncn+12)=12nd|nφ(nd)cd+12|ncn2(c+1)4+12|n+1cn+122.

Exercise 2.15 (). Assuming that on a necklace of length 2n, only two colors are allowed and each color must use exactly n 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 G be a group with |G|=mpn, where p is a prime and pm. Then:

  1. There exists a subgroup PG of order pn, called a Sylow-p subgroup of G.

  2. Let N(pr) denote the number of subgroups of G of order pr, for rn. Then N(pr)1modp.

  3. All Sylow-p subgroups are conjugate to each other, so N(pn)=[G:NG(P)].

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

Proof. Let |G|=npr (without the requirement that n and p are coprime, i.e. r is not necessarily maximal). We consider all pr-element subsets of G, denoted by X, with |X|=(nprpr). Now we can consider the left action of G on X: ρ:GSym(X)g(SgS) We decompose X into a union of orbits: X=i=1mXi with |Xi|=[G:Stab(Si)]. Since Stab(Si)Si=Si, we can decompose Si=j=1kiStab(Si)gij which implies ki|Stab(Si)|=pr and |Xi|=nki. Note that ki must be a power of p, and ki=1 if and only if Si is of the form Pg, where PG is a pr-element subgroup of G and gG. Thus ki=1 if and only if Ti contains exactly one pr-element subgroup, which implies |X|=(nprpr)=i=1mnkinki=11modnp. Hence 1n(nprpr)N(pr)modp.

Now we only need to calculate the remainder of the left number p. First, it is equal to (npr1pr1), so it is equal to the coefficient of the pr1th term of the expression (1+x)npr1. Considering this expression in the formal power series ring Zp\llbracketx\rrbracket modulo p, we have (1+x)npr1+x=(1+xpr)n1+x=(1+nxpr+)(1x++(1)pr1xpr1+) We conclude that the desired coefficient modulo p is (1)pr11, 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 G is a cyclic group, in which case we know that N(pr)=1. 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-p subgroups are conjugate to each other. First, G acts on all Sylow-p subgroups by conjugation, and the order of each orbit [G:NG(P)] must be coprime to p. Let P be a Sylow-p subgroup of G, and consider the conjugation action of P on all Sylow-p subgroups. Then Q is fixed by the action of P if and only if PNG(Q). In this case, consider the projection PNG(Q)NG(Q)/Q. Since the order of the quotient group NG(Q)/Q does not contain p, and all elements of P have order pk, we know that the image of this projection must be 1, which implies that PQ. Therefore, P=Q. This shows that only P is fixed by this conjugation action, and all other orbits have length a power of p. However, under the conjugation action of G, each orbit is not divisible by p, so when each orbit is restricted to act on P, there must be an orbit of length 1. We have already proved that only P is fixed by the conjugation action, so there can only be one G-orbit. ◻

Corollary 2.2. If |G|=npr, where n and p are coprime, and there exists a unique Sylow-p subgroup, then this subgroup is a normal subgroup.

Corollary 2.3. If |G|=npr, where n and p are coprime, then N=N(pr)=[G:NG(P)] is a factor of n and has the form of pk+1.

Example 2.4. We will prove that a group of order 15 must be cyclic. According to Sylow’s theorem, we can consider two Sylow subgroups P3 and P5 of orders 3 and 5, respectively. We have N(3)1mod3 and N(3) is a factor of 5. However, the only number that satisfies the congruence is 1. Similarly, we find that N(5)=1. Therefore, for all factors d of |G|, there is only one subgroup of order d, which must be cyclic.

Exercise 2.16. Let G be a group of order 40. Prove that it has a normal subgroup of order 5.

Exercise 2.17 (). Let P be a Sylow-p subgroup of G. Prove that if NG or PG, then NP is a Sylow-p subgroup of N.

Exercise 2.18 (). Prove that if HG and P is a Sylow-p subgroup of G, then there exists gG such that HgPg1 is a Sylow-p subgroup of H.

Exercise 2.19. Find all Sylow-2 subgroups and Sylow-3 subgroups of S3.

Exercise 2.20 (). Try to find all Sylow subgroups of S4.

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

Using Sylow’s theorem to find normal subgroups

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

  • Take |G|=npr where p and n are coprime, and calculate the possible number of Sylow p-subgroups N, which satisfies {N1modpN is a factor of |G|

  • If N=1, then by Sylow’s theorem we know that PG.

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

  • If r=2, consider the intersection H=P1P2 of two Sylow subgroups. If |P|2>|G|, then |H|=p (since |P1P2|=|P|2/|P1P2|) and P1,P2NG(H), so G=NG(H) and HNG(H)=G.

  • Consider the conjugation action of G on X={P1,P2,,PN}, and its kernel kerρ, which may be a non-trivial normal subgroup of G.

Example 2.5. We prove that the group of order 36 is not a simple group. Consider the number of 9-order subgroups of G, denoted by N. We have N=1 or 4. If N=4, consider the conjugation action of G on these four Sylow-3 subgroups: ρ:GS4 Since |S4|=24, ρ cannot be injective. Moreover, by the transitivity of Sylow subgroups under the conjugation action of G, we know that this action is non-trivial. Therefore, kerρG forms a non-trivial normal subgroup of G.

There is another proof. If N=4, consider H=P1P2. Since 36|P1P2|=81/|H|, we know that |H|=3. But P1,P2NG(H), so NG(H) contains the group generated by P1 and P2. Hence, G=NG(H)H is a non-trivial normal subgroup of G.

Exercise 2.21 (). Prove that the group of order 150 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 H be a p-subgroup acting on all Sylow p-subgroups, then Pi forms a single orbit HPi

Proof. One side is obvious, we prove the other side. Suppose a1Pa=P and a is a pk-order element, then aNG(P). Since PNG(P), consider the projection of a under NG(P)NG(P)/P Since |NG(P)/P| is coprime to p, its projection can only be the identity element, so aP. This is enough to prove the proposition. ◻

Proposition 2.4. Every p-power order subgroup H of G is contained in some Sylow-p subgroup.

Proof. Consider the action of H by conjugation on all Sylow-p subgroups of G. The orbit lengths are either 1 or multiples of p. Since the number of Sylow-p subgroups is 1modp, we know that there must be one P that forms its own orbit, thus by Lemma, HP. ◻

Proposition 2.5. Let H be a p-subgroup. Then the number of Sylow-p subgroups containing H, a, is 1modp.

Proof. Let H act on all Sylow-p subgroups, HP is equivalent to the orbit length of P being 1. Since the number of all Sylow-p subgroups is 1modp, we have aa+other orbits=N1modp. ◻

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, Q cannot be generated by a finite number of elements. The simplest example of a finitely generated abelian group is the so-called n-element free abelian group Zn=Z×Z××Z, which is generated by n elements: e1=(1,0,,0),e2=(0,1,0),,en. It can also be called a free Z-module: Z-modules and abelian groups are the same concept.

Let G be an Abelian group that can be generated by a finite number of elements g1,,gnG. Then we can define a surjective homomorphism as follows: φ:ZnGi=1naieii=1naigi. According to the fundamental homomorphism theorem, we have GZn/kerφ. Therefore, our goal is to study what kind of subgroups Zn has, which will allow us to determine all possible quotient groups.

Let’s first consider the simple case of n=1. We know that the only subgroups of Z are 0 and nZ for n1. Therefore, all non-trivial subgroups of Z are isomorphic to Z.

For the case of n=2,G=Z2, let HG be a subgroup. Consider H1=HZ×0Z and H2=H0×ZZ. We can think of H1 and H2 as subgroups of Z, so they must be H1=aZ and H2=dZ. This means we can find two elements α1=(a,b),α2=(c,d) in H such that the first component of each element is divisible by a and the second component is divisible by d. So we can write α1=(a,xd),α2=(ya,d). Now, note that α2yα1=(0,(1xy)d)H and α1xα2=(0,(1yx)a)H. We will prove the following important result (essentially linear algebra) in Chapter 4:

Theorem 2.4. Subgroups of Zn are necessarily free Abelian groups, isomorphic to Zm with mn. In fact, if HZn, then there exists a set of αiG and a set of non-negative integers di such that di|di+1 and H=Zd1α1Zd2α2Zdnαn.

Corollary 2.4. All finitely generated Abelian groups are isomorphic to some ZmZd1Zd2Zdk.

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 NG, then we can construct the quotient group Q=G/N. One might wonder if GN×Q holds? In most cases, this is not true. For example, consider the case of G=Z4 and N=2Z4, it is obvious that Z4Z2×Z2.

If Q can be naturally realized as a subgroup of G, i.e. there exists QG such that the natural projection GG/N is an isomorphism, then we can assert a weaker proposition: G is the semidirect product of N and Q, i.e. GNQ. Let us explain this, we can reconstruct G from N and Q: for each gG, there exists an image q in Q, so gq1N, which means g=nq, and this representation is unique. Since NG, the multiplication operation on G=NQ can also be recovered from the conjugation action of Q on N: (n1q1)(n2q2)=n1q1n2q11(q1q2). This inspires us to define a group structure on the set N×Q from N, Q, and the (conjugation action) homomorphism θ:QAut(N) as follows: (n1,q1)(n2,q2)=(n1θq1(n2),q1q2). The identity element in the group is (1,1), and the inverse element is (θq1(n1),n1). It can be verified that this definition satisfies the associative law, so N×Q forms a group under the above multiplication, which we denote as NθQ, called the semidirect product of N and Q.

Exercise 2.22 (). Verify the associative law in the above definition.

Example 2.6. G=Z3θZ2 has two possibilities depending on the choice of θ:Z2Aut(Z3)Z2:

  1. If θ=1Z3 is the trivial homomorphism, then G=Z3×Z2Z6.

  2. If θ is the homomorphism that maps θ(1) to the unique non-trivial automorphism αAut(Z3) where α(a)=a1, then we have G=a,b|a3=b2=1,bab1=a1D3.

Verify that DnZnθZ2, what is the homomorphism θ? We give the following simple criterion:

Proposition 2.6. If NG, QG, G=NQ, and NQ=1, then GNθQ where θ is the conjugation action of Q on N.

Proof. From G=NQ and NQ=1, we can see that each element gG can be uniquely represented in the form of nq. Therefore, by the construction of the semidirect product, we know that we can define an obvious homomorphism GNθQ which is obviously a surjective homomorphism. ◻

Exercise 2.23 (). Verify that G=NH implies NG.

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

Proposition 2.7 (Symmetry of N). If there exists αAut(N) such that for all n,q, θq(n)=α1(θq(α(n))) or equivalently, there exists a commutative diagram rendering math failed o.o then NθQNθQ.

Proof. Construct a homomorphism φ:NθQNθQ φ(n,q):=(α(n),q). Firstly, we verify that it is a homomorphism, we have φ((n1,q1)(n2,q2))=φ(n1θq1(n2),q1q2)=(α(n1)α(θq1(n2)),q1q2)=(α(n1)θq1(α(n2)),q1q2)=φ(n1,q1)φ(n2,q2). It is obviously a surjection. ◻

Similarly, we have the following proposition:

Proposition 2.8 (Symmetry of Q). If there exists βAut(Q) such that for all n,q, θq(n)=θβ(q)(n) or equivalently, there exists a commutative diagram rendering math failed o.o then NθQNθQ.

Exercise 2.24 (). Prove the above proposition.

Exercise 2.25 (). Prove the group isomorphism a,b|a3=b7=1,aba1=b2a,b|a3=b7=1,aba1=b4.

Exercise 2.26 (). Find all pq-order groups, where p and q are both prime numbers. Prove that there are at most two different isomorphism classes.

Exercise 2.27 (). If G=ZpθZn, where p is a prime number, prove that the number of conjugacy classes c(G) satisfies c(G)=n(1+p1h2). Here, h represents the order of θ, i.e. the smallest number such that θh=1.

Exercise 2.28 (). If Q is a cyclic group and θ(Q) and θ(Q) are conjugate in Aut(N), prove that NθQNθQ. (Hint: Prove that there exist αAut(N) and βAut(Q) such that α1θqα=θβ(q).)

All Groups with |G|15

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

Proposition 2.9 (|G|=pq case). Let 1<p<q be two primes, and G be a group of order pq. Then,

  1. If p|q1, then GZpq or GZqZp.

  2. If pq1, then GZpq.

Proposition 2.10. By Sylow’s theorem, the q-order cyclic subgroup, denoted by Zq, is a normal subgroup of G. Let Zp be a Sylow-p subgroup of G. Since |ZqZp|=1 and G=ZpZq, we have G=ZqθZp, where θ:ZpAut(Zq)Zq1. This implies that if pq1, the above mapping is trivial, so GZq×ZpZpq. If p|q1, consider the non-trivial choice of θ, so that θ becomes a monomorphism. However, the embedding image of Zp in Zq1 is unique, so these non-trivial homomorphisms differ only by an automorphism of Zp. 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 n=8,12.

Classification of 8-order groups

The commutative 8-order groups are only Z8, Z4×Z2, and Z23. Now we will study the non-commutative 8-order groups. By Sylow’s theorem, we know that G has 2k+1 subgroups of order 4. It is impossible to have 5 subgroups, otherwise it will occupy at least 5×(42)+2=12 elements. Therefore, there can only be 1 or 3 subgroups.

If there is only one subgroup of order 4, HG, then HZ4 must hold, otherwise if HZ22, there will be no elements of order 4 in G, which leads to all elements of G being of order 1 or 2, making G abelian, which is not relevant to our discussion. So now we have H=Z4. Let aGH, then we must have G=aHZ4Z2D4, and there is only one non-trivial choice for the conjugate action. However, in reality, D4 has 3 subgroups of order 4: σ,σ2,τ,τσ,σ2.

If there are 3 4th-order subgroups, note that all subgroups with an index of 2 are normal. By Cauchy’s theorem, we can choose an element b of order 2. If it does not belong to any of the 4th-order subgroups, then G must be a semidirect product, which could be Z4Z2, which is the same as D4 mentioned above. If it is the case of Z22Z2=a,b,c|a2=b2=(ab)2=c2=1,cac1=b, then choosing a=τσ,b=τσ3,c=τ shows that this is also D4.

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

Classification of Groups of Order 12

For groups of order 12, it is easy to see that the only Abelian groups are Z12 and Z2×Z6. Now we only need to consider the case of non-Abelian groups. By the Sylow theorem, we know that G has either 1 or 3 normal subgroups of order 4, and either 1 or 4 subgroups of order 3. We can see that G=HKHθZ3, where HZ4 or Z22 and θ:Z3Aut(H) is a non-trivial homomorphism (if it is trivial, we get a direct product, which is one of the Abelian groups mentioned before).

First, let us assume that G has a normal subgroup H of order 4. If H=Z4, then considering θ:Z3Aut(Z4)Z2, we can see that θ must be trivial.

If H=Z2×Z2, we know that Aut(H)S3 is the permutation group of the three 2-order elements in H. Consider the map θ:Z3Aut(H)=S3 that maps to the unique subgroup A3Z3 in S3. Thus, θ can be seen as an isomorphism from Z3 to A3Z3, and different choices of θ differ only by an element in Aut(Z3). By the symmetric lemma of Q, we know that the groups G=Z22Z3 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 A4.

Now let’s consider the case where it has 3 subgroups of order 4. Since these 3 subgroups must occupy (42)×3+1=7 elements, it is impossible to have 4 subgroups of order 3, because 4 subgroups of order 3 would occupy at least (31)×4+1=9 elements. We conclude that there can only be one subgroup of order 3, which makes it normal. If H=Z4, there is only one non-trivial semidirect product Z3Z4.

If H=Z22, then θ:Z22Aut(Z3)Z2. 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 Z22, which determines the same group Z3Z22. In fact, it is D6.

Exercise 2.30 (). Prove that it is D6.

Now we will prove that Z3Z4 is neither D6 nor A4. Since A4 does not have any normal subgroup of order 3, Z3Z4 cannot be isomorphic to A4. Also, D6 does not have any element of order 4, so it cannot be isomorphic to it.

Table of Small Order Groups

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

Order Abelian Non-Abelian
2 Z2
3 Z3
4 Z4,Z22
5 Z5
6 Z6 S3
7 Z7
8 Z8,Z4×Z2,Z23 D4,Q8
9 Z9,Z32
10 Z10 D5
11 Z11
12 Z12,Z22×Z3 A4,D6,Z3Z4
13 Z13
14 Z14 D7
15 Z15

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, Z is an abelian group under addition, but it also has a multiplication structure. This is a new algebraic structure called a ring. Of course, the addition and multiplication on a ring cannot be arbitrarily defined, they need to be compatible with each other and satisfy some reasonable properties. The complete definition is as follows:

Definition 3.1 (Ring). A set R with two operations (+) and () is called a ring if R forms an abelian group under the operation (+), and for any a,b,rR, the following properties hold:

  1. (Associativity) (ab)r=a(br)

  2. (Distributivity) r(a+b)=ra+rb, (a+b)r=ar+br

  3. There exists a multiplicative identity 1R such that r1=1r=r.

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 0 to represent the additive identity and 1 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 R a commutative ring.

Definition 3.2 (Field). If R is a ring and every non-zero element rR has a multiplicative inverse r1R such that r1r=rr1=1 then we call R a field. If the multiplication in R is commutative, then R is called a commutative field.

In a ring, non-zero elements may not have a multiplicative inverse. If a non-zero element rR has a multiplicative inverse, we call it a unit.

Exercise 3.1. Find all units in the ring Z.

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 Z forms a ring under the usual addition and multiplication.

Example 3.2. The set of all rational numbers Q, real numbers R, and complex numbers C form fields under the usual operations.

Example 3.3. The set of all polynomials with integer coefficients, denoted by Z[x], forms a ring under the usual polynomial multiplication and addition, where Z[x]:={anxn+an1xn1++a1x+a0|aiZ,n0} Similarly, for any ring R, we can define the polynomial ring R[x] as R[x]:={anxn+an1xn1++a1x+a0|aiR,n0} This is also a ring, with addition defined in the usual way and multiplication defined as (i=0maixi)(j=0nbjxj)=k=0m+n(i+j=kaibj)xk It is easy to verify that this satisfies the associative and distributive properties.

Example 3.4. Let S be a set consisting of all finite strings. Define Z[S] as a ring that consists of all finite forms and combinations of strings (and Z), for example 5+2hello3worldZ[S] Addition is given in the natural way, and multiplication is given by concatenation of strings: abcadc=abcadc (2a+3b)(2a3b)=4aa6ab+6ba9bb. Under this definition, Z[S] forms a non-commutative ring, for example ab=ab while ba=ba.

Exercise 3.2. Is the set of all natural numbers N={0,1,2,} a ring under the usual integer operations?

Exercise 3.3 (). Verify that the set Z[2]={a+b2|a,bZ} forms a ring under the usual operations.

Exercise 3.4 (). Consider the set Z(2):={abQ|as a reduced fraction, the denominator b is odd}. Is it a ring? Is it a field?

Exercise 3.5 (). Let H={a+bi+cj+dk|a,b,c,dR} be a ring defined by the following rules, with multiplication given by ij=k,jk=i,ki=j ji=k,kj=i,ik=j i2=j2=k2=1 Prove that H is a field. (Hint: Consider (a+bi+cj+dk)(abicjdk))

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 f:RS between rings is called a ring homomorphism if f satisfies

  1. (Abelian group homomorphism) f(a+b)=f(a)+f(b)

  2. (Preserves multiplication) f(ab)=f(a)f(b)

  3. (Preserves identity element) f(1)=1,f(0)=0.

If f is still an injection, it is called a monomorphism. If f is also a surjection, it is called an epimorphism. If f has a homomorphic inverse, it is called an isomorphism. Homomorphisms between fields are also understood as homomorphisms between rings.

Example 3.5. Let K be a field, x0K, and define a polynomial valuation homomorphism f:K[x]Kp(x)p(x0) that maps a polynomial p(x) to its value at x=x0, p(x0).

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 pZ, we can consider the set of all multiples of p, denoted as (p):={kp|kZ}, which is called the ideal generated by p. The essential characteristic of this set of multiples is its "absorption" property, which means that for any rZ,i(p), we have ri(p). This leads to the concept of an ideal as follows:

Definition 3.4 (Ideal). An Abelian subgroup I of a ring R is called a left ideal if for any rR,iI, we have riI. If the condition is changed to irI, it is called a right ideal. If I 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. R itself is an ideal, called the trivial ideal, and any ideal that is not equal to R 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 R and a two-sided ideal I, we can define the set of cosets R/I={r+I|rR}. This is first and foremost an Abelian group, the quotient group of R by the subgroup I, with elements being cosets r+I or understood as representatives of the equivalence relation on R determined by I. Its multiplication is inherited from the larger ring R, defined as (r+I)(s+I)=rs+I. It can be easily verified that due to the absorption property of ideals, as a subset of R, the product (r+I)(s+I)rs+I. Therefore, the above multiplication is well-defined (independent of the choice of representatives).

Example 3.6. Consider the ideal nZ={nk|kZ} of the ring Z. The quotient ring with respect to this ideal is called the ring of residue classes modulo n: Z/nZ={a+nZ|aZ}={nZ,1+nZ,2+nZ,,(n1)+nZ}. As an additive group, this is a cyclic group of order n. As a ring, it is a finite ring, with the additive identity element being nZ and the multiplicative identity element being 1+nZ. The number-theoretic meaning of this ring is that it consists of n residue classes of all integers modulo n. It is worth noting that when n is a prime number p, Z/pZ is in fact a finite field with p elements.

Exercise 3.7. For a sequence of ideals Iλ, we can define their sum: ΣλIλ as the following ideal {all finite sumsλaλiλ|aλR,iλIλ}. Prove that this is an ideal. For a finite number of ideals I1,,In, we can define their product J=I1In as J={i1in|ikIk}. Prove that this is also an ideal.

Exercise 3.8. Prove Fermat’s little theorem in number theory by following steps:

  1. Let 0aZ/pZ. Prove that for any k, ak0.

  2. From this, it follows that a has a multiplicative inverse, i.e. Z/pZ is a field, sometimes denoted as Fp, called the p-element finite field.

  3. Prove that Fp×:=Z/pZ{0} is a multiplicative group, hence for any aFp×, ap1=1.

Prime Ideals

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

Exercise 3.9 (). We call a ring R an integral domain if ab=0 implies a=0 or b=0 in R. Prove that R/I is an integral domain if and only if I is a prime ideal.

Exercise 3.10. Let f:RS be a ring homomorphism. Prove that the preimage of a prime ideal is always a prime ideal. That is, if PS is a prime ideal, then f1(S) is a prime ideal of R.

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

Proposition 3.1 (Maximal ideals are always prime ideals). Let I be a maximal ideal (two-sided) of R. Then I is also a prime ideal (two-sided) of R.

Proof. Otherwise, suppose abI but a,bI. Consider ((a)+I)((b)+I)=(ab)+II Since (a)+I,(b)+I are strictly larger than I, according to the assumption, they can only be equal to the trivial ideal R. Thus, we have R=RRI This contradicts the fact that I is a maximal ideal (by definition, it must be a proper ideal). ◻

Proposition 3.2. Any non-unit element aR is necessarily contained in some maximal ideal.

Proof. Consider the (left) ideal Ra generated by a. Since a is not a unit, we know that RaR. Therefore, Ra is a proper ideal. Using Zorn’s lemma on the set of all ideals containing Ra, we can find a maximal (left) ideal that contains it. ◻

Exercise 3.11 (). Prove: Let I be a two-sided ideal of R, prove that R/I is a field if and only if I is a maximal ideal.

Exercise 3.12 (). Let a be contained in all maximal ideals, prove that a+1 is a unit.

Kernels and Images of Homomorphisms

Just like the kernels and images of group homomorphisms, for a ring homomorphism f:RS, we can define ker(f):={rR|f(r)=0} and Im(f):={f(r)|rR}.

Exercise 3.13. Verify that the kernel is a two-sided ideal in R and the image is a subring in S.

We have an obvious isomorphism theorem.

Theorem 3.1 (First Isomorphism Theorem). Given a ring homomorphism f:RS, it induces a ring isomorphism f:R/ker(f)Im(f)

Proof. This isomorphism is defined by r+ker(f)f(r) It is obviously well-defined, since the image of ker(f) is 0. If f(r)=0, then rker(f), so it is injective. Surjectivity is also obvious. ◻

Theorem 3.2 (Corresponding Theorem). Let I be a bilateral ideal, p:RR/I be the natural projection. Then all ideals of R/I correspond one-to-one with ideals of R that contain I.

Exercise 3.14. Prove that the only ideals of a field are the trivial ideal and the zero ideal (0):={0}. 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 R are finitely generated, i.e. any ideal IR can be expressed as I=Ra1+Ra2++Ran (where for right ideals, we replace Rai with aiR), where aiR, then we say that R is a Noetherian ring (left, right, or two-sided). This is an important and fundamental property in ring theory, and most of the rings we study are Noetherian.

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

Theorem 3.3 (Noetherian Property). The following three statements are equivalent (each with a corresponding theorem for left, right, and two-sided, respectively):

  1. R is a Noetherian ring.

  2. Any ascending chain of ideals in R, I1I2 must eventually stabilize, i.e. there exists n such that In=In+1=In+2=.

  3. Any non-empty set S consisting of ideals in R must have a maximal element, i.e. there exists IS such that IJSI=J.

Proof. (1)(2):
Assume I=i=1Ii, it is easy to prove that this is an ideal. Therefore, I is finitely generated. Let it be generated by a1,,am. By definition, we can assume aiIni, then when nmax(n1,,nm), In=I, so the chain stops here.

(2)(3):
Otherwise, there exists a strictly increasing infinite chain, which contradicts (2).

(3)(1):
Let I be an arbitrary ideal. Suppose S is the set of all finitely generated ideals contained in I. Then we can choose a maximal element JS. If JI, there exists aJ but aI. Consider J+Ra, which is a finitely generated ideal strictly larger than J. This contradicts the definition of J. Therefore, J=I. ◻

Exercise 3.15. Prove that a finite ring is necessarily Noetherian.

Exercise 3.16. Prove that if R is Noetherian, then R/I is also, where I is a two-sided ideal. Hence, it follows that any homomorphic image of R is also Noetherian.

The following fundamental theorem shows that many rings are Noetherian.

Theorem 3.4 (Hilbert’s Basis Theorem). If R is Noetherian, then R[x] is also.

Proof. Let I be an ideal in R[x] (assume it is a left ideal). Define Jm={rR|r appears in the leading coefficient of some m-degree polynomial f(x)I}{0}. There is an ascending chain of ideals J0J1J2 By the Noetherian property of R, each Ji is finitely generated and this chain must stop. Let Jn=Jn+1= Then take the polynomials fi,j(x)R[x] corresponding to the generators of J0,,Jn, where deg(fi,j)=in. We will prove that g0I, it can be generated by {fi,j}. Suppose its leading coefficient appears in fn1,j1, where n1deg(g0), then we have g1=gfn1,j1xdeg(g)n1 with degree strictly less than deg(g0). If it is not 0, we can continue by taking some fn2,j2, where n2deg(g1), and define g2=g1fn2,j2xdeg(g1)n2 with degree strictly less than deg(g1). If it is not 0, we can continue this process. But since the degree is a non-negative integer, this process must stop, and we can finally get g0=kfnk,jkxdeg(gk1nk) 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 a1,,anR, we define the ideal notation (a1,,an):=Ra1+Ra2++Ran to represent the ideal generated by a1,,an. If an ideal I can be generated by a single element aR, i.e. I=(a), then we call it a principal ideal. If all ideals of an integral domain R are principal, then we call it a principal ideal domain (PID).

Theorem 3.5 (Greatest Common Divisor Theorem). Z is a PID.

Proof. Let I be a nonzero ideal of Z, and let 0<aI. If I=(a), the proof is complete. Otherwise, let 0<bI such that a does not divide b. Consider the division with remainder b=aq+r,0<r<a Thus, we have r=baqI. If all elements in I are divisible by r, then I=(r) and the proof is complete. Otherwise, we can continue to take out an element that is not divisible by r and repeat this process, obtaining a positive integer smaller than r that belongs to I. However, since r is a positive integer, this process cannot continue infinitely and there must be a step where r is an element of I and all elements in I are divisible by r. Therefore, I is a principal ideal. ◻

Corollary 3.1. Let d be the greatest common divisor of a1,,anZ. Then there exist integers x1,,xnZ such that d=a1x1++anxn.

Proof. According to the theorem, I=(a1,,an)=(r) is a principal ideal. Obviously, d|r=r1a1++rnan. But since ai(r), we also have r|ai, so r divides the greatest common divisor of ai, r|d. This shows that r=±d. Therefore, d(d)=Za1++Zan, and there exist xiZ such that d=a1x1++anxn. ◻

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

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 R 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: R is a PID R 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 I, there exist a finite number of non-zero prime ideals Pi such that IP1Pn.

Proof. Let S be the set of ideals for which the proposition does not hold. Then we choose a maximal element JS. Since J is not a prime ideal, there exists xyJ such that x,yJ. We have ((x)+J)((y)+J)=(xy)+JJ Note that (x)+J and (y)+J are strictly larger than J. By the definition of J, they have decompositions. Therefore, their product also has a decomposition, which contradicts the definition of J. Hence, S is an empty set.

As for uniqueness, we can assume that there are two decompositions a=up1pm=vq1qn where u,v are units and (pi),(qj) are prime ideals. From (pi)vq1qn, we can conclude that (pi)qj(pi)=(qj), 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 m=n and the prime factors appearing in the decomposition are exactly the same up to order and units. ◻

Corollary 3.2. Z is a UFD.

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 Z[5]={a+b5|a,bZ}, we have 6=23=(1+5)(15) These are two distinct factorizations of 6. The interesting thing is that the factors appearing in these factorizations are irreducible but not prime.

Exercise 3.19 (). Prove that 2,3,1+5,15 are irreducible elements in Z[5], but not prime. Hence, the unique factorization property does not hold in Z[5].

Interesting Example: Gaussian Integers

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

Exercise 3.20. Prove that if both n and m can be written as the sum of two squares, then nm can also be written as the sum of two squares.

Exercise 3.21. Prove that in Z[i], N(α)=1 if and only if α is a unit.

Lemma 3.2 (Euclidean division in Gaussian integers). Let α,βZ[i]. Then there exist γ,δZ[i] such that α=βγ+δ and 0N(δ)<N(β).

Proof. Consider the quotient of complex numbers αβ=x+iy, where a and b are the two integers closest to x and y, respectively. Then, α=β(x+iy)=β(a+bi+E)=β(a+bi)+δ where δ=αβ(a+bi)Z[i], and N(E)=|E|214+14<1 Thus, N(δ)=N(β)|E|2<N(β). ◻

Corollary 3.3. Z[i] is a PID, and therefore also a UFD.

Proof. Following the proof that Z is a PID, for any non-zero non-unit element aI, if (a)I, we can choose bI(a) and repeatedly use Euclidean division to make the norm of the remainder r=abq smaller. Since this is a positive integer, the process must eventually stop, and we can obtain rI such that r divides all elements in I. ◻

Let’s see the powerful application of the fact that Z[i] is a UFD.

Proposition 3.3. We prove that the equation y2+1=x3 has only one unique integer solution, (x,y)=(1,0).

Proof. Consider the equation in Z[i]: (y+i)(yi)=x3 Let (d)=(y+i,yi) be their greatest common divisor in Z[i]. Then d|y+i,d|yid|y+i(yi)=2i. It is easy to factor 2i as 2i=(1+i)(1i)i, where i is a unit and (1+i),(1i) are irreducible elements, hence prime elements. If d contains (1+i) or (1i) as prime factors, then (yi)(y+i) would be even, which means x3 is divisible by 8, and thus y2 is a number of the form 8k+7. However, this is impossible since the remainder of any integer squared divided by 8 can only be 0,1, or 4. Therefore, d is a unit, which means y+i and yi 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: y+i=u(a+bi)3 yi=u(abi)3 where uZ[i]× is a unit. Since the only units in Z[i] are ±1,±i, and ±1=(±1)3, ±i=(i)3, we can multiply u into the parentheses of the cube, so we can assume u=1. Then: y+i=a33b2a+(b3+3a2b)i This implies b3+3a2b=b(b2+3a2)=1, which means b=±1. Therefore, b2+3a2=3a21|1, which can only be satisfied if a=0 and b=1. Thus, the only integer solution to the equation is y=0,x=1. ◻

Exercise 3.22 (). Prove that Z[2] is a PID.

Exercise 3.23 (). Find all integer solutions to y2+2=x3

Exercise 3.24 (). Prove that Z[3] is not a UFD, but the ring Z[1+32] 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 a,bK[x] be two polynomials, where the degree of b, deg(b)>0. Then there exist polynomials q,rK[x] such that a=bq+r where deg(r)<deg(b).

Proof. Let a(x)=a0xn+a1xn1+, b(x)=b0xm+b1xm1+. Then take q0(x)=a0b0xnm We have abq0=0xn+ The nth term is cancelled. If its degree is not less than that of b, let a0xn1 be its next highest non-zero term, we can take q1=q0+a0b0xn1m We have abq1=0xn+0xn1+ If its degree is not less than that of b, we can continue this process until its degree is less than that of b, and we denote this abq as r. ◻

Corollary 3.4. K[x] is a PID.

Exercise 3.25 (). Is the polynomial ring K[x,y] generated by two variables x and y still a PID? Why?

Fractionalization and Fraction Field of Rings

This section discusses only commutative rings. For an integral domain R, we can take a multiplicative subset SR, that is, a subset satisfying aS,bSabS. Without loss of generality, we can assume that 1S. The fractionalization of the ring R with respect to S is defined as S1R:={rs|rR,sS} This set can be naturally equipped with addition and multiplication structures rs+rs:=rs+srssS1R rsrs:=rrssS1R. Two fractions r/s,r/s are considered equivalent if and only if rsrs=0. It can be easily verified that this forms a ring. If we take S=R{0}, then the resulting fractionalization is denoted as Frac(R) and is called the fraction field of R.

Definition 3.5 (Integrally Closed). Let R be an integral domain and let K=Frac(R). If there exists an element xK satisfying a monic polynomial equation with coefficients in R xn+r1xn1++rn1x+rn=0 then x is said to be integral over R. The set of all elements in K that are integral over R is called the integral closure of R in K, denoted as R. If the integral closure of R in K is equal to R, then R is said to be integrally closed (or normal).

Example 3.7. The integral closure of Z in Q is Z, because if xy is a reduced fraction satisfying a monic Z-coefficient equation, we can multiply both sides by y to get xn+r1yxn1++rnyn=0 which implies that every prime factor of y divides x. By the assumption of being reduced, y can only have no prime factors, which means y is a unit and xy is an integer. Therefore, Z is integrally closed.

Example 3.8. Let d be a square-free number, then Frac(Z[d])=Q(d):={x+yd|x,yQ}. This is because, r+sda+bd=(r+sd)(abd)(a+bd)(abd)=rasbda2b2drb+saa2b2dd The denominator a2b2d is not equal to 0, because d is square-free.

Exercise 3.26. Prove that UFDs are integrally closed.

Exercise 3.27. Verify that 1+72 is integral over Z, thus proving that Z[7] is not a UFD.

Exercise 3.28 (). Find the integral closure of Z[5].

Exercise 3.29 (). Let’s examine an example of how localization affects prime ideals.

  1. For the ring Z, list all of its prime ideals.

  2. Take S={1,2,4,8,16,} and consider the localization of the ring S1Z. List all of its prime ideals.

  3. Take the prime ideal (2)Z and let S=Z(2). Prove that this is a multiplicative subset and list all of the prime ideals in S1Z.

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

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

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

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

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

Elementary Number Theory in Cryptography

Z/n=Zn is an abelian group, representing the n residue classes modulo n, and forms a group under addition. If we consider Zn×=(Z/n)×, the set of all residue classes coprime to n, this set forms a group under multiplication, and its order is φ(n). According to Lagrange’s theorem, for any aZn×, we have aφ(n)=1, which means that for any integer a coprime to n, we have aφ(n)1modn. 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 kZnm as a one-time key that only they know. Before communication, the key k is added to the plaintext x to obtain the ciphertext x+k. Since k is completely random and independent of x, the distribution of x+k is also completely random, i.e. it has a trivial uniform distribution. Therefore, anyone who only obtains x+k without knowing k cannot gain any information about x. The recipient only needs to calculate (x+k)k=x to obtain the original message. However, this key can only be used once, as x has a non-trivial probability distribution, making it unsafe to use the same key multiple times. Therefore, both parties need to prepare a large number of one-time keys, which is not only inconvenient but also makes key distribution a difficult problem: after using a one-time key, it is difficult to ensure that the key can be securely distributed to the other party (through a channel or offline).

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

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

  2. Calculate n=pq,m=(p1)(q1).

  3. Randomly generate an integer e that is coprime to m, and use Euclidean division to calculate d such that ed1modm.

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

  5. When someone needs to send an encrypted message xZ/n to you, they can calculate xeZ/n and send it to you through a channel.

  6. A third party who obtains xe cannot know x because they do not know d and cannot factor n.

  7. You only need to calculate (xe)d=xZ/n to decrypt the original message.

Modules and Linear Algebra

Basic Knowledge of Modules

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

Definition 4.1 (R-module, multiple module, bimodule). Let R be a ring, an R-module M is defined as an abelian group with a (left) action of R on M, which means for rR, mM, we can define an action of r on m, denoted as rmM. This can be understood as a mapping from R×M to M, and this action satisfies the following properties:

  1. (Identity) 1m=m

  2. (Associativity) (rr)m=r(rm)

  3. (Left Distributivity of R) (r+r)m=rm+rm

  4. (Right Distributivity of M) r(m+m)=rm+rm

We say that M is a left R-module, also denoted as RM. Similarly, if M defines a right action mrM, satisfying similar properties, note that the associativity should be changed to m(rr)=(mr)r. We say that M is a right R-module, also denoted as MR.

If we compare the definition made for group actions, that is, a group action is a group homomorphism GAut(X), then we can also understand the above definition as a left R-module M is the action of R on an abelian group M, that is, a ring homomorphism ρ:REnd(M). Here, End(M) represents the ring formed by group homomorphisms from M to itself, and its multiplication is the composition of abelian group homomorphisms fg=fg. So each r can be imagined as an operator on M, an endomorphism, that is, rm=ρ(r)m. Because ρ(r) is an abelian group homomorphism, the distributive law of M is automatically satisfied. The existence of identity element, associativity, and the distributive law of R are guaranteed by the fact that ρ is a ring homomorphism.

It is worth noting that a right R-module M is a contrahomomorphism φ:REnd(M), which reverses the direction of multiplication, φ(rs)=φ(s)φ(r).

If a group M has multiple module structures defined on it, and a family of rings {Ai} has left module structures defined on it, and another family of rings {Bj} has right module structures defined on it, then we say that their actions are commutative, or that their actions are compatible, if aj(aim)=ai(ajm), and (aim)bj=ai(mbj) and (mbi)bj=(mbj)bi. If these module structures are compatible with each other, then we call M a multi-module, which can be denoted as ({Ai};{Bj})-module, or (Ai|Bj)-module, or written as (Ai)M(Bj), and sometimes also written as MAi|Bj. If M is a (R|R) multi-module, i.e. it is both a left R-module and a right R-module and the two module structures are compatible with each other, i.e. (rm)r=r(mr), then M is called a bi-module over R. In the case where R is a commutative ring, left R-modules and right R-modules are collectively referred to as R-modules.

Exercise 4.1. Verify that the left multiplication of a ring R on itself can be seen as a left R-module. Similarly, the right multiplication is a right R-module, so R is a bi-module over R.

Exercise 4.2. Let I be a bilateral ideal of R. Verify that R/I is a bilateral R-module under the natural left and right multiplication.

Exercise 4.3. Explain that every Abelian group is a Z-module, and that a Z-module is also an Abelian group. Show the equivalence of these two concepts.

Exercise 4.4. For a commutative ring R, the structure of a right R-module can be defined for a left R-module M as follows: mr:=rm Why does this definition not hold when R 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 M and N be two R-modules. A homomorphism of R-modules φ:MN is defined as an Abelian group homomorphism satisfying φ(rm)=rφ(m) for all rR and mM. For right modules, the condition is modified to φ(mr)=φ(m)r. A homomorphism of R-modules is also called an R-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 φ:MN, we say that M and N are isomorphic and denote it as MN. Since the theory of right modules is completely similar, we will mostly consider left modules by default.

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

Exercise 4.5. Assume that φ:MN is an R-module homomorphism. Prove that kerφ:={mM|φ(m)=0} is a submodule of M, and Imφ is a submodule of N. Prove the first isomorphism theorem φ:M/kerφImφ.

Exercise 4.6. Let {Mi}iI be a family of submodules of M. Prove that iIMi={all finite sumsmi1++min|mi1Mi1,,minMin,{i1,,in}I} and iIMi are both submodules of M.

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

Theorem 4.1 (Second Isomorphism Theorem). Let M,N be submodules of some R-module. Then M+N and MN are also submodules and (M+N)/NM/MN.

Theorem 4.2 (Corresponding Theorem). Let NM be a submodule of M. Then the submodules of M/N correspond to the submodules L of M such that MLN.

Exact Sequence

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

Exercise 4.7. rendering math failed o.o is an exact sequence if and only if f is a monomorphism.

Exercise 4.8. rendering math failed o.o is an exact sequence if and only if f is an epimorphism.

Example 4.1. rendering math failed o.o is a short exact sequence of Z-modules, where 2 is the multiplication by 2 map and p is the projection. Here, ker(p)=2Z=Im(2).

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.

Hom Functor

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

Module Structure of Hom

Let R and S be two rings. If M has a left R-module structure and a right S-module structure, we write it as RMS when we need to specify the module structure.

We will give an example to show that HomR(RMS,RN) has a left S-module structure. This is because we can define, for fHom(M,N) and sS, (sf)(m):=f(ms) Then (sf) is clearly a left R-module homomorphism (we need to use the definition of multiple module: the module structures of multiple rings need to be compatible with each other). We need to verify that HomR(M,N) satisfies the definition of a left S-module, all other properties are obvious, the only one that needs careful checking is the associativity: (ss)f=s(sf) The left homomorphism is mf(mss), the right homomorphism is s(mf(ms))=mf(mss), so this is true, which means that HomR(M,N) becomes a left S-module under this definition.

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

Group Natural module structure Definition of S-module structure
HomR|(RM,RN)
Hom|R(MR,NR)
Z-module none
HomR|(RMS,RN)
Hom|R(MS,R,NR)
Left S-module (sf)(m):=f(ms)
HomR|(S,RM,RN)
Hom|R(SMR,NR)
Right S-module (fs)(m):=f(sm)
HomR|(RM,RNS)
Hom|R(MR,NS,R)
Right S-module (fs)(m):=f(m)s
HomR|(RM,R,SN)
Hom|R(MR,SNR)
Left S-module (sf)(m):=sf(m)

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

Exercise 4.9 (). Confirm that you understand all the cases in the table.

Endomorphism Ring

When M=N, HomR(M,M) is denoted as EndR(M), and it has a natural ring structure, where multiplication is the composition of homomorphisms from M to M.

Exercise 4.10 (). Prove that if M is an R-module, then it has a natural left R,EndR(M) bimodule structure.

Functoriality of Hom

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

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

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

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

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

As an example, we will explain in detail how Hom forms a functor.

  • For a fixed R-module N, we find that MHomR(M,N) is a contravariant functor, sometimes denoted as hN. This functor maps the R-module M to the Abelian group HomR(M,N), and maps the R-module homomorphism f:MM to the group homomorphism Hom(f,N):=Hom(M,N)Hom(M,N):hhf. It is clear that it preserves composition and identity maps.

  • Similarly, for a fixed module M, we find that NHomR(M,N) is a covariant functor, which maps the module homomorphism g:NN to the group homomorphism Hom(M,g):=Hom(M,N)Hom(M,N):hgh. It also preserves composition and identity maps.

Direct Sum

Given two left R-modules M,N, their direct sum MN is defined as the set M×N={(m,n)|mM,nN} as an Abelian group, with addition defined as component-wise addition, and R-action defined as r(m,n):=(rm,rn) It can be easily verified that this definition gives an R-module structure. Direct sums are not limited to finite sums, for any family of R-modules indexed by a set I, {Mλ}, we can define the direct sum as λIMλ:={(mλ)λIMλ|at most finitely many mλ are non-zero}. If we take a sequence of identical modules Mλ=M, we denote this direct sum as M(I).

Exercise 4.11 (). Verify that if M,N are two submodules of L, satisfying MN=0 then there exists an isomorphism M+NMN. In this case, we call M+N the internal direct sum of M,N.

Exercise 4.12. Prove that we have the following obvious exact sequence:

  1. 0MMNN0

  2. Here, let MM be a submodule. Then 0MMM/M0 is a natural exact sequence.

Direct Product

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

Example 4.2. Consider F=i=0Z, and G=i=0Z are two Z-modules, then (1,2,3,4,)G is an element of G, but not in F. There is a natural inclusion FG, and F is a submodule of G.

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: HomR(λIMλ,N)=λIHomR(Mλ,N). HomR(M,λINλ)=λIHomR(M,Nλ). Explain their equivalence with the following statements:

  • For any mapping hλ:MλN, there exists a unique mapping (hλ):λMλN such that hλ=(hλ)ιλ. Here, ιλ:MλMλ is the natural inclusion mapping.

  • For any mapping gλ:PNλ, there exists a unique mapping (pλ):PMλ such that gλ=prλ(pλ). Here, prλ:MλMλ is the projection onto the component.

Free Module

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

The importance of free modules lies in their good properties. Any homomorphism f:RnM starting from Rn can be easily determined by specifying where each ei=(0,,0,1,0,,0)Rn (the i-th position is 1) is mapped to. The entire homomorphism is completely determined by this. Because every element (r1,,rn)Rn can be written as (r1,,rn)=riei, we have f((r1,,rn))=f(riei)=rif(ei). It is worth noting that there is no restriction on how to choose the value of f(ei). In other words, the determination of f depends entirely on the arbitrary choice of n values f(ei), or, it depends on an arbitrary element (f(e1),f(e2),,f(en))Mn. This gives the following natural isomorphism HomR(Rn,M)=Mn.

Exercise 4.15. Prove the basic property of free modules HomR(R(I),M)=MI Note that I may be infinite, and note the difference between direct sums and direct products.

Generators and Basis

For a (left) R-module M, after selecting a family of elements (mi)iIMI, we can define a map (rrmi):R(I)M from HomR(R(I),M)=MI. We temporarily denote this map as ρ. The image of this map is called the R-linear combination of mi. We say that {mi}iIM is a set of generators of M if ρ:R(I)M is surjective. In other words, any mM can be written as a finite linear combination of mi: m=r1mi1++rnmin. If there exists a finite family of mi that generates M, then M is called finitely generated. We say that {mi}iI is a set of R-linearly independent elements, or simply independent, if the corresponding map ρ:R(I)M is injective. In other words, if any finite subset of mi, mi1,,min has any R-linear relation r1mi1++rnmin=0, then all coefficients r1=r2==rn=0. If a set of elements {mi} is both a set of generators and independent, then it is called a basis of M.

Exercise 4.16. Show that M having a basis is equivalent to M 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 R=k as a field. Since k is a commutative ring, k-modules are not distinguished between left and right. We call k-modules k-vector spaces or k-linear spaces. k-module homomorphisms are called k-linear maps or k-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 k-module. This makes linear space very easy to study, and we will explain this. Next, we assume that V is a k-vector space.

Theorem 4.3 (Basis Extension Theorem). Let F be an independent set of V and G be a generating set of V, satisfying FG. Then there exists a basis B of V such that FBG.

Proof. If there is a series of increasing independent sets Bi such that FBiG, then obviously iBi is also an independent set and satisfies FiBiG. Therefore, by Zorn’s lemma, there exists a maximal independent set B that satisfies FBG. We will prove that B can generate V, that is, the corresponding mapping ρB:k(B)V is an isomorphism. Otherwise, there exists vV that cannot be represented as a linear combination of elements in B. Since G is a generating set, there exists a finite sum v=ρG(a)=gGagg, where G is a finite set. Therefore, there must be an element gG that is independent of B, otherwise all gG are linearly dependent on B, and since B is an independent set, it can be deduced that all gG can be generated by B, which leads to the conclusion that v can also be generated by B, which is impossible. However, in this case, {g}B is a larger independent set contained in F{g}BG, which contradicts the assumption that B is a maximal independent set. Therefore, B is a basis. ◻

Example 4.3. Consider k=R, M=R2={(x,y)} is the set of all vectors on the plane. Under component-wise addition, M forms an Abelian group. Then M naturally becomes a k-vector space under k-multiplication: a(x,y):=(ax,ay)M. It is easy to verify that M satisfies the four definitions of a k-vector space (k-module) under this action. {(0,1),(1,0)} is a basis for M.

Exercise 4.19 (). Prove that the following statements are equivalent for a vector space V:

  1. B is a basis for V.

  2. B is a maximal linearly independent set in V.

  3. B is a minimal generating set for V.

Exercise 4.20. Let k=Q, find out which of the following are bases of k2 and which are not?

  1. (1,2),(3,4)

  2. (1,1),(1,1)

  3. (1,1),(1,2),(1,0)

Dimension Theory

If V has two different bases B1,B2, we hope to prove that B1 and B2 are equipotent, that is, there exists a bijection between them.

Finite Case

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

Now assuming that the proposition holds for |B1|m, we consider the case where |B1|=m+1. Let aB2, by the basis extension theorem, there exists a basis B={a}B such that {a}B{a}B1, so Vka(bBkb), and V=V/ka has B (as the projection image) as a basis, with m elements. Similarly, V also has B2{a} as a basis, so |B2|1m.

Infinite case

Now assuming that V has an infinite basis B, so Vk(B), if C is another basis, for each cC, there exists a finite expression c=bBcbb where only finitely many cb are non-zero. Then for any cC, consider the finite set Bc:={bB|cb0}, since C can generate the entire space, for each b there must be some c with non-zero coefficient for b, so we have cCBc=B Since B is infinite, this implies |C||B|, and since B is infinite, we can use the same reasoning to show that |B||C|.

Definition 4.3. We define the dimension dimkV of V to be the cardinality |B| of any basis B of V.

Exercise 4.21 (). Let there be a family of exact sequences of k-vector spaces 0EFG0 Using the basis extension theorem, prove that dimE+dimG=dimF. From this, deduce the following dimension formulas

  1. Let f:VW, then dimV=dimkerf+dimImf.

  2. Let FE be a subspace, then dimE=dim(E/F)+dimF.

  3. dim(MN)=dimM+dimN.

  4. Let M,NV be two subspaces, then dimM+dimN=dim(MN)=dim(M+N)+dimMN.

Matrices over Commutative Rings

Finitely Generated Free Modules

In this section, we assume that R is a commutative ring. It is worth noting that in the free module Rm, there exists a standard basis, where each element can be uniquely written in the form a1e1+a2e2++amem.

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

Matrices over Rings

We consider the R-module homomorphisms from Rn to Rm. Since HomR(Rn,Rm)=(HomR(R,Rm))n=(Rm)n=Rmn we know that to determine a homomorphism φ:RnRm, it is essentially enough to know where each ejRn is mapped to in Rm. We use eiRm to denote the standard basis of Rm. If we denote the ith component of the image of ej as aij, then we can write φ(ej)=iaijei Here aijR are the mn elements in R that we want. We can arrange these elements into a matrix A=(a11a12a13a1na21a22a23a2nam1am2am3amn) Matrices are usually represented by capital letters A,B,, etc. Here our matrix is the matrix of φ, which we also denote as Aφ. When we need to emphasize that the matrix elements are aij, we write A=(aij)1im,1jn. This matrix has m rows and n columns, and we say it is an m×n matrix over R, denoted as AMm×n(R). When m=n, this notation is simply written as Mn(R).

Exercise 4.22. Make sure you understand: giving an m×n matrix is equivalent to giving a homomorphism RnRm. That is, any matrix consisting of elements of R represents a homomorphism. So any matrix A can be (uniquely) written in the form of Af, where f is some homomorphism.

Composition of mappings and multiplication of matrices

For f,gHomR(Rn,Rm), and rR, we can define the homomorphisms rf and f+g. Similarly, we can define scalar multiplication and addition of matrices, i.e. we define r multiplied by Af as the matrix Brf corresponding to the mapping rf: rAf:=Brf Let Af and Bg be the matrices corresponding to the homomorphisms f and g, respectively. Then we define A+B as the matrix Cf+g corresponding to the mapping f+g: Af+Bg:=Cf+g.

Exercise 4.23. Prove that the elements of rA are (raij), and the elements of A+B are (aij+bij). Thus, prove that Mm×n(R) forms an R-module.

When we have the composition of homomorphisms rendering math failed o.o we can calculate Cgf using Af and Bg, and we call this process matrix multiplication, denoted as BgAf=Cgf. How do we actually perform this operation? We can write out the matrices Af=(aij),Bg=(bij) as f(ej)=iaijei g(ei)=kbkiek Therefore, (gf)(ej)=g(f(ej))=g(iaijei)=k(ibkiaij)ek. This shows that the coefficients of Cgf=(cij)=BA should be cij=kbikakj. This is the formula for matrix multiplication. Note that B is n×m, A is m×l, and BA is n×l, which means that matrix multiplication gives a mapping Mn×m(R)×Mm×l(R)Mn×l(R). When m=n=l, this multiplication operation gives multiplication on Mn(R), making Mn(R) 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 1:RnRn be the identity mapping. Write its matrix as In. This matrix is called the n-dimensional identity matrix. It is the multiplicative identity in Mn(R).

Exercise 4.26. Let AMm×n(R).

  1. Show that if we view elements in Rn as n×1 matrices (called column vectors), then the mapping RnRm corresponding to A is the matrix multiplication RnRm:vAv where vMn×1(R)=Rn.

  2. Show that the image of A as a linear mapping, Im(A), is a submodule of Rm generated by all the columns of A.

Reduction Theory of Matrices over PID

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

The group formed by the multiplicative inverses in the ring Mn(R) is called GLn(R). We say that A,BMm×n are equivalent if there exist two invertible elements PGLm(R), QGLn(R) such that A=PBQ. Note that equivalence is an equivalence relation.

Elementary Transformations of Matrices

For the matrix multiplication C=BA, we can interpret it as C being a recombination of the columns of B and the rows of A, with the coefficients determined by another matrix. From the formula for matrix multiplication cij=kbikakj we can see that the jth column of C is obtained by multiplying the first column of B by a1j, adding the second column of B multiplied by a2j, and so on until the kth column multiplied by akj. Similarly, the ith row of C is obtained by multiplying each kth row of A by the corresponding bik and then adding them together. Thus, left multiplication by a matrix corresponds to row operations, while right multiplication corresponds to column operations.

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

  1. Multiplying one row (or column) of the matrix by a non-zero element in R, and then adding it to another row (or column). For example, multiplying the first row of A by r and adding it to the second row: (10r1)(a11a12a21a22)=(a11a12ra11+a21ra12+a22).

  2. Rearranging the rows or columns of the matrix. Let A=(aij)Mm×n(R), if we want to rearrange the rows of the matrix using the permutation σSm, we left multiply with an m-dimensional matrix P=(δσ(i)j). Here, δij=1i=j is a function that equals 1 when i=j and 0 otherwise. We have (PA)ij=kδσ(i)kakj=aσ(i)j. Such a matrix is called a permutation matrix. Similarly, to rearrange the columns of the matrix, we right multiply with an n-dimensional permutation matrix.

  3. Multiplying a row or column of the matrix by a unit uR×. This can be achieved by left or right multiplying the matrix with a diagonal matrix (1u11). The row (or column) containing u is the one that needs to be multiplied.

  4. Adding a times the ith row (or column) of the matrix to b times the jth row (or column) to create a new ith row (or column), and adding c times the ith row (or column) to d times the jth row (or column) to create a new jth row (or column), where adbc=1. This is also a reversible transformation, which is equivalent to left multiplying with the following matrix (for the column case: right multiply and swap b and c): (abcd) where the omitted parts are all diagonal 1s. Its inverse is (dbca).

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 Pi and Qi in a certain order. By the associative law, the result can be written as (PkP1)A(Q1Qk) Of course, this is equivalent to saying that Mm×n(R) is a multi-module of (Mm(R);Mn(R)).

Equivalent Canonical Form

Theorem 4.4 (Equivalent Canonical Form in PID). Let AMm×n(R), where R is a PID. Then there exists a unique (up to units in R) set of diR such that d1|d2||dr and A is equivalent to the following diagonal form: (d1d2drO). Here, O represents a zero matrix (which may not exist), and the empty positions are all 0. We call the obtained r the rank of A, denoted as rankA.

Proof.

  • Consider the top left element a=a11 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 0 to have infinitely many prime factors. If the entire matrix is 0, we can consider it as already completed. Otherwise, we can assume that a11 has a finite number of prime factors.

  • If a11 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 ai1 that is not divisible by a11 to the position of a21. Let I=(a11,a21)=(d). We have αa11+βa21=d. Here, it must be that (α,β)=(1), otherwise if both α and β are divisible by some prime factor p, we have (α/p)a11+(β/p)a21=d/pI=(d), which is impossible. Therefore, we can assume that there exist δ,γR such that αδβγ=1. 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 d, which is a proper factor of the original a11 and has fewer prime factors.

  • We continue this operation until all elements in the first column are divisible by a11. At this point, the other elements in the first column can be eliminated by a11 through elementary operations, and we perform a similar operation on the first row until all elements except a11 are 0.

  • If a11 divides all elements in the matrix, we let d1=a11 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 a11. This operation will eventually stop, because the number of prime factors of a11 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, R is a PID. And let AMn(R) be viewed as an R-linear transformation from Rn to Rn. Follow the hints below to discover the Gaussian elimination method.

  1. Prove that AMn(R) is invertible if and only if it is equivalent to the identity matrix In, and hence conclude that A is invertible if and only if rankA=n and d1=d2==dn=1.

  2. 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 GLn(R).

  3. Prove that if A is invertible, then it can be transformed into the equivalent standard form In by using only row transformations.

  4. Consider the following algorithm for finding the inverse matrix A1, and write down the two matrices (A|B) side by side, where B is an n×m matrix. Use only row transformations (or column transformations if B is also an n-order square matrix) to perform the same operations on both A and B. Prove that when A is transformed into the identity matrix, B is transformed into A1B.

  5. Consider the cases where B=In and B=β is a column vector, and obtain an algorithm for finding the inverse matrix and solving the equation Ax=β when A is invertible. Here xRn=Mn×1(R) is an unknown column vector.

  1. Suppose A is not necessarily invertible. Prove that the kernel of A, denoted by kerA, can be generated by Qer+1,,Qen, where Q is the matrix that transforms A into its equivalent standard form, and r=rankA is the number of nonzero d1||dr.

  2. Obtain the following algorithm for computing the submodule kerARn: Write the two matrices (A|I) side by side, where I is the identity matrix. Apply elementary transformations to A and perform the same column operations on In, but do not perform any row operations. When A is transformed into standard form, the submodule generated by the last nr columns of the right matrix is kerA.

Let φ:VW be a linear map. Under a certain basis of V and W, the corresponding matrix is AMm×n(k). Prove that rankA=dimkImφ.

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, RmRnm=n. The second is that a submodule of a finite-generated free module on a PID is still a finite-generated free module.

Rank of Finite-Generated Free Modules

In fact, this holds for all integral domains.

Theorem 4.5. If R is an integral domain, then RnRmn=m.

Proof. We use the field of fractions K=Frac(R) of the integral domain R 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 f:RnRm defines an m×n matrix A over R. Since R is an integral domain, the inclusion mapping i:RK is injective, and we can view A as a matrix over K, denoted as AK. This matrix defines a mapping fK:KnKm, and since f has an inverse, we can see that fK also has an inverse. Therefore, fK is also an isomorphism. By the uniqueness of dimension for vector spaces, we have m=n.

Thus, we can define the rank of a finitely generated free module as rank(Rn)=n. ◻

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 R be a Noetherian ring. Then, as a submodule of itself, R is a module whose submodules are all ideals of R. By the Noetherian property, these ideals are finitely generated, so R is a Noetherian module.

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

Theorem 4.6. The following statements about R-module M are equivalent:

  1. M is a Noetherian module.

  2. Any ascending chain of submodules of M must terminate.

  3. The set of all submodules of M 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 R.

Theorem 4.7.

  1. If M is a Noetherian module, then all homomorphic images of M are also Noetherian modules.

  2. M is a Noetherian module if and only if there exists a submodule NM such that N and M/N are also Noetherian modules.

  3. Finite sums and direct sums of Noetherian modules are also Noetherian modules.

Proof.

  1. The image of any homomorphism φ:MN is isomorphic to M/kerφ. By the Correspondence Theorem, all ascending chains of submodules of M/kerφ can be corresponded to ascending chains of submodules of M, and thus must terminate.

  2. (): Clearly holds.
    (): Consider a family of ascending chains of submodules of M, denoted by Mi. Then MiN and (Mi+N)/N are two ascending chains of submodules of N and M/N, respectively. Since they are both Noetherian, these two sequences must terminate. Therefore, it suffices to prove that if PQ, PN=QN, and (P+N)/N=(Q+N)/N, then P=Q. Suppose qQ, then there exists pP such that qpN. Since qpQN=PNP, we have qP.

  3. From 0MMNN0, we can see that finite direct sums are Noetherian. Moreover, for a general finite sum MiM, it is the image of the homomorphism MiMiM.

 ◻

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

Finite generated free modules over PID

Let R be a PID, then R is obviously a Noetherian ring, so Rn is a Noetherian module, so all its submodules are finitely generated. Let NRn be a submodule, since it is finitely generated, there is a surjection RmN, which can be composed with the natural map NRn to obtain a map f:RmRn, whose image is N. So we can write this map as an n×m matrix A, consider the equivalent standard form of A, there are invertible n-order and m-order square matrices P,Q such that PAQ=D, where D is a diagonal matrix. Translating back to the language of maps, this means that there are two isomorphic maps p:RnRn and q:RmRm such that pfq=δ:RmRmRnRn. Obviously Im(f)=Im(fq)Im(pfq)=Imδ, where the matrix corresponding to δ is D, which is of the following form (d1d2drO). Here diR, rn. So we know that there is a basis e1,e2,,en of Rn such that Imδ=d1Re1d2Re2drRer, where the direct sum is an internal direct sum. This Imδ is already isomorphic to N, if you want to change back to the original form of N, then since p1 is an isomorphism, N=p1(Imδ)=irdiRp1(ei). Here ei=p1(ei) still forms a basis of Rn, because p1 is an isomorphism. So there is a basis e1,,en of Rn such that N=d1Re1drRer.

Corollary 4.1. NRr and rankN=rn.

Finite Generation Modules over PID

Any finite generation module M is the homomorphic image of a free module, and thus is the quotient of a free module by one of its submodules. We know that the submodules of a free module Rn over a PID are of the form (d1)e1(dr)er, where ei is a basis of Rn (not necessarily the standard basis). Therefore, under the isomorphism RnRe1Ren, this quotient is isomorphic to R/(d1)R/(dr)Rnr

Theorem 4.8. Let R be a PID and M be a finite generation R-module. Then there exists a sequence of elements d1|d2||dr in R and a non-negative integer k such that MR/(d1)R/(dr)Rk. This is called the ’cyclic decomposition’ of M.

Exercise 4.29 (). Prove that all finitely generated abelian groups are isomorphic to the following form GZd1ZdrZk where d1|d2||dr 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.

  1. If d=up1k1psks, where u is a unit, pi are distinct primes, and ks0 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 d=d1d2, where d1,d2 are coprime) R/(d)R/(p1k1)R/(psks).

  2. Show that Z2Z6Z18Z23(Z3Z9).

  3. Prove that all finitely generated R-modules are direct sums of modules of the form R/(pk) and R. More precisely, there is the following decomposition MRkp((R/pαp,1)βp,1(R/pαp,2)βp,2(R/pαp,sp)βp,sp) where 0αp,1αp,2αp,sp, βp,i0.

  4. Conversely, show how to transform quasi-prime decomposition into cyclic decomposition.

Standard Form of Linear Maps

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

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

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

Similar Matrices

Let’s first look at the first question. Let B={e1,,en} be another basis, with its matrix denoted as A. The so-called matrix is essentially a mapping from kn to kn, and its relationship with the original mapping can be described using the basis mapping ρ:k(B)V, where ρ is the mapping determined by {e1,,en} and is an isomorphism. Viewing A as a linear mapping from kn to kn, we have A=ρ1φρ, 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). rendering math failed o.o Similarly, if ρ is the mapping determined by another basis, we have A=ρ1φρ. Therefore, A=ρ1ρAρ1ρ=(ρ1ρ)A(ρ1ρ)1 This story can be represented by the commutative diagram below. rendering math failed o.o Note that ρ1ρ:k(B)k(B) is also an n×n matrix and is also an isomorphism (thus an invertible matrix). Let’s denote this matrix as P and call it the coordinate transformation matrix. We then have A=PAP1. This way, two matrices from the same mapping are connected. If there exists an invertible matrix P such that two square matrices A,A are connected by the above relationship, we call these two matrices similar. It can be easily verified that similarity is an equivalence relation on Mn(k).

Exercise 4.31. Let V=k2, and choose φ:VV to be the unique linear mapping that satisfies φ(e1)=e2 and φ(e2)=e1. What is the matrix A corresponding to φ? If we choose a new basis e1:=(1,1),e2=(1,1), calculate the transformation matrix P and A.

Similar Standard Form

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

Lemma 4.1. Let VA be the k[t]-module structure of V under the action t.v:=A.v, and VB be the k[t]-module structure of V under the action t.v:=B.v. Then A and B are similar if and only if, as k[t]-modules, VAVB.

Proof.

  • If A is similar to B, then the transition matrix P:VAVB is the required isomorphism mapping, noting that its action on t is different on its range and domain. Since it is an invertible matrix, it is obviously a k-module isomorphism. To verify that it is a k[t]-module homomorphism, it is sufficient to show that it commutes with t: P(tv)=PAva=PAP1Pv=B(Pv)=t(Pv). Note that conceptually, (Pv)VB, although as vector spaces VA and VB are identical, their k[t]-module structures are different.

  • Conversely, if there exists a k[t]-module isomorphism P:VAVB, then we have P(tv)=tP(v) which implies PA=BPPAP1=B.

 ◻

So, we found that classifying matrices or mappings by similarity is equivalent to classifying k[t] modules. Note that k[t] is a PID, and we know that the structure of finitely generated modules over a PID has been completely classified! It can be written as a direct sum of modules of the form R/(d) or quasi-prime modules R/(pk). One idea is that we can use matrices corresponding to these forms as our representatives, so we only need to transform VA 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 VA, we call the obtained di the invariant factors of the matrix A 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, V becomes a direct sum of modules of the form R/(pk) (R will not appear in the decomposition because V is a finite-dimensional k-vector space), where pR is an irreducible element of R. When we write VAR/(p1k1)R/(prkr) (allowing for repetition of elements in the sequences pi and ki), we call all of these pi(t)ki (which can be repeated) the elementary factors of A or φ. It is easy to see that giving the elementary factors completely determines the module structure of VA. The above decomposition is not only a direct sum decomposition of R modules, but also a direct sum decomposition as k modules. Therefore, we only need to find a k-basis for R/(piki) to find a k-basis for V. Let pi(t)ki=tdiadi1tdi1a0 be a polynomial with leading coefficient 1 (because in k[t], k{0} are all units), we take the images of 1,t,t2,,tdi1 in R/(piki) as a k-basis. Then the action of φ on this basis is just multiplication by t, so we have t1=t tt=t2 ttdi1=tdi=adi1tdi1+adi2tdi2++a0 This gives the matrix of φ on the subspace R/(piki) as Apiki=(a01a11a21adi1). Thus, in this basis, the matrix of φ is a matrix composed of such matrices arranged diagonally A=(Ap1k1Ap2k2Aprkr). Here, all elements in the matrix belong to k, and we call it the rational standard form of φ.

Exercise 4.32 (). Let φ:VV be a linear transformation on an n-dimensional k-vector space. Thus, φ makes V into a k[t] module Vφ.

  1. Prove that dn in the invariant factors of φ is the least common multiple of all elementary factors.

  2. For a module M over a ring R, define ann(M):={rR|rM=0} and prove that it is an ideal of R.

  3. Show that φ has a minimal polynomial, that is, ann(Vφ)=(m(t)) and the polynomial is m(t)=dn(t), with degree n.

Jordan Normal Form

If our field k is algebraically closed, that is, all polynomials over k have roots in k, which can be decomposed into a product of linear factors (such as k=C), then the matrix can be reduced to a simpler form. In this case, the irreducible polynomials over k[t] are all of the form (ta), so piki must be of the form (tλi)ki. We consider a more convenient k-basis for R/((tλi)ki): (tλ)ki1,(tλ)ki2,,1. In this basis, the action of t is as follows: t(tλ)ki1=λ(tλ)ki1+0 t(tλ)ki2=λ(tλ)ki2+(tλ)ki1 t1=λ1+(tλ) This shows that in this basis, φ has the following matrix representation on this subspace: Jpiki=(λi1λi1λi11λi). Here the matrix is of size ki×ki. So φ has the following matrix representation on V with this chosen basis: A=(Jp1k1Jp2k2Jprkr). This is called the Jordan normal form of φ. In particular, if ki=1, then J(xλi)=(λi) is a first-order matrix with only diagonal elements.

Exercise 4.33. Prove that A can be diagonalized over the field k if and only if all elementary divisors are of first order. This is equivalent to the minimal polynomial of A being able to be factored into a product of first-order polynomials over k and having no repeated roots.

Exercise 4.34 (). Let k=Fp be a finite field. How many k-similarity equivalence classes are there in M2(k)?

The k[t]-decomposition of V

In this section, we denote R=k[t]. How can we give a surjection from Rn to V? Or in other words, how can we find a set of generators? In fact, when we give a basis α1,,αn of V, φ has a matrix representation A, and α1,,αn are a set of k-generators of V, which are also a set of R-generators. Therefore, we consider the R-surjection determined by α1,,αnV ρ:RnV. Now to find the kernel of this mapping, we consider the matrix representation A, and obviously we have xi:=tei(a1ie1++anien)kerρ. Here eiRn is the standard basis, which gives us n generators x1,,xn of kerρ. Therefore, we can construct a mapping RnRn whose image corresponds to xi, and in fact, this mapping is described by the matrix tIAMn(R). Since tei=xi+(a1ie1+), we find that N=Rxi+kei is an R-submodule of Rn. Therefore, for any x=pi(t)eikerρ, it belongs to N, and can be written as x=qi(t)xi+ciei. Note that 0=ρ(x)=ciαi, we know that all ci=0. This shows that x is an R-linear combination of xi, and we have proved that xi are indeed a set of generators of kerρ.

We also need to prove that RnRn is an injection, which means that xi is a linearly independent set over R. To do this, let qi(t)xi=0. We have iqi(t)teii,jqjaijei=i(qitjqjaij)ei=0 This implies that tqi=jaijqj. Then we find that (q1,,qn)=Rqikqi. Since R is a PID, the left ideal is a principal ideal, let it be (d). If d0, since R is an integral domain, (d) should contain polynomials of any degree, but the right side kqi is a finite dimensional k-space and only contains polynomials of finite degree, which is impossible. Therefore, d=0, and we know that q1=q2==qn=0.

Corollary 4.2. We have the following short exact sequence of R-modules 0RnRnVA0. where RnRn is the map determined by tIAMn(R).

After having this basic exact sequence, we will examine how to specifically calculate the module structure of VA. Note that tIA is a matrix over a PID, so there exist invertible matrices P,QMn(R) such that P(tIA)Q=D=diag(d1,,dr,0,,0) where d1||dr, and diag denotes a diagonal matrix with these elements on the diagonal and 0 elsewhere. Then we have the following commutative diagram rendering math failed o.o Here we need the following simple lemma

Lemma 4.2. Let R be a (not necessarily commutative) ring, and let M and N be (let’s assume) left R-modules. If we are given the following commutative diagram with R-modules and R-module homomorphisms (except for γ) rendering math failed o.o and both rows are exact, then we can uniquely construct an R-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 mM and consider its preimage m in M. We map it to gβ(m) and define γ(m)=gβ(m). It is necessary to verify that this definition does not depend on the choice of preimage m. In fact, another preimage differs from m by an element in ker(g), which is equivalent to an element in Imf. Thus, we can denote the other preimage as m+f(m), and its image in N is g(β(m))+g(β(f(m)))=g(β(m))+g(f(α(m)))=g(β(m)). Therefore, the definition of γ does not depend on the choice of preimage m. Here we use commutativity. It is easy to verify that γ is indeed an R-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 α1 and β1, and define a commutative diagram as follows: rendering math failed o.o Then by the first part of the lemma, we can uniquely construct γ that commutes with the diagram. Note that 1M:MM is obviously a map that commutes with the first and third rows. Therefore, by uniqueness, γγ=1M, which implies that γ is an isomorphism. ◻

Now, since P,Q are invertible, Q1,P obviously define an isomorphic mapping. From this lemma, we know that an isomorphism can be constructed from VA to V, where VRn/DRn=R/(d1)R/(dr)Rnr. Note that VVA is also a k-module isomorphism, and is a finite-dimensional k-vector space, but R is not a finite-dimensional k-vector space, so n=r, d1|d2||dn is a nonzero element in R such that VAVR/(d1)R/(dn). Of course, it is not necessary to prove that VA is isomorphic to the above form, only the structure theorem for finitely generated R-modules is needed. However, the above process gives an explicit way to calculate the standard form of VA using the form of A.

Exercise 4.35 (). Prove that, when the following commutative diagram of R-module homomorphisms is given (where the rows are all short exact sequences) rendering math failed o.o a unique mapping α can be constructed to make the diagram commute. If β,γ are both isomorphisms, then α is also.

Exercise 4.36 (). Let KL be two fields, where K is a subfield of L. Prove that A,BMn(K) are similar over K if and only if they are similar over L.

Eigenvectors and Root Subspaces

In this section, we will discuss how to actually obtain a transition matrix P such that P1AP=D is our standard form, or equivalently, AP=DP. Let k be a field (e.g. an algebraically closed field like k=C) such that all elementary divisors of φ are products of linear factors (xλi)ki. 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 Vφλ(k(R/(tλ)k)nk). For each eigenvalue λ, the subspace k(R/(tλ)k)nk corresponds to a subspace of Vφ under this isomorphism, which we call the root subspace with respect to λ. It is given by Rλ:=kker(φλ)k. The subspace ker(φλ) is called the eigenspace with respect to λ, denoted by Vλ. 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 k-basis for a submodule of the form R/((tλ)k), and we know that the projection of 1R onto this submodule generates it. In other words, it has a basis (tλ)k1,,(tλ),1, 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 1R/((xλ)k) under the isomorphism to Vφ, denoted by α, then the k-basis for this subspace can be written as (φλ)k1α,,(φλ)α,α.

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 P. For a general φ, we need to find a basis for the root subspaces ker(φλ)k. Here are some examples to illustrate this.

Example 4.5. We consider the following matrix over the field k=Q: A=(1234),tIA=(t123t4). By performing elementary transformations on tIA, we get: (2t1t43)(20t4(t4)(t1)23)(100t25t2). Thus, the rational canonical form of A over Q is (0215). In other words, there exists an invertible matrix over Q such that A is similar to the above form. If we consider k=R or k=C (in fact, we only need k=Q(33)), then from t25t2=(t5+332)(t5332), we obtain its elementary factors, and thus it is similar to the following diagonal matrix over k: A=(5+332005332). This is the Jordan canonical form of A over any field k that contains Q(33).

To find P, consider its eigenspaces for the two eigenvalues λ1=5+332,λ2=5332, Vλ1=ker(Aλ1I) and Vλ2=ker(Aλ2I). Using the algorithm for calculating ker described in the previous sections (or solving the equations directly), we can compute the generators of these two spaces, which are the eigenvectors (2λ1), where λ=λ1,λ2 for the corresponding eigenvalues. Therefore (note that P does not need to be unique), P=(223+3323332) satisfies AP=PA, i.e. P1AP=A.

Example 4.6. Consider the following matrix over Q, transform it into Jordan canonical form J, and find the corresponding P such that P1AP=J. A=(2121122100110001). By performing elementary transformations on tIA, we can calculate its invariant factors (1000010000(t1)0000(t1)2(t3)) Thus, the elementary factors are (t1),(t1)2, and (t3). We then calculate ker(A1I)2 and obtain the root subspace R1 with the following basis (the basis is not unique and may differ from what others calculate) v1=(1100),v2=(2010),v3=(2001). By applying AI to these vectors, we find that the first two vectors fall into ker(AI), while the last one (AI)v3=e1e2+e3 belongs to ker(AI)2ker(AI). Therefore, we let α2=v3, which corresponds to the generator 1 in R/((t1)2), and its Jordan block corresponds to the basis (AI)α2,α2. We also need another eigenvector that does not belong to the space generated by k[φ]α2 to correspond to the other elementary factor (t1). It is clear that we can take α1=v1.

Finally, by simply calculating the feature vector ker(A3I), we find an eigenvalue of 3 and its corresponding eigenvector β=(1100) By arranging them in the order of α1,(AI)α2,α2,β and putting them into the matrix P, we obtain the desired transition matrix P=(1121110101000010),P1AP=(1000011000100003).

Exercise 4.37 (). In fact, in the calculation process of P in the above example, we can also reduce the amount of calculation by the following means.

  1. Let φ:VV be a general linear map on an n-dimensional space, and its minimal polynomial is of the form (tλ1)k1(tλ2)k2, where the two eigenvalues are distinct. Prove that Im(φλ1)k1=ker(φλ2)k2 ker(φλ1)k1=Im(φλ2)k2.

  2. Here, A returns to the A in the previous example. By calculating the matrix (A3I) and ker(A3I), find the eigenvector of λ=3, and use ker(AI)2=Im(A3I) to show that ker(AI)2 is directly generated by the columns of A3I, so there is no need to calculate (AI)2 and its kernel.

Exercise 4.38 (). The Fibonacci sequence is a unique sequence of positive integers determined by the initial conditions F1=1,F2=1 and the recurrence relation Fn+2=Fn+1+Fn. We can convert the above recurrence relation into matrix form (Fn+2Fn+1)=(1110)(Fn+1Fn). Let the matrix be denoted as A. By converting this matrix into Jordan canonical form over k=C, we can easily calculate An and derive the general formula for Fn.

Exercise 4.39 (). Is there a matrix X such that X2=(011001000)?

Invariants of Linear Maps

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

Determinant

Consider an n-dimensional k-vector space V and a linear map φ:VV. We consider an n-linear alternating function on V D(v1,v2,,vn):V×V××Vk. Here, n-linear means that D is linear in each variable vi, i.e. when fixing all other elements, viD(v1,,vi,,vn):Vk is a k-linear map. Alternating means that if two vectors are the same, e.g. vi=vj=v, then the value of the function is 0. D(v1,,v,,v,,vn)=0. As a consequence, this implies that when we swap the positions of two vectors vi,vj, the value of the function becomes the negative of its original value D(v1,,vi,,vj,,vn)=D(v1,,vj,,vi,,vn). This is because D(,vi+vj,,vi+vj,)=0, and using the n-linear expansion, we can obtain the above consequence. Now, we may ask, with all these strange conditions, can such a function even exist? We consider introducing a basis e1,,en for V, and consider the decomposition of vi in terms of this basis vi=ajiej. Then, by n-linearity, we have D(v1,)=j1aj11D(ej1,)=j1j2aj11aj22D(ej1,ej2,)==j1,,jnaj11ajnnD(ej1,,ejn) Since D(ej1,,ejn) requires no repeated elements in order to be non-zero, we only need to consider the case where kjk forms a permutation of {1,,n}. 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 D. Therefore, D(eσ(1),,eσ(n))=sgn(σ)D(e1,,en) Thus, D(v1,,vn)=(σSnsgn(σ)aσ(1)1aσ(n)n)D(e1,,en). It is easy to verify that the above expression defines a function that satisfies n-linearity and alternativity. Therefore, the desired function D exists. However, its definition seems to depend on the choice of the value of D(e1,,en) and a basis for V. In order to avoid the meaningless zero function, we choose D(e1,,en)0. For any mapping φ, we consider det(φ):=D(φ(e1),,φ(en))D(e1,,en) which is called the determinant of φ. If we write the matrix decomposition as φ(ei)=ajiej, according to the above formula, we know that this definition does not depend on the choice of the value of D(e1,,en) (as long as it is non-zero). Therefore, we can write the definition of the determinant for a matrix A as detA=σSnsgn(σ)aσ(1)1aσ(n)n. This is equivalent to assuming that the value of D(α1,,αn), where αi are the columns of A, is equal to 1 when D(e1,,en)=1. Interestingly, the definition of the determinant for φ also does not depend on the choice of the basis e1,,en! 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 V, and let A,BMn(k) be two matrices. Then, det(AB)=det(A)det(B).

Proof. Let the columns of A from left to right be α1,,αn, then the jth column of AB is b1jα1++bnjαn. By using a similar alternating sum expansion as before, we have det(AB)=σSnsgn(σ)bσ(1)1bσ(n)nD(α1,,αn)=σSnsgn(σ)bσ(1)1bσ(n)ndet(A)=det(A)det(B). ◻

Proof. It is easy to see that det(I)=1, so for an invertible matrix P, we have det(PP1)=det(P)det(P1)=1det(P1)=(detP)1. Therefore, for two similar matrices A=PAP1, their determinants are equal: det(A)=det(P)det(A)(detP)1=det(A). In fact, the determinant has a clear meaning: it is a kind of signed volume function in n-dimensional space, which describes the volume of the parallelotope formed by the vectors v1,,vn. The definition of this volume ultimately depends on the value of the "base volume" D(e1,,en). 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 Mn(R), where R is a commutative ring.

 ◻

Exercise 4.41 (). In this problem, let AMn(R) be a matrix over a PID.

  1. A is invertible if and only if det(A)R× is a unit.

  2. A defines an injection if and only if det(A)0.

  3. rankA<n if and only if det(A)=0.

Exercise 4.42 (). Let φ:VV be a k-linear map on an n-dimensional vector space, and let A be its matrix with respect to some basis. Prove the equivalence of the following statements:

  1. rankA=dimV.

  2. The columns of A span dimV.

  3. kerφ=0, i.e. φ is injective.

  4. detφ0.

  5. 0 is not an eigenvalue of φ.

  6. Ax=0 has no non-zero solutions.

  7. A is an invertible matrix and φ is an isomorphism.

Exercise 4.43 (). Let φ:VV be a linear map on an n-dimensional vector space over a field k. Define the polynomial pφ(t)=det(t1Vφ).

  1. pφ(t) is an invariant of φ under similarity, and its roots are all eigenvalues of φ. Therefore, it is called the characteristic polynomial of φ.

  2. Prove that pφ(t) is equal to the product of all invariant factors of φ, i.e. the product of all elementary factors.

  3. Prove the Cayley-Hamilton theorem pφ(φ)=0.

Tensor product

Let M and N be a right A-module and a left A-module, respectively. We can define an abelian group MAN, where the elements are generated by symbols of the form mn. The zero element is 00, and it satisfies the following three constraints:

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

  2. (Left linearity) (m+m)n=mn+mn,

  3. (Right linearity) m(n+n)=mn+mn.

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

Example 4.7. Let M=Z/2 and N=Z/3 be two Z-modules. Consider T=MZN=Z/2Z/3. This group is generated by all symbols of the form mn, where mZ/2 represents the residue class of the integer m.

  1. When m=0, we have 0=00, so 0n=(00)n=0(0n)=00=0, which is the zero element in T.

  2. Similarly, when n=0, m0=0.

  3. When m=1, we have 1=31, so 1n=(13)n=1(3n)=10=0.

Therefore, in this example, the tensor product (Z/2)Z(Z/3)=0. In fact, for (m,n)=1 coprime, we have (Z/m)Z(Z/n)=0.

Exercise 4.44. Observe the above example and answer: Is mn=0 equivalent to at least one of m,n being 0 in MAN?

Although in general, the MAN we define is just an Abelian group, similar to Hom, when either M or N has a bimodule structure, we can give MAN a module structure. Let’s give an example of how SMRRRN has a left S-module structure. This is because we can define, for sS, s(mn):=(sm)n.

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

Group Natural module structure Definition of S-module structure
MRRN
Z-module none
SMRRN
MRS,RN
Left S-module
s(mn):=(sm)n
s(mn):=m(sn)
MS,RRN
MRRNS
Right S-module
(mn)s:=(ms)n
(mn)s:=m(ns)

Exercise 4.45. Confirm that you understand all the situations in the table.

Example 4.8. Let M be a left A-module, and let ρ:AB be a coefficient extension homomorphism. Here, you can think of B as a ring with larger coefficients, such as QC. Then, since B can be viewed as a left B-right A-module, we can use tensor product to extend the A-coefficients of M to B-coefficients, resulting in a left B-module: N=BAM The balancing relation can be understood as b(am)=(bρ(a))m, since the right A-module structure of B is given by ρ.

Theorem 4.10 (Universal Property of Tensor Product).

  1. Let M and N be two Z-modules. Then any bilinear map B:M×NP can be decomposed as the composition of maps rendering math failed o.o where φ(m,n)=mn is a canonical map that depends only on M and N, and B:MNP is the unique map that makes the above diagram commute.

  2. Let M and N be two modules with right and left A-module structures, respectively. Then similarly, any Z-bilinear map B:M×NP that is A-balanced can be uniquely decomposed as Bφ:M×NMANP.

According to the definition, MN=F/I, where F=(m,n)M×NZ(mn) is the free module generated by all abstract symbols mn, and I is the submodule generated by all bilinear relations, I=(m+m)nmnmn,m(n+n)mnmnm,n. Given a bilinear map B:M×NP, we can define a Z-linear map fHomZ(F,P)=M×NHom(Z(mn),P) that satisfies mnB(m,n) uniquely. Its existence is guaranteed by the property of free modules. Since B is bilinear, it is obvious that f(I)=0 (because f is 0 on all generators of I, we have Ikerf), so we can make a quotient map f:F/IP:a+If(a), which is the B:MNP we need. The second part of the proposition is similar, and only requires minor modifications.

Corollary 4.3. HomZ(MAN,P)=Hom|A(M,HomZ(N,P)) Here, the left side corresponds to B in the proposition, and the right side corresponds to the A-balanced bilinear map B:M×NP.

Lemma 4.3. If V,W are k-vector spaces, then in VkW, vw=0v=0 or w=0.

Proof. () is obvious. For (), if v,w are both non-zero, we can construct k-linear functions f:Vk,g:Wk such that f(v),g(w)0. Then it is easy to verify that B(x,y):=f(x)g(y) is a k-balanced bilinear map, so it can be decomposed as B=Bφ:V×WVkWk. But B(v,w)=f(v)g(w) is not 0, so φ(v,w)=vw0. ◻

Exercise 4.46. Generalize the proposition to the case where M,N are right and left A-modules respectively. Here we need to add the appropriate assumption: M and N satisfy that any non-zero element has an A-linear function that does not take zero on that element.

Example 4.9. Let k be a field, V and W be two k-vector spaces. Obviously, they are two bi-k-modules, so we can define a k-linear space VkW. If V and W are generated by bases {ei} and {fj} respectively, then VkW is generated by the basis eifj. It is obvious that this basis can generate the entire VW, the difficulty lies in showing that {eifj}VW is linearly independent. Suppose there is a finite sum x=aijeifj=0 This implies that for any k-balanced bilinear map B:V×Wk, we have B(x)=0. Since (v,w)ei(v)fj(w) is obviously a k-balanced bilinear map, where ei represents the unique linear function on V that takes the value 1 on the basis ei and 0 on all other bases, applying this function to x gives us aij=0. Since i and j are arbitrary, this shows that all coefficients of x are 0.

Exercise 4.47 ().

  1. Can a natural linear mapping fg:VWVW be defined if there are two linear mappings f:VV and g:WW?

  2. Let V,V,W,W have bases ei,ei,fj,fj respectively, and let f,g have matrix representations A=(aij),B=(bij) with respect to the bases. Find the matrix representation AB of fg with respect to the natural bases {eifj},{eifj} of VW and VW respectively. You should be able to obtain the following form by arranging the bases in the appropriate order: (a11Ba1mBam1BammB). If you change the order of the bases, you can obtain the following matrix form: (b11Ab1nAbn1AbnnA). As a corollary, these two matrices must be similar. Usually, we define the former as the matrix AB.

Dual Space

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

In the simple case of a k-vector space V, V=Homk(V,k) is called the dual space of V. It can be understood as the vector space of all linear functions f:Vk on V. The interesting thing about the dual space is that it is a contravariant functor.

Theorem 4.11. The dual functor MM is a contravariant functor from left A-modules to right A-modules, meaning it maps a left A-module to a right A-module M, and maps a left A-module homomorphism f:MN to a right A-module homomorphism f:MN. This correspondence satisfies the law of composition, meaning that the composition LgMfN=LfgN is preserved by the dual functor (but because it is a contravariant functor, the direction of composition is reversed): LgMfN=L(fg)=gfN

Proof. In fact, this is a special case of the property of the Hom functor ()=HomA(,A) that we discussed earlier. Recall that it maps f:MN to f:MfN, i.e. it pulls back the linear function h:NA on N to the linear function hf:MNA on M through f:MN. ◻

Dual basis

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

Let V be generated by a basis {b1,,bn}. Then this basis is equivalent to an isomorphism φ:knV, which maps the standard basis {ei} of kn to φ(ei)=bi. Taking the dual functor of this mapping, we obtain kn(kn)φV By functoriality, φ is also an isomorphism. If we reverse the direction of φ, we get an isomorphism kn(kn)(φ)1V, which gives a basis for V, called the dual basis of {bi} and denoted by {bi}.

Specifically, ei is defined such that its image under φ is the function on kn that takes the ith coordinate, i.e. ei:knk. This satisfies biφ=ei Substituting ej gives bi(bj)=ei(ej)=δij Here, δij=1i=j is a symbol that equals 1 when i=j and 0 otherwise. This last line is also commonly used as an equivalent definition of the dual basis, since it can be linearly extended to all vectors by satisfying biφ=ei for all ejkn.

Matrix Representation of Dual Linear Mapping: Transpose

Let f:VW be a linear mapping between finite-dimensional vector spaces. After choosing bases vi and wi for V and W, respectively, we can represent f as a matrix A=(aij) such that f(vj)=iaijwi. Then, what is the matrix representation B=(bij) of the corresponding dual mapping f:VW under the dual bases vi and wi? We can calculate ibijvi=f(wj)=wjf, and substituting vi gives bij=wj(f(vi))=wjjajiwj=aji. This matrix is actually obtained by flipping all elements of A along the main diagonal, i.e. rows become columns and columns become rows. This operation is called the transpose of A, denoted as AT. 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. (AB)T=BTAT.

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

Exercise 4.48 (). Let V be a finite-dimensional vector space. Discuss how the dual basis changes when the basis changes. That is, if we have a basis {αi} and a new basis {βi} given by a coordinate transformation, βi=jajiαj, where A=(aij) is an invertible matrix. How can the corresponding dual basis βi be expressed in terms of αi?

Double Dual

Although V and V are not naturally isomorphic when the vector space is finite-dimensional, it is remarkable that V and V are naturally isomorphic.

Theorem 4.13. Let V be a finite-dimensional vector space. Then the map ev:VV:vevv is a natural isomorphism that does not depend on the choice of basis. Here, evv represents the linear map that maps a function f in V to evv(f)=f(v)k, i.e. the value of f at v.

Proof. It is easy to see that evv:VV is an element of V=(V). We will prove that this mapping is an isomorphism. Firstly, ev is obviously a linear mapping, since it calculates the value of linear functions. To prove this, we only need to show that ev is an injection, because in the case of finite dimension, we know that dimV=dimV=dimV.

If v0, we can always find a linear function f:Vk such that f(v)0 (for example, by extending v to a basis and then taking the dual basis f=v). In this case, evv(f)=f(v)0, so as an element of V, evv0. This proves that ev is an injection, and thus proves the proposition. ◻

If V is not finite-dimensional, V is usually very large, but we still have the natural monomorphism ev:VV mentioned above.

Field Extensions and Galois Theory


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

  2. It is also denoted as Cn or Z/nZ.↩︎

  3. We will mainly discuss finite groups.↩︎

  4. Strictly speaking, D3 is isomorphic to a subgroup of D6↩︎

  5. A relation is called an equivalence relation if it satisfies reflexivity aa, symmetry abba, and transitivity ab,bcac.↩︎

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

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

  8. Some books also use SX↩︎

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

  10. For SG, we use the notation CG(S) to represent {gG|gs=sg,sS}, which is called the centralizer of S.↩︎

  11. We can also define the right regular representation α:GSym(G)g(aag1)↩︎

  12. It is called induced representation because it is actually IndHGV0=gG/HgV0, where V0 is the trivial one-dimensional representation of H.↩︎