3. The General Case

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

In order to describe the generating set of solutions we have to find

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 .

- 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 .
- Equation 4 is solvable if and only if which is again decidable using prefix reduction with respect to .
- Let
be a generating set for the solutions of the
homogeneous system

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 .

- 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 . - 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 .

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

- 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 :- For we get
and as
and the resulting monomials
add up to zero we get
^{5}. - For we get and either if or else

- For we get
and as
and the resulting monomials
add up to zero we get
- 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 .- For we get and by Lemma 8 . Hence implying either if or else .
- For we get . Since we find .
- For we get . Hence either if or else.