4
$\begingroup$

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!

$\endgroup$
2
2
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ 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) $\endgroup$ Apr 21 '17 at 9:58
  • $\begingroup$ With the trivial norm on $\mathbb{R}$, $0, 1, 2$ are all equidistant but $3 > 1+1$, so the norm is important. $\endgroup$
    – Harambe
    Apr 21 '17 at 11:21
  • $\begingroup$ what is the trivial norm? $\endgroup$ Apr 21 '17 at 12:14
  • $\begingroup$ As far as I see every norm on $\mathbb{R}$ only differs in a positiv factor. $\endgroup$ Apr 21 '17 at 13:51
  • $\begingroup$ $$\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. $\endgroup$
    – Harambe
    Apr 21 '17 at 23:48
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.