Points in $ \mathbb{R}^{n} $

Question

Let $ a_{1}, \dots a_{m} \in \mathbb{R}^{n} $ such that $ ||a_{i}-a_{j}||=1 \, \forall i \neq j $, where $ || \cdot || $ denotes the usual norm on $ \mathbb{R}^{n} $. Prove that $ m \leq n+1 $. I did it for the easy case when $ n=1 $ by explicit computation using the modulus, but I can't think of a clever argument for the general case. I think I should use some inequalities like Minkowski, Cauchy-Schwarz or the triangle inequality, but I don't see how. I would appreciate any help. Thank you!

Answer 1

If you can do it, then you can put $a_m$ at the origin. Then $a_i\cdot a_i= 1$ ($i<m$), $a_i\cdot a_j=1/2$ ($i<j<m$). Consider the $(m-1)\times(m-1)$ matrix $$A=\pmatrix{a_1\cdot a_1&a_1\cdot a_2&\cdots&a_1\cdot a_{m-1}\\ a_2\cdot a_1&a_2\cdot a_2&\cdots&a_2\cdot a_{m-1}\\ \vdots&\vdots&\ddots&\vdots\\ a_{m-1}\cdot a_1&a_{m-1}\cdot a_2&\cdots&a_{m-1}\cdot a_{m-1} } =\frac12\pmatrix{2&1&\cdots&1\\ 1&2&\cdots&1\\ \vdots&\vdots&\ddots&\vdots\\ 1&1&\cdots&2\\ }.$$ This matrix is nonsingular (why?) and that implies $a_1,\ldots,a_{m-1}$ are linearly dependent (why?). So $m-1\le n$.

Answer 2

Let $a_1,\cdots, a_m \in \mathbb{R}^n$. Without loss of generality, let $a_1$ be at the origin. Then each of $a_2,\cdots, a_m$ can be represented with their position vectors, where $\Vert a_i\Vert = 1, i>1$, and $\Vert a_i - a_j \Vert = 1, i\neq j$.

Using this, for $i, j > 1$ and not equal, you get $1 = \Vert a_i - a_j \Vert^2 = \langle a_i - a_j, a_i - a_j\rangle = \langle a_i, a_i\rangle - 2\langle a_i, a_j \rangle + \langle a_j, a_j \rangle = \Vert a_i \Vert^2 + \Vert a_j \Vert^2 - 2\langle a_i, a_j \rangle = 2 - 2\langle a_i, a_j \rangle$. Hence $\langle a_i, a_j \rangle = 1/2$.

Now I will show that each of $a_2, \cdots, a_m$ are linearly independent. This means there are at most $n$ of these, and so there are at most $n+1$ vectors (or "points") $a_1, \cdots, a_m$. Suppose $\lambda_2a_2+\cdots+\lambda_ma_m = 0$. Choose $1 < i ≤ m$. Then $0 = \langle a_i, 0 \rangle = \langle a_i, \lambda_2a_2+\cdots+\lambda_ma_m\rangle = \lambda_i + 1/2\sum_{j\neq i}\lambda_j$. Now you get $\lambda_i = -1/2\sum_{j\neq i}\lambda_j$ for each $i$. You can show that the only solution is that each $\lambda_i$ is $0$ by setting up a matrix and calculating the determinant.

Therefore you have the result!