# Attempt to reduce to problem of inner product

The problem of Orthogonality: gives $$n$$ vectors of dimension $$k$$ and another set of same, can a pair be found with inner product = $$0$$?

The problem of max product: likewise two sets each $$n$$ vectors (I forgot to mention in both cases values are binary). We want to find maximal inner product (one vector from set $$A$$ and one from $$B$$).

I want to find a reduction between OV to max. Inner product.

My idea: Use negative values, claim its equivalent with negative value and possitive values.

What I mean, OV reduced to max. Inner prod with negative values by multiplying all by $$-1$$.

Then if maximum is zero... Orthogonality. Else, no orthogonality.

But i need to argue negative max inner product equivalent to max. Inner product.

Maybe there is another way?

If it does not work, also interested in reduction from sat.

• What kind of reduction are you looking for? Many to one reductions? Turing reductions? Jan 9 at 23:54
• Turing reduction will be good, and if possible, many to one. But even turing will assiste me. Jan 9 at 23:56

One possibility is to take the tensor squares of the vector: replace each vector $$x$$ with a new vector $$\hat{x}$$ given by $$\hat{x}_{ij} = x_i x_j$$ (the vectors have length $$k^2)$$. We have $$\langle \hat{x}, \hat{y} \rangle = \sum_{ij} x_i x_j y_i y_j = \langle x,y \rangle^2.$$ Therefore if you know the minimum inner product, you can solve OV. It remains to negate all vectors in one of the sets.
• This is interesting. But for minimum inner product, there is no need for that simply leave the vectors as they are and then if minimal ip is 0 they are orthogonal and else they are not. My problem begins when i try reducing to maximum inner product i thought they are equivalent easily, but it required more than just multiplying by $-1$ (if simply multiply by $-1$, we get also positive values when multiplied, also to note). Jan 10 at 7:12
• Use $\langle \hat x, - \hat y \rangle = -\langle x,y \rangle^2$. Jan 10 at 7:18