A linear equation problem related to projection

Question

Let $v_1,\cdots,v_s$ be $s$ vectors in $\mathbb R^d$ such that every set of $d$ vectors are linearly independent. Let $x_1,\cdots,x_n$ be $n$ vectors in $\mathbb R^d$ that satisfy the following linear equations: $$v_i^T x_{a_i}=v_i^T x_{b_i}, \quad i=1,\cdots,s.$$ where $a_i$ and $b_i$ are arbitrary indices such that $a_i\neq b_i$, $i=1,\cdots,s$. I find that when $s=(n-1)d$, there must exist two indices $p\neq q$ such that $x_p=x_q$.

I have checked several simple cases, such as when $n\le 3$ and $d\le 4$, and I am quite sure that the result holds for general $n$ and $d$. But proving it seems to be hard. As can be seen, the problem has strong symmetry. I have tried Gaussian elimination but such an approach heavily destroys the symmetry and fails to prove it.

Answer 1

Just to make it easier let

$V := \{v_1, ...,v_s\}$

$X:= \{x_1, ..., x_n\}$

And then let $X_i := \{x \in X| \ v_i^Tx = v_i^Tx',\ for\ some\ x'\in X, \ x' \neq x \}$

You're condition is then equivalent to $$|X_i| \geq 2 $$

I don't think your claim is correct, allow me to give the following counterexample:

Let $d =2$, $s= 10$ then we have $n= 6$, if we use $s = (n-1)d$ and assume $$|X| = n$$ that is, that there are no "duplicates"

Then we ask the question, "what is the space in which the solutions, $v$, to $v^Tx_1 = v^Tx_2$ live?"

And you can confirm that this space is a vector space, and it is all vectors perpendicular to the vector $x_1-x_2$ Then we ask,

"Given 6 distinct $x_i$ vectors, can we find 10 linearly independent $v$ vectors in the spaces spanned by some $x_i - x_j, \ i\neq j$ ?"

(Not that when $d=2$ your first requirement on $V$ simply says that no vcetor in $V$ is a scalar multiple of another vector in $V$

And I believe the answer to that question is affirmative, since we can generate $\binom62 \ = 15$ spaces for our $V$ vectors to lie in, since we have 15 (6 choose 2) possible instances of $x_i -x_j, \ i \neq j$

and yes, I have not shown that it is possible for at least 10 of these to be distinct, it seems unlikely that this is not possible, you can try for yourself however:

Draw a hexagon where each side has a different slope, and connect all the vertices, if you can connect at least 4 vertices, each successive one with an unused slope, then you can construct a counterexample

The reason the small test cases failed is because for example $\binom32 \ = \ 3 < (3-1)2 = 4$ so your condition was actually stronger in those cases than the condition I proposed, this scales up nicely, and I think the correct condition for failure is $s>\binom{n}{d}$ which would be rather nifty, but I can't prove this rigorously as of now

Answer 2

I got to understand say $n=2$ and $s=d$, you are putting $\langle x_1;v_i\rangle=\langle x_2;v_i\rangle$ for all $i=1,\ldots, d$. This implies by linear combination, as $(v_1;\ldots;v_d)$ is a basis, that $x_1-x_2$ is orthogonal to every vector in $\mathbb{R}^d $ and thus is zero.