Linearization of Multiplication

Friday, April 26, 2013

So multiplication is generally not linearizable. However you can linearize binary multiplication. Let's assume x and y is two binary variables (either 0 or 1), we can linearize z = x*y as follow:

z <= x;
z <= y;
z >= x+y-1;
z >= 0;

Further more you can use this trick to multiply two variables x and y with value {-1,1}. Here is the trick is noticing if x and y is equal then multiplication z is 1 otherwise it is -1. Thus we can map variable x to {0,1} by (x+1)/2 or we can use binary variable to generate variables with value {-1,1} by 2*binary-1. After we get binary variable x' and y', we multiply them as above to get z'. And we may flip x' and y', to get x'' and y'' as x''=(1-x'); and we may multiply them as show above as well to get z''. If we add z' and z'', we get sum which is 1 if both values of x and y are same (1,1 or -1,-1) and 0 if they are different (-1,1 or 1,-1). We may map sum to correct result by final_result=(2*sum-1)formula. Bellow you may find a truth table:

 Truth Table x' y' z' x'' y'' z'' sum x y z 0 0 0 1 1 1 1 -1 -1 1 0 1 0 1 0 0 0 -1 1 -1 1 0 0 0 1 0 0 1 -1 -1 1 1 1 0 0 0 1 1 1 1