Re: two questions on R-modules

suppose you have a free module M over a commutative
ring R.

1. given two submodules M1 and M2, and their bases,
B1 and B2, is there any algorithm/method known to
compute a basis for the intersection M1\cap M2?

It is not true that submodules of free modules are
free.

I think here assuming a suitable hypothesis so that it
is true is the key to getting such an algorithm.

I think it is roughly the case that there is a general
algorithm for R if and only if R-submodules of free
R-modules are free.

As usual to decide whether there is an algorithm requires
specifying how the modules (and how bases) are represented.
Assuming the elements of the ring are easily worked with,
that the free module is represented by n-tuples of ring
elements, the submodules are finitely generated, and
represented by generators, (so I think we are now over
a computable PID), then I believe it is just a small
change from the vector space version. You need to
use Bezout's theorem (or your PID oracle) a few times
when otherwise you would divide by a non-unit had you
been working in the field of fractions instead.

I would check Cohen's computational number theory (vol
1 or 2).

2. is there any general algorithm/method to compute
a basis for M/M1?

Neither is true that such a quotient is free.

Here I have to agree that a hypothesis such that every
quotient of a free module is free is a bit silly. Such
commutative rings are just called fields, and I'll assume
you can handle the vector space case.

Going back to the previous hypothesis though, there is
still sort of a "basis" of a finitely generated module
over a PID, and you can use the "Smith normal form"
of the injection from the free module M1 into M to find
the basis of the cokernel, M/M1. This is definitely in
Cohen, and I think actually in quite a few algebra texts.
.

Relevant Pages

  • Re: An algorithm problem
    ... what we exapct from the algorithm is a list of 0 or 1, ... We can take it as a ring, and fetch any continuous 2 numbers from it, finally get four combinations: ... for i in temp: ... global flag ...
    (comp.lang.python)
  • Re: Ideals, Integral domain question
    ... >> There are rings for which the independent basis ... Composition of homomorphisms between these vectors spaces ... Let R be a ring, and let m,n be positive integers. ... letting R denote the ring Endor left A-module endomorphisms of M, ...
    (sci.math)
  • Re: Discovering a great new British City; MIDDLETON
    ... consists of the ring of the cities of Rotterdam, The Hague, Amsterdam ... but putting that framework on it means ... They plan on the basis of the towns being laid out in this form. ...
    (uk.railway)
  • Re: Implementing FOV for hexagonal dungeons
    ... A simple though inefficient algorithm is to do 'rings' of hexes ... spiralling out from a centre point (first ring has 6 hexes, ... Calculate the extreme angles of the corners of each hex ... I used a similar algorithm in my game Lair; ...
    (rec.games.roguelike.development)
  • Re: example of module...
    ... I know an example with the ring being Z x Z (where Z is the ring of ... First is a basis, so all other bases will have dimension 1 by ... is a linear combination equal to 0 with nonzero coefficients; ...
    (sci.math)