# To find the combinational coefficients of vectors in polynomials

Simply put, I have a few vectors of polynomials $$\{d_i\}$$ and I know one of their combinations gives $$x$$, which is also a vector of polynomials. How do I find the combinational coefficients $$a_i$$, namely, $$x=\sum_i a_id_i .$$

To be precise, the vectors of polynomials $$\{d_i\}$$ in question constitute the generating set of the kernel of a map $$\psi$$ (defined below), which is a (sub)module of the free module $$M$$ in polynomial ring $$R$$. Consider that they are known beforehand. Then for another element of the kernel, $$x$$, one needs to find the proper combinational coefficients.

I am not familiar with the ring theory either the module of syzygies. But I am doing some practical calculations which involve the first module of syzygies. For a given (multivariable) polynomial ring $$R$$, I understand that the first module of syzygies is related to the kernel of the following map (eg. consider the case with four generators) $$\psi: R^4\to R$$ $$c_1r_1+c_2r_2+c_3r_3+c_4r_4 \mapsto r$$ where $$r_1,\cdots,r_4$$ are four given elements of the polynomial ring, and the four coefficients $$c_i$$ are arbitrary coefficients, also polynomials. As discussed above, $$r_i$$ serve as the generators of an ideal, and by definition, the map constitutes a free module. Furthermore, the first module of syzygies is defined as the kernel of the above map, which is a submodule. My question is about how to find the expansion coefficients of an element $$x$$ belong to the kernel in terms of its generating set $$\{d_i\}$$. It seems to be a rather rudimental task but I have no idea how it might work. Many thanks in advance!

Below, I give explicitly what I need to solve and what I have tried. The generating set $$\{d_j\}$$ ($$j=1,\cdots,6$$) consists of six four-component vectors'' of polynomials in six variables $$D_i$$ and $$D_{i'}$$ ($$i'$$ is denoted by $$Pi$$ below) with $$i=1,2,3$$.

d1 = {(1 - Subscript[D, 1] Subscript[D, P1]), 0,   0, -(1 - Subscript[D, 1] Subscript[D, 2] Subscript[D, 3])};
d2 = {Subscript[D, 3] - Subscript[D, P1] Subscript[D, P2], -(Subscript[D, P1] - Subscript[D, 3] Subscript[D, 2]),    0, -Subscript[D, 3] (1 - Subscript[D, P2] Subscript[D, 2])};
d3 = {Subscript[D, 1] - Subscript[D, P3] Subscript[D, P2], -(Subscript[D, P3] - Subscript[D, 1] Subscript[D, 2]), -(1 - Subscript[D, P2] Subscript[D, 2]), 0};
d4 = {Subscript[D, 1] (Subscript[D, P3] Subscript[D, 3] - 1), 0, -(Subscript[D, 1] Subscript[D, 2] Subscript[D, 3] - 1), 0};
d5 = {0, -(Subscript[D, P1] Subscript[D, 1] - 1), 0, -(Subscript[D, 3] Subscript[D, 1] - Subscript[D, P2])};
d6 = {(1 - Subscript[D, P3] Subscript[D, 3]), 0, -(Subscript[D, P1] - Subscript[D, 2] Subscript[D, 3]), -(1 - Subscript[D, P3] Subscript[D, 3])};


Now I need to find the combinational coefficients $$a_i$$ so that $$x=\sum_{i=1}^6 a_i d_i ,$$ where

x = {Subscript[D, 2] Subscript[D, P3] Subscript[D, P3] - Subscript[D, 2] Subscript[D, P3] Subscript[D, P3] Subscript[D, P1] Subscript[D, 1] - Subscript[D, 2] Subscript[D, 1] Subscript[D, P1] Subscript[D, P3] Subscript[D, P3] + Subscript[D, 2] Subscript[D, 1] Subscript[D, P1] Subscript[D, P3] Subscript[D, P3] Subscript[D, P1] Subscript[D, 1], 0, -(Subscript[D, P3] Subscript[D, 2] Subscript[D, 2] - Subscript[D, P3] Subscript[D, 2] Subscript[D, 2] Subscript[D, 1] Subscript[D, P1] - Subscript[D, P3] Subscript[D, P1] Subscript[D, 1] Subscript[D, 2] Subscript[D, 2] + Subscript[D, P3] Subscript[D, P1] Subscript[D, 1] Subscript[D, 2] Subscript[D, 2] Subscript[D, 1] Subscript[D,       P1]), -(Subscript[D, 2] Subscript[D, P3] Subscript[D, P3] - Subscript[D, 2] Subscript[D, P1] Subscript[D, 1] Subscript[D, P3] Subscript[D, P3] -    Subscript[D, P3] Subscript[D, 2] Subscript[D, 2] Subscript[D, 1] + Subscript[D, P3] Subscript[D, P1] Subscript[D, 1]Subscript[D, 2] Subscript[D, 2] Subscript[D, 1])};


One may solve the above problem straightforwardly. But as explained above, the problem is closely associated with the one regarding the first module of syzygies, and I am not sure a general solution is related. Therefore I also present them here. Consider an ideal generated by following four polynomials

r1 = (-1 + Subscript[D, 1] Subscript[D, 2] Subscript[D, 3]);
r2 = (-1 + Subscript[D, 1] Subscript[D, P1]);
r3 = (-Subscript[D, 1] Subscript[D, 3] + Subscript[D, P2]);
r4 = (-Subscript[D, 1] + Subscript[D, 1] Subscript[D, 3] Subscript[D, P3]);


When linearly combined with four arbitrary polynomial coefficients $$c_i$$, the resultant expression $$\sum c_ir_i$$ is also a polynomial, which corresponds to a map $$R^4\to R .$$ Now, the kernel of the above map can be derived through the Grobner basis $$G=\{g_i\}$$ of these polynomials, which can be obtained (without awareness of the details) by the Mathematica command GroebnerBasis[].

GroebnerBasis[{(-1 + Subscript[D, 1] Subscript[D, 2] Subscript[D, 3]), (-1 + Subscript[D, 1] Subscript[D, P1]), (-Subscript[D, 1] Subscript[D, 3] + Subscript[D, P2]), (-Subscript[D, 1] + Subscript[D, 1] Subscript[D, 3] Subscript[D, P3])}, {Subscript[D, 1], Subscript[D, 2], Subscript[D, 3], Subscript[D, P1], Subscript[D, P2], Subscript[D, P3]}]


To obtain the coefficients $$a_i$$, I tried the command PolynomialReduce[] to expand the $$x$$ in both $$D_i$$ ($$D_{i'}$$) and individual vector component (assigned by artificial variable $$A_i$$), as follows

DSixBases = {d1[[1]] A1 + d1[[2]] A2 + d1[[3]] A3 + d1[[4]] A4, d2[[1]] A1 + d2[[2]] A2 + d2[[3]] A3 + d2[[4]] A4, d3[[1]] A1 + d3[[2]] A2 + d3[[3]] A3 + d3[[4]] A4, d4[[1]] A1 + d4[[2]] A2 + d4[[3]] A3 + d4[[4]] A4, d5[[1]] A1 + d5[[2]] A2 + d5[[3]] A3 + d5[[4]] A4, d6[[1]] A1 + d6[[2]] A2 + d6[[3]] A3 + d6[[4]] A4}
PolynomialReduce[x[[1]] A1 + x[[2]] A2 + x[[3]] A3 + x[[4]] A4, DSixBases, {Subscript[D, 1], Subscript[D, 2], Subscript[D, 3], Subscript[D, P1], Subscript[D, P2], Subscript[D, P3], A1, A2, A3, A4}]


However, it does not seem to work.

• For the "But instead, I need ...." part near the end of your post, can you give an example input and desired output? May 27, 2021 at 8:42
• The question is quite clear and well written by the way, nice job. May 27, 2021 at 8:43
• Thanks for the comments, I will update the question. @MariusLadegårdMeyer May 27, 2021 at 8:58
• This is an interesting question. Please edit so I can fix my downvote (meant to upvote and apparently hit wrong arrow, noticed too late to fix). May 27, 2021 at 16:12

This can be done using Groebner bases but it involves either a bit of undocumented functionality or some digging through past posts to code a module GB.

First I set up the inputs, and use new variables to convert vectors to an equivalent form. The idea is to create a module basis, where each column corresponds to a new variable.

polymat = {{(1 - dD[1] dD[p1]), 0, 0, -(1 - dD[1] dD[2] dD[3])},
{dD[3] - dD[p1] dD[p2], -(dD[p1] - dD[3] dD[2]),
0, -dD[3] (1 - dD[p2] dD[2])},
{dD[1] -
dD[p3] dD[p2], -(dD[p3] - dD[1] dD[2]), -(1 - dD[p2] dD[2]), 0},
{dD[1] (dD[p3] dD[3] - 1), 0, -(dD[1] dD[2] dD[3] - 1), 0},
{0, -(dD[p1] dD[1] - 1), 0, -(dD[3] dD[1] - dD[p2])},
{(1 - dD[p3] dD[3]),
0, -(dD[p1] - dD[2] dD[3]), -(1 - dD[p3] dD[3])}};
wvars = Array[w, Length[polymat[[1]]]];
newpolys = polymat . wvars;

xvec = {dD[2] dD[p3] dD[p3] - dD[2] dD[p3] dD[p3] dD[p1] dD[1] -
dD[2] dD[1] dD[p1] dD[p3] dD[p3] +
dD[2] dD[1] dD[p1] dD[p3] dD[p3] dD[p1] dD[1],
0, -(dD[p3] dD[2] dD[2] - dD[p3] dD[2] dD[2] dD[1] dD[p1] -
dD[p3] dD[p1] dD[1] dD[2] dD[2] +
dD[p3] dD[p1] dD[1] dD[2] dD[2] dD[1] dD[p1]), -(dD[2] dD[
p3] dD[p3] - dD[2] dD[p1] dD[1] dD[p3] dD[p3] -
dD[p3] dD[2] dD[2] dD[1] +
dD[p3] dD[p1] dD[1] dD[2] dD[2] dD[1])};
targetpoly = xvec . wvars;


Now we compute a Groebner basis for this. To force it to effectively preserve module structure, we do not allow multiplication of the module variables. This can be done using the undocumented DegreeBound->{dvec,dval} option as below. It works by taking dot product of the vector part dvec with the exponent vector of a given monomial, and enforcing that this be no greater than dval.

Another wrinkle is that we will want the (not uniquely defined) conversion matrix that takes input polynomials to GB. For this there is a resource function ExtendedGroebnerBasis.

vars = Variables[{polymat, xvec}];
{gb, cmat} =
ResourceFunction["ExtendedGroebnerBasis"][newpolys,
Join[wvars, vars],
DegreeBound -> {Join[ConstantArray[1, Length[wvars]],
ConstantArray[0, Length[vars]]], 1}];


Check that we do get the desired conversion.

In[278]:= cmat . newpolys - gb // Expand

(* Out[278]= {0, 0, 0, 0, 0, 0} *)


Now we use PolynomialReduce to get a rewrite of the target in terms of the GB elements.

{mults, red} =
PolynomialReduce[targetpoly, gb, Join[wvars, vars]]

(* Out[275]= {{dD[2]^2 dD[p3] - dD[1] dD[2]^2 dD[p1] dD[p3], 0,
dD[2]^2 dD[p3]^2 - dD[1] dD[2]^2 dD[p1] dD[p3]^2, -dD[2] dD[p3]^2 +
dD[1] dD[2] dD[p1] dD[p3]^2,
0, -dD[2] dD[p1] dD[p3]^2 + dD[1] dD[2] dD[p1]^2 dD[p3]^2}, 0} *)


We see that this was a full rewrite, meaning no remainder (second value is zero). But we will check explicitly that the rewrite equation works.

In[279]:= mults . gb - targetpoly // Expand

(* Out[279]= 0 *)


We can put all this together to get the polynomial coefficients needed to represent the target in terms of the original vectors.

coeffs = Expand[mults . cmat]

(* Out[292]= {dD[2]^2 dD[p2] dD[p3]^2 -
dD[1] dD[2]^2 dD[p1] dD[p2] dD[p3]^2, -dD[1] dD[2]^2 dD[p3]^2 +
dD[1]^2 dD[2]^2 dD[p1] dD[p3]^2 + dD[2] dD[p3]^3 -
dD[1] dD[2] dD[p1] dD[p3]^3,
dD[2]^2 dD[3] dD[p3]^2 - dD[2] dD[p1] dD[p3]^2 -
dD[1] dD[2]^2 dD[3] dD[p1] dD[p3]^2 +
dD[1] dD[2] dD[p1]^2 dD[p3]^2, -dD[2]^2 dD[p3] +
dD[1] dD[2]^2 dD[p1] dD[p3], 0, -dD[1] dD[2]^2 dD[p3] +
dD[1]^2 dD[2]^2 dD[p1] dD[p3] + dD[2] dD[p3]^2 -
dD[1] dD[2] dD[p1] dD[p3]^2 - dD[2]^2 dD[p2] dD[p3]^2 +
dD[1] dD[2]^2 dD[p1] dD[p2] dD[p3]^2} *)


These are the a1,...,a6 that were sought.

• Thanks a lot for the answer! So if I understood correctly, one first finds the module Grobnber basis, which is given in terms of the linear combinations of the d_i, and then reduces the target polynomial in terms of the obtained basis, and therefore the resultant matrix product of expansion coefficients gives the desired expansion coefficients. Also, I took the liberty to fix a minor typo and removed a few blanks. May 28, 2021 at 7:02
• That seems about right. Thanks for catching the d-->a error. May 28, 2021 at 14:57