8

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?

Shovik Guha
  • 95
  • 4
  • 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. – Arthur Jan 22 '19 at 06:50
  • 2
    Is there any other information related to the vectors? Do you know anything about their values, dimension etc? – Matti P. Jan 22 '19 at 06:51
  • No information is given about the vectors other than the fact they are all in the same dimension – Shovik Guha Jan 22 '19 at 06:57
  • 2
    Obviously, if they are all orthogonal to each other, one couldn't tell. – Zeekless Jan 22 '19 at 07:09
  • It depends on the base field; if $x^2+1$ has a zero in the base field then it is always impossible to tell which is $L_1$ and which is $L_2$. – Servaes Jan 22 '19 at 14:03
  • I think a more interesting variant is the following: For each pair $(k,n)$ of natural numbers, suppose you select $k$ vectors from $\mathbb{R}^n$ and compile the lists $L_1$ and $L_2$. For which $(k,n)$ can you determine which list is which? It seems reasonable to me if $k$ is "large" compared to $n$, then you can do it - if you have a lot of vectors in small vector space, you necessarily have many positive dot products... – Jason DeVito - on hiatus Jan 22 '19 at 15:29
  • @JasonDeVito, about lots of vectors in small space: I thought about it and it doesn't seem that there must be more positive products than negative ones. For instance, consider something one-dimensional like ${-3,-2,-1,1,2,3}$ (six vectors in $\mathbb{R}^1$). There are actually 9 negative products vs only 6 positive ones. Reality works in mysterious ways. – Zeekless Jan 23 '19 at 21:37
  • 1
    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. – Jason DeVito - on hiatus Jan 23 '19 at 22:04

2 Answers2

7

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\}$.

Zeekless
  • 1,479
  • 8
  • 17
  • 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. – Shovik Guha Jan 22 '19 at 16:26
  • @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". – Zeekless Jan 22 '19 at 17:18
  • 1
    Ah, I see what you are saying now! – Shovik Guha Jan 22 '19 at 17:50
3

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...

kajacx
  • 123