[GAP Forum] element in ideal (more specific)
Alexander Hulpke
ahulpke at gmail.com
Fri Aug 22 22:10:11 BST 2008
Dear Forum,
b-eide (no real name given) asked:
>> I was asked to be more specific about my "element in ideal"
>> question: >This is what I am trying to do:
>
>> I have a matrix group with 3 generators (3 by 3 matrices), G.
>> Then R is the Group Ring over the integers,
>> R:=GroupRing(Integers,G);
>> Then I have
>> emb:=Embedding(G,R);
>> so that I could create 4 elements in R such as,
>> R3:=A^emb+B^emb+C^emb;
>> b;
>> where A, B, and C are 3 by 3 matrices.
>> Next, I created a right ideal, I, by generators(R3,R13,R6,R10) in R,
>> I:=RightIdealByGenerators(R,R3,R13,R6,R10);
Presumably
RightIdealByGenerators(R,[R3,R13,R6,R10]);
>>
>> Finally I have 3 more elements in R which look similar to R3 and
>> I'd like to
> determine if they are in the ideal I.
>> I tried "in":
>> R7 in I;
>> and I got the error
>> Error, no method found! For debuggin hints type ?Recovery from
>> NoMethodFound.
>> Error, no 1st choice method found for 'Basis' on 1 arguments called
>> from
> NiceBasis(B) called from BasisVectors(MB!.immutableBasis ) called
> from BasisVectors(MB)
> called from NrBasisVectors(MB) called from...
>
> If GAP cannot do this, does anyone know a software package that will?
Let me describe what GAP does, and where it fails. From this it should
be clear how one can test "by hand" whether an element is an ideal (Or
what is needed to add functionality to make the `in' command working).
GAP translates the problem into a linear algebra problem. It chooses
a basis (presumably just the images of the group elements) for the
algebra R. With respect to this basis every subring is simply a
subspace of row vectors. To find a linear spanning set for the ideal
R3, it essentially uses what is called the spinning algorithm for
submodules. We assume that we have a subspace T, which is initialized
to be the space spanned by the ideal generators. We now iteratively
expand T.
We form the products of all (linear) generators of T with all (linear)
generators of R. If the product does not lie in T, we extend T with
this product as new linear generator.
The process ends, once all products are found to lie in T.
At this point T will be the ideal R3, and we have a basis for it.
Testing from membership in the ideal now is simply testing for
membership in the subspace T.
The problem arises, because you form the group ring over the
integers. (So de facto we do not have subspaces, but only submodules.)
The membership test in such a submodule is not just Gaussian
elimination, but requires an Hermite normal form. This is where GAP
trips up. (Actually it even trips up a moment earlier when trying to
find a basis, because methods for basis are only implemented over
fields.)
Adding all this functionality to the system is a little bit tricky,
because it would involve extending most of the vector space
functionality to Z- modules. Still all the underlying machinery is
available in the system. So what you could do is to construct the Z-
submodule T yourself, doing membership tests using mobile forms.
What you also could do is to replace Integers by Rationals your
definition of R. As long as your elements are simple sums of group
elements, membership in the ideal should be the same regardless over
which scalar ring you are working.
There is of course one further difficulty. The vector space (module)
over which we are working has dimension |G|. Once this goes beyond a
few 10,000 you will likely run into memory problems. I do not have a
good idea how to avoid this in general.
You could however replace R with an image under any representation of
G. The image would be a smaller dimensional vector space, and you
could test membership in this image first.
A single image will give you only a necessary condition. If you use
all irreducible representations of G (assuming we are working
characteristic zero), I would think that one can use Wedderburn's
structure theorem to patch a result together.
All the best,
Alexander Hulpke
-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke at math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke
More information about the Forum
mailing list