5
$\begingroup$

Preface: To clear the theoretical background this question is cross-posted on math.stackexchange here.


I have a polynomial in $n$ variables of the form

$$P(x_1,x_2,\dots,x_n)=\left(\sum_{i,j}a_{ij}x_ix_j+\sum_{i}b_{i}x_i+c\right)^2$$

Is there some way to find a polynomial also in $n$ variables of degree at most 2

$$Q(y_1,y_2,\dots,y_n)=\sum_{i,j}d_{ij}y_iy_j+\sum_{i}e_{i}y_i+f$$

with the same roots and which is positive for all values in the domain? You may assume that all the variables only take on the values $0$ or $1$ and all coefficients are real.

At the moment my code is quite messy and FindInstance[] fails when there are a lot of variables.

getVariables[exp_]:=Union@Cases[exp,_Symbol,\[Infinity]]
generateConstraint[tuple_,f_,g_]:=Module[{val=f/.tuple},If[val==0,0==g/.tuple,0<g/.tuple]]

convertEqToQuadraticForm[eq_]:=Module[
    {f,g,nV,constraints,aVars,bVars,cVars,variables=Evaluate@getVariables@eq},
    nV=Length@variables;
    aVars=$a[1];
bVars=Array[$b,nV];
    cVars=Table[$c[a,b]//Sort,{a,nV},{b,nV}];
    f=eq;
    g=aVars+bVars.variables+variables.cVars.variables;
    constraints=generateConstraint[Thread[variables->#],f,g]&/@Tuples[{0,1},nV];
    Expand[g/.First@FindInstance[And@@constraints,Flatten@{aVars,bVars,cVars}]]
]

convertEqToQuadraticForm[(x y - z w - 1)^2]
(*1 + (w x)/2 - (w y)/2 - 2 x y + y^2 + 2 w z - y z + z^2*)

Is there a nicer way to do this?

$\endgroup$
  • $\begingroup$ Your first line can be replaced simply by Variables[exp]. $\endgroup$ – David G. Stork Jan 19 '15 at 23:14
  • $\begingroup$ I don't understand your example x y - z w - 1 because in the first sentence, you say that you have a polynomial of the form P=(...)^2 but your example is not of that form. Furthermore, if you have P=f*f doesn't that imply that f has the same roots as P and it is what you want? Except that it might miss the property of being positive. This all looks like it is a question for Mathematics. $\endgroup$ – halirutan Jan 20 '15 at 0:30
  • $\begingroup$ @halirutan sorry that was a typo. It was meant to be (xy-zw-1)^2. The positivity is the main challenge of the question. I have cross posted the question on the maths stackexchange. $\endgroup$ – E.O. Jan 20 '15 at 9:46
  • $\begingroup$ @E.O. That's better, because the guys over there should know the theoretical background of your problem. I have another question: You write we can assume that the variables only take 0 or 1 as value. Is it important that the polynomial is positive everywhere or is it enough when it is positive when the variables have 0/1 values? $\endgroup$ – halirutan Jan 20 '15 at 13:57
  • $\begingroup$ @halirutan sorry, I should have made that clear. It only needs to be positive when the variables have 0/1 values. $\endgroup$ – E.O. Jan 20 '15 at 14:15
2
$\begingroup$

One can go about this using an anzatz that each product of variables is replaced by a sum of corresponding new variables. Some GroebnerBasis rewriting and reduction by the result can then recover the desired form.

convertEqToQuadraticForm[form_, t_] := 
 Module[{vars = Variables[form], len, tvars, reps, allvars, gb},
  len = Length@vars;
  tvars = Array[t, len];
  reps = Table[
    vars[[i]]*vars[[j]] - (t[i] + t[j]), {i, len - 1}, {j, i, len}];
  allvars = Join[vars, tvars];
  gb = GroebnerBasis[reps, allvars];
  PolynomialReduce[form, gb, allvars][[2]]
  ]

Your example.

convertEqToQuadraticForm[(x y - z w - 1)^2, t]

(* Out[65]= 1 - 2 t[1] - 2 t[2] + 2 t[3] + t[3]^2 + 2 t[4] - 
 2 t[3] t[4] + t[4]^2 *)

This might need a specialized term order in general in order to force the new variables to minimal degrees. Also the above ansatz is a bit naive. Better might be, for each quadratic term in input e.g. term_k = c[k]*w[i]*w[j], to have a replacement of the form c[k]*(a[i,k]*y[i] + a[j,k]*y[j]).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.