Orthogonal Vectors [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 12 years ago.

Given a vector V of size N, Find if there exists another vector A (of size N) such that A.V = 开发者_Go百科0 where . represents the Dot product or Inner Product ie a1*v1 + a2*v2 + a3 * v3 + ... an*vn = 0, and A >0 ie all ai are non-negative integers and all ais cannot be 0 at the same time(trivial case). Suggest an algorithm to generate a YES of NO.

---

Consider first the case when at least one of v_i = 0. Then it is easy for you to show that the answer is YES. Now move on to the cases where all the v_i ≠ 0. Now break this into two more subcases.

1. All the v_i have the same sign.
2. At least one pair, say v_i and v_j, i ≠ j , have different signs.

You should be able to complete the assignment from this breakdown.

---

I'm going to jump out on a limb here based on some intuition. Try the set of vectors A where a1..an are 0 or 1. So for size N you will have 2**N vectors in this set. Take the dot product V.A for each of these. If there are at least one positive and at least one negative dot product, then there exists one vector in that quadrant/octant/X-ant where the dot product is zero, otherwise not.

The dot product will interpolate as you interpolate between vectors, so if there is a positive one and a negative one, then some linear combination of those will have a dot product that is zero.

The intuition part is that this test is sufficient - i.e. the "otherwise not" part.

Edit: This ends up being equivalent to "if there is at least one positive component of V AND one negative component, then yes. Otherwise no."