## And while I’m at it

Yaroslav Bulatov sent me the following nice question. Given vectors (a1,…,an) and (b1,…,bn) in Rn, is there an efficient algorithm to decide whether sgn(a1x1+…+anxn) equals sgn(b1x1+…+bnxn) 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.

### 9 Responses to “And while I’m at it”

1. Anonymous Says:

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

2. Kurt Says:

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.

3. Kurt Says:

This post has been removed by the author.

4. Anonymous Says:

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.

5. Anonymous Says:

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

–Troy

6. David Says:

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.

7. Anonymous Says:

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?)

8. Yaroslav Says:

Thanks Anonymous, I think your argument works

9. Scott Says:

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