Next: 4. Conclusions Up: Solving One-Sided Equations in Previous: 2. The Special Case

# 3. The General Case

Let , , and

be the system of equations we want to solve in . Let , be vectors in the right -module . Hence we can abbreviate the system of inhomogeneous equations by
 (4)

In order to describe the generating set of solutions we have to find one solution of the inhomogeneous system 4 and if possible a finite set of generators for the solutions of the homogeneous system
 (5)

We can proceed as described in the previous section. Of course now the prefix Gröbner bases are bases of submodules in the right -module , i.e., their elements are vectors in .
1. Let be a finite reduced prefix Gröbner basis of the right submodule generated by in , and , the corresponding vectors of course now in respectively . There are two linear mappings given by matrices , such that and .
2. Equation 4 is solvable if and only if which is again decidable using prefix reduction with respect to .
3. Let be a generating set for the solutions of the homogeneous system
 (6)

and let be the identity matrix. Further let be the columns of the matrix . Since these are solutions of the homogeneous system 5 as well. We can even show that the set generates all solutions of 5:
Let be an arbitrary solution of system 5, i.e.  . Then is a solution of system 6 as . Hence there are such that . Further we find

and hence is a right linear combination of elements in .
Now the important part is to find a generating set for the solutions of the homogeneous system 6. Let be a finite reduced prefix Gröbner basis of the right submodule generated by . Notice that for vectors the head term is defined to be the polynomial in the first non-zero component. We define where for and , . See Section 5 for details how to realize a reduction relation for the module case. Hence we get and . As before we have to distinguish two cases.
1. For every with such that is a prefix (as a word) of , i.e.  for some , by Lemma 8 we know for some . We determine vectors as follows:

where the polynomials are due to the reduction sequence .
Then , where

, is a solution of 6 as .
2. For let for some . Additionally, we define vectors for and as follows: Let . For every we know as is a prefix Gröbner basis. Then , where

, is a solution of system 6 as .

Lemma 3   The finitely many vectors , , form a right generating set for all solutions of system 6.

Proof : 1.1
Let be an arbitrary (non-trivial) solution of 6. We proceed by showing for all as follows: Let be the maximal term when concatenating the head terms of the multiples in the sum and the number of multiples with and . A solution is called smaller than if either or and . We will prove our claim by induction on and 4. Since we assume to be a non-trivial solution, we know . Then following the lines of the proof of Lemma 2 we can distinguish two cases:
1. If there is such that , then , , and for some , . Then with

, is again a solution of 6. It remains to show that it is a smaller one. To see this we have to examine the multiples for all where and :
1. For we get and as and the resulting monomials add up to zero we get 5.
2. For we get and either if or else
Hence either or is decreased.
2. Let us now assume there are such that and , with . Without loss of generality we can assume that for some . Then by Lemma 8 we know that for some . For the corresponding s-polynomial we have a vector and we can define where with

. It remains to show that this solution indeed is smaller. To do this we examine the multiples for all where and .
1. For we get and by Lemma 8 . Hence implying either if or else .
2. For we get . Since we find .
3. For we get . Hence either if or else.
Hence we find that either or in case , .

Next: 4. Conclusions Up: Solving One-Sided Equations in Previous: 2. The Special Case
| ZCA Home | Reports |