Constructing Homomorphisms via Structure-Preserving Extensions

In this post, we study methods of constructing a group homomorphism by first constructing a funciton on a generating set and extending it in a homomorphic way.

This post consists of two parts: the regular text, and the red text. You are strongly advised to skip the part in red on the first read.

1. Linear Extensions

We first consider a linear-algebraic analogue. Let be a linear transformation between two vector spaces and over a field . Take a basis of . Since every vector in can be written in the form , we see that the image of a generic vector in under is of the form

.

In other words, the values of the linear transformation are completely determined by the values of on the basis vectors . This suggests the following:

Proposition 1.1. Let and be vector spaces over a field . Assume that is a basis of . Given a function , the linear extension of defined by setting

is a linear transformation. Moreover, . (See also the first universal property of free vector spaces.)

Proof. We forced to be linear, didn’t we?

Example 1.2. Let , , and . The collection forms a basis of . We define a function by setting , , and . The linear extension of is given by the formula

so that . is easily seen to be linear.

Suppose we want to determine injectivity or surjectivity of a linear extension of . For this, we need additional information about how interacts with the codomain . For example, if spans , then the linearity of implies that is surjective. Similarly, if is a linearly independent set in , then must be injective. We can codify this observation in the following generators-to-generators principle:

Proposition 1.3. Let and be vector spaces over a field . Take bases and of and , respectively. Given a function , the linear extension defined in Proposition 1.1 is injective if is injective and is surjective if is surjective. (See also the second universal property of free vector spaces.)

Proof. If is injective, then is a linearly independent subset of . Since , we see that every element of can be written uniquely as a finite linear combination of elements in . Therefore, if for some , then we can find and scalars such that

.

It follows from the definition of that . We conclude that is injective.

If is surjective, then is a spanning set of . Since , we conclude that is surjective.

Example 1.4. The linear map in Example 1.2 is surjective. (Check this!)

2. Generators

In order to develop a group-theoretic analogue of the method of linear extensions, we must formulate a group-theoretic analogue of vector bases.

Definition 2.1. Let be a group and be a subset of . The subgroup of generated by is the smallest subgroup of that contains , i.e.,

H,

the intersect of all subgroups of that contain . If , then we say that is a generating set of ; in this case, elements of are said to be generators of . We say that is finitely generated if there exists a finite set such that . In this case, we often write .

In order to justify the use of the term subgroup, we establish the following:

Proposition 2.2. Let be a group and be a collection of subgroups of . The intersection is a subgroup of .

Proof. Since for each , we see that .

To show that is closed under group operation, we fix . This implies that for all . Since each is a subgroup of , we conclude that for all . It now follows that , as was to be shown.

It remains to show that is closed under the inverse operation. To this end, we fix . This implies that for all . Since each is a subgroup of , we conclude that for all . It now follows that , as desired.

We now show that, just like vector bases, we can construct from generators any element of a group by a finitary process.

Proposition 2.3. Let be a group and be a subset of . We let and define, for each , the set

.

We then have the identity

.

Remark. signifies the collection of all -fold products of elements in or their inverses. The claim, then, is that corresponds to the collection of all finite products of generators and their inverses.

Proof. For notational convenience, we set . Since is a group that contains , it also contains . By applying the closure property repeatedly, we see that for all . It follows that .

To establish the reverse inclusion, we show that is a subgroup of . is then a subgroup of containing , whence we must have the inclusion relation .

It therefore suffices to show that . To this end, we first observe that for any fixed . Secondly, if we are given , then we can find such that and . It then follows that

.

Finally, if , then we can find such that , whence

.

We conclude that .

Example 2.4. We say that a group is cyclic if there exists an element such that . The main example is the group of integers , which is generated by . For each , the set is a subgroup of . Since is an abelian group, every subgroup of is normal, whence we can form the quotient group

,

where . Since , the quotient group is cyclic as well.We note that not every generating set of a cyclic group is of cardinality one. Indeed, and so on.

Example 2.5. Consider , the symmetric group on three letters. We claim that is a generating set for : see the Wikipedia page on cycle notation. To establish the claim, we first observe that . Now:

  • ;
  • ;
  • ;

this verifies the claim.

It is a general fact that , the symmetric group on letters, is generated by 2-cycles.

Example 2.6. (Presentation of groups via generators and relations). We define the free group on letters , denoted by , as follows. We first define the symbol to be the identity element of . For each , we define the symbol to be the inverse of , and declare that . Let and . For each , we define a word of length m to be the string

where such that for all . In other words, a word of length is a string of letters and their inverses, written down in a way that no two adjacent symbols cancel each other out. For example, is a word of length 6, whereas is actually a word of length 2, because and cancel out.

We now define to be the collection of all words of finite length, and define the group product of two words and to be the concatenation

of the words. In order for the concatenation to be a word, we must prune out the symbols that cancel each other out: if , then we take out both . The reduced concatenation is the resulting string; if no symbol is left, then the we declare the reduced concatenation to be . For example, the product of and is

,

a word of length 3. The product of and is

,

a word of length 1. We observe that the inverse of a word is . Indeed,

and

.

A relation on is an equivalence relation on . For example, for all is the abelian relation on , since we have identified with . We define the “relation set” , so that if and only if . We now let be the normal closure of , viz.,

By construction, is a normal subgroup of , so we can construct the quotient group . Since contains , the quotient group must be abelian. Indeed, given , the commutator is in , whence the coset is equal to the identity coset .

In a similar manner, we can define a group generated by subject to relations as follows. Given a finite set of generators, we construct the free group , where is the number of generators. We let be a collection of equivalence relations on and define the “relation set” by declaring if and only if for some . We then take to be the normal closure of and define

.

is then the group of all words generated by , with the condition that two words and are identified in case for some .

It is typical to write out the relations using the symbol, rather than the symbol. For example, the abelian group example above can be written as . This notation also suggests the following general fact. If is a group such that , then we can work out the relations that the generators satisfy as follows: whenever the two products of generators are equal in , the equal-relation induces an equivalence relation on . We collect all such equivalent relations in and generate the set as above. Taking the normal closure of , we see that the quotient group is essentially the same as , having been generated by generators subject to the same relation. See Example 3.3 for a concrete example

We conclude with a general remark. Echoing the universal property of free vector spaces, we can also work out a universal-property characterization of free groups. Given a set , we define the free group on to be the group containing as a subset such that each function into another group admits a group homomorphism such that the following diagram commutes:

universal property of free groups

Here is the canonical injection map . A group is said to be free if it is isomorphic to the free group generated by some set. is isomorphic to the free group generated by one letter. The symmetric group , as well as the groups presented in the next two examples, are not free. This is in stark contrast with vector spaces, as every vector space is free. The key difference is that vector spaces admit bases, whereas groups, in general, do not. A good w way to think about freeness as an algebraic property is “it has a basis”, although this isn’t entirely accurate.

Example 2.7. , the dihedral group of degree , is defined to be , the group generated by and , subject to the relations

  1. ;
  2. ;
  3. .

We show that is a group of order . We first note that every word (see Example 2.6) in can be written in the form ; this is a consequence of relation 3. Indeed, we see, for example, that

Now, by relations 1 and 2, we have the restriction and . Therefore, there are unique elements of .

Example 2.8. , the group of unit quaternions, is the group generated by , , , and subject to the relations

  1. ;
  2. ;
  3. ;
  4. ;
  5. ;
  6. ;
  7. ;
  8. ;
  9. ;
  10. .

Here we have denoted the inverses of , , and by , , and , respectively.

The relations show that every word (see Example 2.6) in is of length 1, as any multi-letter word can be reduced to a one-letter word. There are 8 unique words of length 1 in : ,, , , , , , .

3. Homomorphic Extensions

Let us now return to the task of developing a group-theoretic analogue of the method of linear extensions. One key difference between generators of a group and basis elements of a vector spaces is that the former does not provide a unique presentation of a generic element.

Example 3.1. Consider , the dihedral group of degree 4 (see Example 2.7). It is true, for example, that

It is crucial to note that group elements are subject to various relations that differ from group to group (see Example 2.6), whereas all vectors are subject to the same relations. (Formally, not every group is free, but every vector space is free; see Example 2.6.) This causes naïve adaptations of the method of linear extensions to fail, as illustrated in the example below.

Example 3.2. Consider the group of integers and the group of integers mod 3. Observe that and . The map defined by setting and declaring

is not a group homomorphism, despite the obvious attempt to force to be structure-preserving Indeed, , whereas

Moreover, does not map , the identity element in , to , the identity element in .

In using the generators-to-generators trick, then, we must take the relations imposed on the domain group and the codomain group into consideration.

Example 3.3. The direct product of the symmetric group on three letters and the cyclic group is a nonabelian group, as the subgroup is nonabelian. Since and , the argument below shows that .

The order of the direct product of two finite groups and is . Indeed, if and , then

It follows that is a normal subgroup of . Now, the mapping defined by the formula is easily seen to be a bijection. Since and , we conclude from Lagrange’s theorem that

as was to be shown.

Note that is an element of order 6—see the Wikipedia page on cycle notation for the definition of —as we can explicitly compute the 6 powers:

  1. ;
  2. ;
  3. ;
  4. ;
  5. ;
  6. .

We now set , which is easily seen to be an element of order 2. Since , we see that

We claim that generate . To prove this, it suffices to show that is contained in , the subgroup generated by and . Assume the inclusion relation for the sake of the argument. We have seen in Example 2.5 that the 2-cycles generate ; this, in particular, implies that is contained in . Since is in , elements of the form for arbitrary are also in . It follows that the full group is contained in , whence .

Now, and , and so

  • ;
  • ;
  • ;
  • .

It follows that is generated by and , which, in turn, are subject to the relations

  1. ;
  2. ;
  3. .

Recall now that , the dihedral group of degree 6 (see Example 2.7). Indeed, is a nonabelian group of order 12 generated by two elements subject to the same relations!

We define a mapping by setting for all . This is a homomorphic extension of the generators-to-generators mapping given by setting , ; indeed, an equivalent way of defining is to declare that

for all , which is resminiscent of the linear extension definition in Proposition 1.1. To check that is a group homomorphism, we fix . Since , we apply relation 3 repeatedly to conclude that

Since the exponents were arbitrary, we conclude that is a group homomorphism. By restricting the exponents to and , we see that is a bijection. It follows that .

What the above example shows is that the generators-and-generators trick for constructing homomorphisms works if two groups in question have the same number of generators that are subject to the same relations. This appears to be too stringent of a condition, however, as we expect such groups to be isomorphic, anyway. (If a group is generated by , subject to a set of relations , then is isomorphic to , where is the free group on , and is the normal closure of the set generated by the relations ; see Example 2.6.)

In fact, having merely compatible relations suffices, as the next example shows.

Example 3.4. Consider , the dihedral group of degree 4 (see Example 2.7). We note that is a normal subgroup of . Indeed,

for all . The quotient group is then generated by and , which are now subject to the relations

  1. ;
  2. ;
  3. .

This stems from the fact that .

Now, we know an abelian group with two generators, both of order 2: . Analogously as in Example 3.3, we can define a group homomorphism by setting . is an isomorphism.

This suggests, however, that defined by setting should also be a group homomorphism, and it indeed is. In fact, is a homomorphism with , and is just the induced homomorphism from that we obtain when we invoke the first isomorphism theorem.

The takeaway point is as follows. While and do not share the same relations, we can make some identifications in to recover the relations for the generators of . For example, can be “turned into” an element by making the identification , as 4 is divisible by 2. It would not be possible to turn into an element of order 3, whence we cannot expect the mappping given by the same formula to be a group homomorphism. Indeed, , but

and so is not even well-defined.

This isn’t to say that the number of generators in the domain group should match up with the number of generators in the codomain group. Remember: generators do not behave like vector-spaces bases. It doesn’t even make sense to talk about the number of generators of a group. Moreover, we can just map multiple generators to one generator, or simply create a non-surjective map that misses some generators in the codomain group.

Example 3.5. The mapping defined by the formula is a surjective homomorphism.

Example 3.6. The mapping defined by the formula is an injective homomorphism.

Here is a good rule of thumb for creating group homomorphisms via homomorphic extensions:

  1. send generators to generators;
  2. extend in a structure-preserving way (as described above several times);
  3. make sure that the identity element gets sent to the identity element;
  4. check that the function is well-defined.

Once you have many examples under your belt, you will be able to see intuitively when structure-preserving extensions work. We conclude the post with an application to the classification of cyclic groups.

Example 3.7 (Cyclic groups). Let be a cyclic group, so that for some . We shall show that is isomorphic to either or for some ; see Example 2.4.

We define a mapping by setting . is evidently a well-defined surjective function. Moreover,

,

and so is a homomorphism.

We now invoke the first isomorphism theorem to obtain the isomorphic relation . If is trivial, then . If is nontrivial, then we determine as follows. Since is nontrivial, there exists at least one nonzero element of . is closed under taking inverses, and so contains at least one positive integer. We let be the smallest positive integer in .

We claim that . If not, then, by long division, we can find a positive integer such that , where and . Since is closed under taking inverses, is in . Now, is closed under the group operation, and so is in . This is evidently absurd, as was assumed to be the smallest positive integer. We conclude that , whence .