8
$\begingroup$

I was given this riddle by one of my professors, and was wondering if anyone could give some hints on this problem. Say I have 100 vectors, $x_1, x_2, ... x_{100}$. I compute every dot product pair, excluding self-pairs, so a vector is not dotted with itself, i.e $x_1 \cdot x_2$, $x_1 \cdot x_3$, ... $x_1 \cdot x_{100}$, $x_2 \cdot x_3$, $x_2 \cdot x_4$, ... $x_2 \cdot x_{100}$ ... $x_{99} \cdot x_{100}$, and tabulate the result in a list $L_1$. I then create another list $L_2 = -L_1$, $L_2$ is just $L_1$ with the signs flipped. If I only gave you the two lists, could you tell which one is $L_1$ and which one is $L_2$, i.e which list is the true dot product pairs, and which list had it's sign flipped?

$\endgroup$
  • $\begingroup$ With two vectors this is clearly not possible. What about three or four? Try those, and see if you can't spot some pattern to use. $\endgroup$ – Arthur Jan 22 at 6:50
  • 2
    $\begingroup$ Is there any other information related to the vectors? Do you know anything about their values, dimension etc? $\endgroup$ – Matti P. Jan 22 at 6:51
  • $\begingroup$ No information is given about the vectors other than the fact they are all in the same dimension $\endgroup$ – Shovik Guha Jan 22 at 6:57
  • 2
    $\begingroup$ Obviously, if they are all orthogonal to each other, one couldn't tell. $\endgroup$ – Zeekless Jan 22 at 7:09
  • 1
    $\begingroup$ Zeekless: Of course, I was very vague in my comment. (Because I didn't think too much about the problem), but I only claimed "many" not "most". For example, in $\mathbb{R}$, if you select $k \geq 2$ (with $k$ even) vectors, there must be at least $\frac{1}{2}( k^2/2 - k)$ positive products. (So you example is actually worst case scenario). There are $k^2/2 - k/2$ total distinct products, so, asymptotically, roughly half must be positive. $\endgroup$ – Jason DeVito Jan 23 at 22:04
7
$\begingroup$

Consider a set of vectors $x_k\in \mathbb{R}^{100}:$

$$ \Big\{ x_1 = \begin{bmatrix} 1 \\ 0 \\ 0 \\ \vdots \\ 0 \\0 \end{bmatrix}, \; x_2 = \begin{bmatrix} 1 \\ 1 \\ 0 \\ \vdots \\ 0 \\0\end{bmatrix}\; x_3 = \begin{bmatrix} 1 \\ 1 \\ 1 \\ \vdots \\ 0\\0 \end{bmatrix}, \; \dots,\; x_{99} = \begin{bmatrix} 1 \\ 1 \\ 1 \\ \vdots\\1 \\ 0\end{bmatrix},\;x_{100} = \begin{bmatrix} 1 \\ 1 \\ 1 \\ \vdots \\ 1\\1\end{bmatrix}\Big\} $$

Then $L_1=\big\{(1)_{\times 99},(2)_{\times 98},\dots,(99)_{\times 1}\big\}, \; L_2=\big\{(-1)_{\times 99},(-2)_{\times 98},\dots,(-99)_{\times 1}\big\}$.

Now consider a set of vectors $x_k\in \mathbb{R}^{100}:$

$$ \Big\{ x_1 = \begin{bmatrix} -1 \\ 0 \\ 0 \\ \vdots \\ 0 \\0 \end{bmatrix}, \; x_2 = \begin{bmatrix} 1 \\ -3 \\ 0 \\ \vdots \\ 0 \\0\end{bmatrix}\; x_3 = \begin{bmatrix} 1 \\ 1 \\ -5 \\ \vdots \\ 0\\0 \end{bmatrix}, \; \dots,\; x_{99} = \begin{bmatrix} 1 \\ 1 \\ 1 \\ \vdots\\-197 \\ 0\end{bmatrix},\;x_{100} = \begin{bmatrix} 1 \\ 1 \\ 1 \\ \vdots \\ 1\\1\end{bmatrix}\Big\} $$

Then $L_1=\big\{(-1)_{\times 99},(-2)_{\times 98},\dots,(-99)_{\times 1}\big\},\; L_2=\big\{(1)_{\times 99},(2)_{\times 98},\dots,(99)_{\times 1}\big\}$.

$\endgroup$
  • $\begingroup$ This is clever, but I'm not quite sure how this answers the question. In the question, we are only given the 2 lists, $L_1$ and $L_2$, and from there we have to derive which list is flipped and which is the true dot products. We don't get to choose the set of vectors. $\endgroup$ – Shovik Guha Jan 22 at 16:26
  • $\begingroup$ @Shovik Guha If you get two lists: $\big\{(-1)_{\times 99},(-2)_{\times 98},\dots,(-99)_{\times 1}\big\}$ and $\big\{(1)_{\times 99},(2)_{\times 98},\dots,(99)_{\times 1}\big\}$ you won't be able to decide which one is true and which one is inverted. Each one of these lists is the true one - either for the first or the second set of vectors. This works as a counterexample and thus answers the question: "could you tell which one is which?". The answer is: "No, for this pair of lists, I can't. Both could be $L_1$ and both could be $L_2$ depending on the initial set of vectors". $\endgroup$ – Zeekless Jan 22 at 17:18
  • 1
    $\begingroup$ Ah, I see what you are saying now! $\endgroup$ – Shovik Guha Jan 22 at 17:50
3
$\begingroup$

First, let's consider all the possible answers this question could have:

  1. It it always possible t otell which list is which
  2. It is always impossible to tell which list is which
  3. It is sometimes possible and sometimes impossible to tell, depending on the list.

Since both the dimension and amount of vectors can be arbitrary, we can consider 3 1-dimensional vectors resulting in lists [1,1,1] and [-1,-1,-1]. It is clear that [1,1,1] is the correct one, since you can never have 3 real numbers so that the product of any 2 of them is negative.

On the other hand, consider 2 1-dimensional vectors with lists [1,1] and [-1,-1]. Both are possible from vectors (1), (1) and (1), (-1).

Therefore, the answer 3) is correct. Sometimes it is possible to tell, sometimes it isn't. The fun begins when you try to investigate when it is possible to tell...

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.