100 dot product riddle

Question

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?

Answer 1

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

Answer 2

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