linear dependence of polynomials + the function "eliminate"

rambiz · Tue May 31, 2016 6:58 pm

Hi all,
It is known that in the case of a zero-dimensional ideal, if we reduce successive powers of a variable, say
1,x,x^2,x^3, etc, until the remainders become linearly dependent, we can get a polynomial in x alone by using the same respective coefficients, which made the remainders linearly dependent.

simple illustrative example:

>ring r=0,(x,y),dp;
>ideal i=x3+y2-2,x+y;
>ideal g=std(i);
>g;
g[1]=x+y
g[2]=y3-y2+2
>poly r1=reduce(1,g);r1;
1
>poly rx=reduce(x,g);rx;
-y
>poly rx2=reduce(x2,g);rx2;
y2
>poly rx3=reduce(x3,g);rx3;
-y2+2

At this point, it can easily be seen that 1*rx3+1*rx2-2*rx1=0 and taking the same coefficients we get: 1*x3+1*x2-2*1=0 and so we have an equation in x alone (which is easily verified in this case).

-Now my question is, if this procedure has already been implemented in Singular?
-If not do you have any tips how to efficiently check for linear dependency of polynomials and access the coefficients, that make them linearly dependent?
I know that calculating a reduced Groebner basis with respect to lex order does the same, but it is sometimes not really efficient. The function eliminate does provide the same results too, and not only for zero-dimensional ideals. How exactly does eliminate work? Which algorithm is used? Does it calculates the intersection of an ideal with k[X(k+1), X(k+2), ...,X(n)] to eliminate the first k variables? If it does calculate the intersection, which exact algorithm is used? In general, I think that a few words about the algorithms in use in the inbuilt functions of Singular would be very helpful. Unfortunately, most of the time, the online manual doesn't contain information about the algorithms used!

Re: linear dependence of multivariate polynomials

rambiz · Sat Jun 11, 2016 5:15 pm

Hi all,
this is the code I could come up with. Please have a look, proof-read, and make possibly improvement suggestions.

Code:

LIB "matrix.lib";

ring r=0,(x,y),lp;

ideal i=x4+x2+xy3+2,x2+y2-1;

ideal g=std(i);
//option(redSB);
g;
dim(g);
vdim(g);

ideal B=kbase(g);
int   L=size(B);


matrix m[L][1];
matrix column[L][1];

int n=0;          //power of the ring variable for which we want to calculate the elimination ideal
int flag=1;       //flag is set to zero, when the reduced powers become linearly dependent
while(flag==1)
{
 
 poly f=reduce(x^n,g);
 
 for(int counter=1;counter<=L;counter=counter+1)
 {
  column[counter,1]=jet(f/B[counter],0);
 }

 if (n==0)
    {m=column;}
 else
     {m=concat(m,column);}
 
 if (rank(m)<(n+1))
      {flag=0;} 
 
 n=n+1;

}

print(m);

///////////////////////////////////////////////////
option(noredefine);

int nc=ncols(m);
 
ring r2=0,(x(1..nc)),lp;    //number of variables must be the same as the number of columns of the matrix for which we want the reduced row echelon form

map f=r,x(1),x(2);
matrix m2=f(m);


print("m2=");print(m2);

int nr=nrows(m2);
int nc=ncols(m2);
int j;
int k;
for(j=1;j<=nr;j=j+1){for(k=1;k<=nc;k=k+1){m2[j,k]=m2[j,k]*x(k);}};
kill j;
kill k;
//print(m2);

matrix ONES[nc][1];
for(int j=1;j<=nc;j=j+1){ONES[j,1]=1;};
kill j;

ideal i=m2*ONES;
option(redSB);
ideal g=std(i);
option(redSB);
int L=size(g);
for(int j=1;j<=L;j=j+1) {g[j]=g[j]/leadcoef(g[j]);}
kill j;

matrix Output[L][nc];

int k;
for (int j=L;j>0;j=j-1){for (k=1;k<=nc;k=k+1){Output[j,k]=jet(g[L+1-j]/x(k),0);}};
kill j;
kill k;


print("Output=");print(Output);print("Output is the reduced row echelon form of matrix m");

setring r;

map phi=r2,x;
matrix rref=phi(Output);

print(rref);

poly EliminationIdeal=x^(nc-1);

for (int n=1;n<=(nc-1);n=n+1)
    {EliminationIdeal=EliminationIdeal+(-rref[n,nc])*x^(n-1);};
print(EliminationIdeal);


//ring r=0,(x,y),dp; ideal i=x3-yx+1,x2+y2-1;---->x6+x4+2x3-x2+1
//ring r=0,(x,y),dp; ideal i=x3-y2+xy,x+y-1; ---->x3-2x2+3x-1
//ring r=0,(x,y),lp; ideal i=x4+x2+xy3+2,x2+y2-1;---->x8-1/2x6+4x4+3/2x2+2

The last 3 lines are examples with the corresponding elimination ideal. I checked the answers manually and these solutions are right.