Agoston M.K. Computer Graphics and Geometric Modelling: Mathematics

Подождите немного. Документ загружается.

If ker(j) = 0, then G ª Z; otherwise,

for some n Œ Z and G ª Z

Deﬁnition. Let G be a group and let g be an element of G. Deﬁne the order of g, o(g),

to be the smallest of the integers k > 0, such that g

= 1, if such integers exist; other-

wise, deﬁne the order of g to be •.

B.4.21. Example. Let G = Z

= {0,1,2,3,4,5}. Then o(1) = 6 = o(5), o(2) = 3 = o(4),

o(3) = 2, and o(0) = 1.

Deﬁnition. The number of elements in a group G is called the order of G and is

denoted by o(G). If G has only a ﬁnite number of elements, then G is called a group

of ﬁnite order, or simply a ﬁnite group.

Note that two ﬁnite groups of the same order need not be isomorphic.

B.4.22. Theorem. (Lagrange) Let G be a ﬁnite group.

(1) If H is a subgroup of G, then o(H) | o(G). In fact, if n is the number of cosets

of H in G, then o(G) = n o(H). The number n is called the index of H in G.

(2) If g Œ G, then o(g) | o(G).

Proof. Part (1) follows from the fact that G is a union of disjoint cosets of H, each

of which has the same number of elements. To prove (2), one only has to observe that

o(g) = o(Zg) and apply (1).

Deﬁnition. A commutator of a group G is any element in G of the form ghg

-1

where g, h Œ G.

B.4.23. Theorem. The set of ﬁnite products of commutators of G is a normal sub-

group H called the derived or commutator subgroup of G. The factor group G/H is

abelian and called the abelianization of G.

Proof. See [Dean66].

Finally, we want to deﬁne a free group. Basically, a free group is a group in which

no “nontrivial” identities hold between elements. An example of a trivial identity is

-1

= 1, which holds for all elements g in a group. A nontrivial identity would be

something like g

= 1, if that were to hold for all elements g

. Although the idea

ker j

()

=Œ

{}

kn k Z

j kkg

()

= .

j : Z Æ G

B.4 Groups 829

of a free group is fairly simple, the deﬁnition is surprisingly complicated. We shall

sketch it only.

Let S be any set of elements called symbols. Think of the elements of S as the

letters in an alphabet S. A reduced word in S will refer to any formal string of the form

where s

Œ S, n

Œ Z, and we have made all possible elementary contractions. An ele-

mentary contraction involves replacing occurrences of the form s

by s

n+m

, occur-

rences of s

by 1, and occurrences of 1·s for s·1 by s. For example, if S = {a,b,c}, then

-7

is a reduced word but a

-2

bc is not since it can be reduced to bc. Let F(S) denote

the set of reduces words in S. If u, v Œ F(S), deﬁne u·v to be the element of F(S) obtained

by concatenating u and v and then reducing the result as much as possible.

B.4.24. Lemma. (F(S),·) is a group.

Deﬁnition. (F(S),·) is called the free group generated by S. The elements of S are called

generators of the group F(S).

A key property of free groups is that they satisfy a universality property with

respect to being able to extend maps of S into a group to a homomorphism of F(S).

B.4.25. Theorem. Let G be any group and let h :S Æ G be any map. Then h extends

to a unique homomorphism H:F(S) Æ G.

Proof. See [Fral67]. To put it another way, each h lifts to a unique map H so that

we have a commutative diagram

ss s

◊◊◊

830 Appendix B Basic Algebra

inclusion map i

F(S)

This universal factorization property is what actually deﬁnes the free group F(s) in the

sense that if K is any other group containing S and satisfying this property, then K is

isomorphic to F(S).

Deﬁnition. Let G

, G

,..., and G

be groups. The direct product of the G

, denoted

by G

¥ G

¥ ···¥ G

, is the group (G

¥ G

¥ ···¥ G

,·), where the operation · is deﬁned

(The operations on the right are the operations from the groups G

It is easy to check that (G

¥ G

¥ ···¥ G

,·) is a group.

gg g gg g gggg gg

nn nn12 12 1122

, ,..., , ,..., , ,..., .

()

◊¢¢ ¢

()

=◊¢◊¢ ◊¢

()

B.5 Abelian Groups

In this section we concentrate on abelian groups and we shall use the standard addi-

tive notation.

Deﬁnition. Let G be an abelian group and let g

, g

,..., g

Œ G. Then

is called the subgroup of G generated by the g

, g

,..., and g

It is easy to show that Zg

+ Zg

+ ···+ Zg

is in fact a subgroup of G and also that it

is the intersection of all subgroups of G which contain the elements g

, g

,..., and g

B.5.1. Lemma. For any abelian group G the elements of ﬁnite order form a unique

subgroup T(G) called the torsion subgroup of G.

Proof. The proof is clear since o(0) = 1, o(-g) = o(g), and o(g + h) | o(g)o(h) for all

g, h Œ G.

Deﬁnition. An abelian group G is said to be torsion-free if it has no element of ﬁnite

order other than 0, that is, T(G) = 0.

Clearly, G/T(G) is a torsion-free group for every abelian group G.

Deﬁnition. An abelian group G is said to be ﬁnitely generated if

for some g

, g

,..., g

Œ G. In that case, the g

are called generators for G.

B.5.2. Example. All cyclic groups are ﬁnitely generated.

B.5.3. Example. The group Z

is not cyclic, but it is ﬁnitely generated since

= Z(1,0) + Z(0,1). A similar statement holds for Z

, n ≥ 2 .

B.5.4. Example. The groups Q and R are not ﬁnitely generated.

B.5.5. Lemma. Subgroups of ﬁnitely generated abelian groups are ﬁnitely

generated.

Proof. See [Dean66].

Deﬁnition. Let G

, G

,..., and G

be abelian groups. The external direct sum of the

, denoted by G

ƒ G

ƒ ···ƒ G

, is the group (G

¥ G

¥ ···¥ G

,+), where the oper-

ation + is deﬁned by

GZg Zg Zg

=++◊◊◊+

ZZ Z Zgg gngng ngn

kkki12 1122

+ +◊◊◊+ = + +◊◊◊+ Œ

{}

B.5 Abelian Groups 831

It is easy to check that (G

¥ G

¥ ···¥ G

,+) is an abelian group. Except for the

different name and notation that is used in the abelian case, the external direct sum

is just the direct product deﬁned at the end of the last section.

B.5.6. Example. The groups Z

and R

are the external direct sums of n copies of

Z and R, respectively.

Deﬁnition. Let G

, G

,..., and G

be subgroups of an abelian group G. Deﬁne the

sum of the groups G

, denoted by G

+ G

+ ···+ G

, by

It is easy to show that G

+ G

+ ···+ G

is a subgroup of G.

Deﬁnition. If G

, G

,..., and G

are subgroups of a given abelian group G and if

each element g in G can be written uniquely in the form g

+ ···+g

with

in G

, then G is called the internal direct sum of the groups G

and we write

G = G

≈G

≈ ···≈G

Because it is easily shown that G

≈G

≈ ···≈G

is isomorphic to

ƒG

ƒ ···ƒG

, one usually does not distinguish between internal and external

direct sums and uses the same symbol ≈ to denote either direct sum. The context

decides which is being used. One also uses the summation notation, so that the

expressions

will all refer to the same object.

B.5.7. Theorem. (The Fundamental Theorem of Finitely Generated Abelian

Groups) Let G be a ﬁnitely generated abelian group. Then

for some r, t ≥ 0, where 1 < n

Œ Z and n

| n

i+1

if t > 0. The integer r is called the rank of

G and is denoted by rank(G). The integers n

, n

,..., and n

are called the torsion coef-

ﬁcients of G. Both the rank and the torsion coefﬁcients are uniquely determined by G.

Proof. See [Dean66].

Note that the example

ZZZ

236

≈ª

nn n

ª ≈ ≈◊◊◊≈ ≈ ≈ ≈◊◊◊≈ZZ ZZ Z Z

1244 344

G G G G G G and G

i12 12

≈ ≈◊◊◊≈ ƒ ƒ◊◊◊ƒ ≈

GG G gg ggG

nnii12 12

+ +◊◊◊+ = + +◊◊◊+ Œ

{}

gg g gg g g gg g g g

nn nn12 12 1 12 2

, ,..., , ,..., , ,..., .

()

+¢¢ ¢

()

=+¢+¢ +¢

()

832 Appendix B Basic Algebra

shows that the condition that n

divides n

i+1

is important for the uniqueness part of

Theorem B.5.7.

B.5.8. Theorem. Assume that G, H, and K are ﬁnitely generated abelian groups.

(1) If j:K Æ G and y:G Æ H are homomorphisms satisfying

(a) j is injective,

(b) im(j) = ker(y), and

then

(2) The function rank is “additive”, that is,

Before proving Theorem B.5.8, we introduce some more notation.

Deﬁnition. The subset {g

,...,g

} of an abelian group G is said to form a basis

for G provided that

(1) G = Zg

+ Zg

+ ···+ Zg

, and

(2) if k

+ k

+ ···+ k

= 0, for k

Œ Z, then k

= 0 for all i.

It is easy to show that {g

,...,g

} is a basis for the group G if and only if

Thus, by Theorem B.5.7 each ﬁnitely generated group has a basis.

Deﬁnition. Any abelian group which is isomorphic to G

≈G

≈ ···≈G

, where each

is isomorphic to Z, is called a free abelian group.

It follows easily from Theorem B.5.7 and the deﬁnitions that the following con-

ditions on a ﬁnitely generated abelian group are equivalent:

(1) G is free.

(2) G is torsion-free.

(3) G has a basis consisting of elements of inﬁnite order.

Proof of Theorem B.5.8. To prove part (1), assume without loss of generality that

all three groups G, H, and K are torsion-free. Let {h

,...,h

} and {k

,...,k

} be

bases for H and K, respectively, where s = rank(H) and t = rank(K). Choose elements

, g

,..., and g

in G such that y(g

) = h

. It is now easy to show that

jj jkk kgg g

ts12 12

()() (){}

, ,..., , , ,...,

Gg g g

= ≈ ≈◊◊◊≈ZZ Z

rank H K rank H rank K≈

()

rank G rank K rank H

()

B.5 Abelian Groups 833

forms a basis for G. In other words,

Part (2) follows from (1) by letting G = H ≈ K and letting j and y be the natural

inclusion and projection map, respectively, and the theorem is proved.

B.5.9. Theorem. Let G be a free abelian group with basis {g

,...,g

} . If H is any

group and h

, h

,..., h

Œ H, then there exists a unique homomorphism j:G Æ H

such that j(g

) = h

Proof. Show that any element g of G has a unique representation of the form

and deﬁne

Free abelian groups behave very similarly to free groups. Compare Theorem B.5.9

with Theorem B.4.25. There is also an analogous commutative diagram to describe

what is going on and we again have a universal factorization property. Alternatively,

Theorem B.5.9 can be paraphrased by saying that, given a free group G and any other

group H, in order to deﬁne a homomophism from G to H it sufﬁces to deﬁne it on a

basis of G, because any map from a basis of G to H extends uniquely to a homo-

morphism of G. The freeness of G is important because consider

and deﬁne

The map j does not extend to a homomorphism j: Z

Æ Z. Of course, although 1 is

a basis for Z

, the group Z

is not a free group and so there is no contradiction.

Next, let G and H be groups.

Deﬁnition. Let

and if h

Œ hom(G,H), then deﬁne

h hghghgforgG

12 1 2

()()

()

Œ .

hhGH

+Æ:

hom , :GH h h G

()

=Æ

{}

H is a homomorphism

j11

()

=ŒZ.

G ==

{}

012,,

j gkhkh kh

()

= + +◊◊◊+

11 22

gkg kg kg k

nn i

= + +◊◊◊+ Œ

11 22

,,Z

rank G t s rank K rank H

()

=+=

()

834 Appendix B Basic Algebra

B.5.10. Lemma. (hom (G,H),+) is an abelian group.

Proof. Straightforward.

B.5.11. Lemma. Let G be any group that is isomorphic to Z. If h Œ hom (G,G), then

there is a unique integer k such that h(g) = kg for all g in G.

Proof. Since G is isomorphic to Z, there is some g

in G so that G = Zg

. It fol-

lows that h(g

) = kg

for some integer k, because {g

} is a basis for G. The fact that

o(g

) =•implies that the integer k is unique. Now let g be any element of G. Again,

there is some integer t with g = tg

. Thus,

and the lemma is proved.

Lemma B.5.11 implies that if G ª Z, then hom (G,G) = Z1

ª Z.

B.6 Rings

Deﬁnition. A ring is a triple (R,+,·) where R is a set and + and · are two binary oper-

ations on R, called addition and multiplication, respectively, satisfying the following:

(1) (R,+) is an abelian group.

(2) The multiplication · is associative.

(3) For all a, b, c Œ R we have

(a) (left distributativity)

(b) (right distributativity)

Two standard examples of rings are Z and Z

Deﬁnition. A ring in which the multiplication is commutative is called a commuta-

tive ring. A ring with a multiplicative identity is called a ring with unity. An element

of a ring with unity is called a unit if it has a multiplicative inverse in R.

Deﬁnition. Let (R,+,·) be a ring. If A is a subset of R and if (A,+,·) is a ring, then

(A,+,·) is called a subring of R.

Note. From now on, like in the case of groups, we shall not explicitly mention the

operations + and · for a ring(R,+,·) and simply refer to “the ring R.” Products “r · s”

will be abbreviated to “rs.”

Deﬁnition. A subset I of a ring R with the property that

(1) I is an additive subgroup of R (equivalently, a - b Œ I for all a, b Œ I), and

(2) ra, ar Œ I for all r Œ R and a Œ I,

abc ac bc+

()

◊= ◊

()

+◊

()

abc ab ac◊+

()

=◊

()

+◊

(

)

hg htg thg tkg ktg kg

()

0000

B.6 Rings 835

is called an ideal of R.

An ideal is a subring. Note that if the ring R is commutative, then we can replace

condition (2) in the deﬁnition of an ideal by

(2¢) ra Œ I for all r Œ R and a Œ I.

Deﬁnition. Let R and R¢ be rings. A map h : R Æ R¢ is said to be a (ring) homomor-

phism if

for all a, b Œ R. If h is a bijection, then h is called a (ring) isomorphism.

Deﬁnition. Let h :R Æ R¢ be a homomorphism between rings. The kernel of h, ker

h, and the image of h, im(h), are deﬁned by

and

B.6.1. Theorem.

(1) The image of a ring homomorphism is a subring.

(2) The kernel of a homomorphism is an ideal.

(3) A ring homomorphism is an isomorphism if and only if its kernel is 0.

Proof. See [Fral67].

Deﬁnition. Let I be an ideal in a ring (R,+,·). The factor or quotient ring of the ring

R by the ideal I, denoted by (R/I,+,·), is deﬁned as follows: The additive group (R/I,+)

is just the quotient group of (R,+) by the subgroup (I,+). The operation · is deﬁned by

Using the deﬁnition of an ideal it is easy to check that the quotient ring of a ring

R by an ideal I is in fact a ring and that the map

that sends an element into its coset is a surjective ring homomorphism with kernel I.

In analogy with the integers one can deﬁne a notion of congruence.

Deﬁnition. Let I be an ideal in a commutative ring R. Let a, b Œ R. We say that a

and b are congruent modulo I, or mod I, and write

RRIÆ

r I s I rs I+

()

◊+

()

=+.

im h h r r R

()

{}

ker h r R h r=Œ

()

{}

h a b h a h b and

hab hahb

()

()()

836 Appendix B Basic Algebra

if a - b Œ I.

It is easy to show that ∫ is an equivalence relation on R and the equivalence classes

are just the cosets of the additive subgroup of R.

Deﬁnition. Let r

, r

,..., and r

be elements of a commutative ring R. then

is called the ideal generated by the r

It is easy to show that <r

,...,r

> is an ideal.

Deﬁnition. If r is an element of a commutative ring R, then <r> is called the prin-

cipal ideal generated by r in R.

Deﬁnition. An ideal I in a ring R, I π R, is called a maximal ideal if, whenever J is

an ideal of R with I Õ J Õ R, then either J = I or J = R.

Deﬁnition. A commutative ring R, I π R, with identity is said to be an integral domain

if ab = 0 implies that either a = 0 or b = 0.

Deﬁnition. An integral domain is called a principal ideal domain (PID) if all of its

ideals are principal ideals.

The ring of integers is a good example of a principal ideal domain.

Deﬁnition. Let a and b be elements of a commutative ring R. We say that b divides

a, denoted by b|a, if b is nonzero and a = bc, for some c in R. One calls b a factor or

divisor of a in this case.

Deﬁnition. Let R be a commutative ring with unity. Two elements a and b in R are

said to be associates if a = ub, where u is a unit.

Deﬁnition. Let R be an integral domain. An element a in R is said to be irreducible

(1) a is not 0,

(2) a is not a unit,

(3) for all b in R, if b|a, then b is a unit or b is an associate of a.

Deﬁnition. An integral domain is called a unique factorization domain (UFD)

provided that

(1) Every nonzero element r is either a unit or a product of irreducible

elements.

(2) If

rpp p qq q

= ◊◊◊ = ◊◊◊

12 12

< >= + +◊◊◊+ Œ

{}

rr r ar ar ar a R

kkki12 11 22

, ,...,

ab I∫

()

mod ,

B.6 Rings 837

where the p

and q

are irreducible elements, then n = m and upon renum-

bering we may assume that p

and q

differ by a unit factor.

The ring of integers is the standard example of a UFD.

B.6.2. Theorem. Every PID is a UFD.

Proof. See [Fral67].

Deﬁnition. Let I and J be ideals in a commutative ring R. Deﬁne the product of I

and J, denoted by I·J or IJ, by

Deﬁne the sum of I and J, denoted by I + J, by

It is easy to show that I·J, the set of ﬁnite linear combinations of products of

elements from I and J, is actually an ideal. One can rephrase the deﬁnition of an ideal

in a commutative ring R as follows:

One can also show that the sum of ideals is an ideal. In fact, if I, J, and K are ideals,

then the following properties hold:

(1) Associativity: I ·(J·K) = (I·J) · K

(2) Commutativity: I·J = J·I

(3) Distributivity: I·(J + K) = I·J + I·K

(I + J)·K = I·K + J·K

What this means is that using the product and sum on ideals along with standard set

operations, one can deﬁne a factorization theory for ideals.

Deﬁnition. Let I and J be ideals in a commutative ring R. We say that I is a divisor

of J and that J is a multiple of I if I

傶

For example, <5> is a divisor of <15> and <15> is a multiple of <5> in Z.

Deﬁnition. An ideal I in a commutative ring R is called a prime ideal if, whenever ab

lies in I for some elements a and b in R, then either a or b belongs to I. Equivalently,

the ideal I is prime if ab ∫ 0 (mod I) implies that either a ∫ 0 (mod I) or b ∫ 0 (mod I).

For example, <7> is a prime ideal in Z.

B.6.3. Theorem. Let R be a commutative ring with unity element and let I be an

ideal in R. Then I is a prime ideal if and only if R/I is an integral domain.

An ideal is an additive subgroup I with R I I◊Õ.

IJ abaIbJ+= + Œ Œ

{}

I J a b a b a b a I and b J for all i

nn i i

◊ = + +◊◊◊+ Œ Œ

{}

11 22

838 Appendix B Basic Algebra