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

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!

• So $a_m$ will satisfy $m-1$ quadratic equations in $n$ variables. Maybe you can show this means $m-1 \le n$? Apr 21 '17 at 8:37
• mathoverflow.net/questions/30270/… Apr 21 '17 at 11:05

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!

• I also had the feeling that this works for an arbitrary norm on $\mathbb{R}^n$ but I got stuck at some point... Do you think that the norm is important to show this? (cleary in your solution yes) Apr 21 '17 at 9:58
• With the trivial norm on $\mathbb{R}$, $0, 1, 2$ are all equidistant but $3 > 1+1$, so the norm is important. Apr 21 '17 at 11:21
• what is the trivial norm? Apr 21 '17 at 12:14
• As far as I see every norm on $\mathbb{R}$ only differs in a positiv factor. Apr 21 '17 at 13:51
• $$\Vert a\Vert_{trivial} = \begin{cases}1,\ a \neq 0\\ 0,\ a = 0\end{cases}$$. However, this is only a norm if you change the absolute value defined on the field over which the vector space is defined. If the absolute value for $\mathbb{R}$ is fixed, then yes, every norm is equivalent. I suspect the answer shouldn't depend on the norm in that case. I wonder how to prove that. Apr 21 '17 at 23:48

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