## And while I’m at it

Yaroslav Bulatov sent me the following nice question. Given vectors (a_{1},…,a_{n}) and (b_{1},…,b_{n}) in R^{n}, is there an efficient algorithm to decide whether sgn(a_{1}x_{1}+…+a_{n}x_{n}) equals sgn(b_{1}x_{1}+…+b_{n}x_{n}) for all x in {0,1}^{n}? I could think about it myself, but wouldn’t it be more fun to call upon the collective expertise of my readers? After all, this is a Serious Blog now. I await the observation that’s eluded me for the past five minutes.

Comment #1 April 21st, 2006 at 9:53 am

Doesn’t this mean that the vectors are

linearly dependent, related by a positive

coefficient?

Assume that a’,b’ have this property.

Normalize these to unit vectors a,b which

will still clearly have the property.

Now

sgn(a dot (a-b))=sgn(b dot (a-b)).

Notice that if sgn(x)=sgn(y) then also

sgn(x+y)=sgn(x)=sgn(y). Applying this to

the above with x=a dot a – a dot b

and y=b dot a – b dot b we have

sgn(a dot a – a dot b)=0 and so

a dot b=1 and a=b. Thus the two

original vectors are linearly independent,

related by a positive coefficient.

–Troy

Comment #2 April 21st, 2006 at 10:03 am

Scott, how are those vectors being specified? Are they actually in Q^n and not R^n? I ask that because, if you think like Andrej Bauer, sgn(x) for x ∈ R is not even computable.

Comment #3 April 21st, 2006 at 10:17 am

This post has been removed by the author.

Comment #4 April 21st, 2006 at 10:21 am

Troy-

Why does sgn(a dot (a-b)) have to equal

sgn(b dot (a-b))? The equality was only

specified for vectors in {0,1}^n

which a-b might not be.

Comment #5 April 21st, 2006 at 10:25 am

oh, I didn’t see the {0,1}^n. oops, ok, more interesting now.

–Troy

Comment #6 April 21st, 2006 at 10:53 am

Yes there is. Check every pair (sgn(Ai), sgn(Bi) ) and if any are different, you can construct X s.t. it is 1 for Xi and 0 for all others.

I’ll prove this is exhaustive later.

Comment #7 April 21st, 2006 at 1:19 pm

David: a=(3,-2), b=(1,-2), x=(1,1)?

There’s a reduction from subset sum. Let S=(s1, …, sn) be an instance of subset sum (integer entries, we’re looking for a subset that sums to 0). Define a and b so that:

ai = si + 1/3n

bi = si – 1/3n

for every i. Then the absolute difference between a sum from a and a sum from b is always less than one, and the signs of the sums differ if and only if the corresponding sum of entries from S sums to 0. So the problem is NP-complete.

(Any errors in this?)

Comment #8 April 21st, 2006 at 3:33 pm

Thanks Anonymous, I think your argument works

Comment #9 April 21st, 2006 at 6:06 pm

Thanks, anonymous. I figured there was probably a reduction from Subset Sum, but I suck at reductions.