The Unapologetic Mathematician

Mathematics for the interested outsider

Carnival time again

The 7th Carnival of Mathematics is up over at nOnoscience, including my latest discussion of knot coloring.

Advertisements

May 4, 2007 Posted by | Uncategorized | Leave a comment

Some examples of modules

Today I want to run through a bunch of examples of the constructions we’ve been considering for modules. I’ll restrict to the case of a ring R with unit.

One easy example of an R-module that I’ve mentioned before is the ring R itself. We drop down to the underlying abelian group and then act on it using the ring multiplication. There are both left and right actions here: r\cdot x=rx and x\cdot r=xr where r and x are ring elements, x considered as an element of the module. We’ll start off by taking this module and sticking it into some of the constructions.

When we consider \hom_{R-{\rm mod}}(R,M) for some left R-module M the left module structures on R and M will get eaten and the right module structure on R will get flipped over, leaving us a left R-module. We can pick an element f\in\hom_{R-{\rm mod}}(R,M) by specifying f(1)\in M. Then f(r)=f(r\cdot1)=r\cdot f(1), telling us where everything else goes. If we write f_m for the homomorphism with f_m(1)=m, then the left action of R on homomorphisms says
\left[r\cdot f_m\right](1)=f_m(r\cdot1)=r\cdot f_m(1)=r\cdot m
Thus r\cdot f_m=f_{r\cdot m}. This means that \hom_{R-{\rm mod}}(R,M)\cong M as left R-modules.

On the other hand, if we consider \hom_{R-{\rm mod}}(M,R) we get a right R-module. This consists of all R-linear functions from M to the ring R itself. We call this the “dual” module to M, and write M^*=\hom_{R-{\rm mod}}(M,R). Elements of the dual module are often called “linear functionals” on M.

Tensor products are even easier. When we consider R\otimes_RM for a left R-module M we can use the construction of tensor products to write an element as a finite sum: \sum r_i\otimes m_i. But then we can use the middle-linear property to write r_i\otimes m_i=(1\cdot r_i)\otimes m_i=1\otimes(r_i\cdot m_i), and then the linearity to collect all the terms together, giving 1\otimes m. The tensor product eats the module structure on M and the right module structure on R, leaving a left R-module structure. We calculate
r\cdot(1\otimes m)=(r\cdot1)\otimes m=r\cdot m=(1\cdot r)\otimes m=1\otimes(r\cdot m)
so R\otimes_RM\cong M as left R-modules.

Now let’s take two left R-modules M and N and make \hom(M,N). This is an abelian group — a \mathbb{Z}-module — as is M. Let’s write M as \hom(R,M) as above and then tensor over \mathbb{Z} with \hom(M,N). Then we can compose homomorphisms
\hom(M,N)\otimes M\cong\hom(M,N)\otimes\hom(R,M)\rightarrow\hom(R,N)\cong N
This is the “evaluation” homomorphism that takes an element m\in M and a homomorphism f\in\hom(M,N) and gives back f(m)\in N.

As a special case, we can take R itself in place of N. We get an evaluation homomorphism M^*\otimes M\rightarrow R. This “canonical pairing” we often write as \langle\mu,m\rangle=\mu(m) for a linear functional \mu and module element m.

What if we composed with an element of N^*=\hom(N,R) instead of M\cong\hom(R,M)? We use the evaluation homomorphism to get
N^*\otimes\hom(M,N)=\hom(N,R)\otimes\hom(M,N)\rightarrow\hom(M,R)=M^*
So given a homomorphism f:M\rightarrow N we get a homomorphism f^*:N^*\rightarrow M^*

Of course, all this goes through suitably changed by swapping “right” for “left”. For example, given a right R-module M we have a dual left R-module M^*=\hom_{{\rm mod}-R}(M,R).

What do we get if we start with a left module M, dualize it, then dualize again to get another left module M^{**}=\left(M^*\right)^*? Following the definitions we see M^{**}=\hom_{{\rm mod}-R}(\hom_{R-{\rm mod}}(M,R),R). I claim that there is a natural morphism of left R-modules M\rightarrow M^{**}. That is, a special element of
\hom_{R-{\rm mod}}(M,\hom_{{\rm mod}-R}(\hom_{R-{\rm mod}}(M,R),R)
but we know that this is isomorphic to
\hom_{R-{\rm mod}}(\hom_{R-{\rm mod}}(M,R)\otimes M,R)
which we write as
\hom_{R-{\rm mod}}(M^*\otimes M,R)
so we’re really looking for a special homomorphism from M^*\otimes M to R. And we’ve got one: the canonical pairing! So we take the canonical pairing as a homomorphism from M^*\otimes M\rightarrow R and pass it through this natural isomorphism to get a homomorphism d:M\rightarrow M^{**}. In case this looks completely insane, here it is in terms of elements: d(m) takes a linear functional \mu and gives back an element of the ring by the rule \left[d(m)\right](\mu)=\mu(m).

May 4, 2007 Posted by | Ring theory | 1 Comment

Greatest Lower Bounds and Euclid’s Algorithm

One interesting question for any partial order is that of lower or upper bounds. Given a partial order (P,\leq) and a subset S\subseteq P we say that b is a lower bound of S if b\leq s for every element s\in S. Similarly, an upper bound b is one so that s\leq b for every s.

A given subset S may have many different lower bounds. For example, if b is a lower bound for S and b'\leq b, then the transitive property of \leq shows that b' is also a lower bound. If we’re lucky, we can find a greatest lower bound. This is a lower bound d so that for any other lower bound b we have b\leq d. Then the set of all lower bounds is just the set of all elements below d.

As an explicit example, let’s consider the partial order we get from the divisibility relation on integers. In this case, a greatest lower bound is better known as a greatest common divisor, and for any pair of natural numbers we can find a greatest common divisor. The method we use actually goes all the way back to Euclid’s Elements, proposition VII.2. Because of this, it’s known as Euclid’s algorithm.

First we need remember how we divide numbers from back in arithmetic. Given two numbers a and b we can find numbers q and r with r<b and a=qb+r. We start with a and make up all the natural numbers of the form a-kb with k a natural number. Since the natural numbers are well-ordered, there is a least element a-qb in this set. Notice that here we use the regular order on \mathbb{N}, not divisibility. Anyhow, I claim that a-qb is less than b, so it will be our r. Indeed if it’s greater than b we can subtract b from it to get a-(q+1)b: a lower natural number, which contradicts the fact that a-qb is the lowest. Thus we have found a=qb+r with r<b. Notice that b|a if and only if r=0.

Okay, now that we remember how to divide we’re ready for Euclid’s algorithm. We start with numbers a and b and divide b into a to find a=q_1b+r_1. If r_1=0 then b|a and b is a common divisor. It’s clearly the greatest since any common divisor divides it.

If r_1\neq 0 then I say that any common divisor of b and r_1 is also a common divisor of a and b. We see that if r_1=k_1d and b=kd then a=q_1kd+k_1d=(q_1k+k_1)d so d|a as well. Thus if we can find the greatest common divisor of b and r_1 it will also be the greatest common divisor of a and b.

To do this, just keep going. Divide r_1 into b to get b=q_2r_1+r_2. If r_2=0 then we’re done, otherwise keep going again. At each step r_{i+1}<r_i, so we must eventually hit zero and stop. If we didn’t, then we could collect all the r_i together to have a set of natural numbers with no lowest element, contradicting the well-ordered property of \mathbb{N}. At the end we’ll have the greatest common divisor of a and b.

In fact, if we watch closely we can do even better. We stop when r_{n-1}=q_{n+1}r_n with a remainder of zero, getting the greatest common divisor d=r_n. Now we look at the next-to-last step r_{n-2}=q_nr_{n-1}+r_n. We can rewrite this as d=r_{n-2}-q_nr_{n-1}. Then the step before this — r_{n-3}=q_{n-1}r_{n-2}+r_{n-1} — can be written as r_{n-3}-q_{n-1}r_{n-2}=r_{n-1}. This gives us d=r_{n-2}-q_n(r_{n-3}-q_{n-1}r_{n-2})=-q_nr_{n-3}+(1+q_nq_{n-1})r_{n-2}. We can keep doing this over and over, at each step writing d as a linear combination of the two remainders that we started a given step with. Taking this all the way back to the beginning of the algorithm, we get d=ax+by for some integers x and y.

From here you should be able to see how to use Euclid’s algorithm to find the greatest common divisor of any finite set S of natural numbers, and further how to write it as an integral linear combination of the elements of S.

May 4, 2007 Posted by | Ring theory | 3 Comments