Hi! I want to show that sum(norm(x_i-x_j), 1<=i<j<=n) <= n^2 for any vector space over R or C, where x_i are unit vectors.
I haven't got any idea how to show this. Can somebody please help me?
Banach
This is true if you are using a euclidean or Hilbert space norm, but it need not hold for other norms. For example, in the space $\displaystyle \mathbb{R}^2$ with the norm $\displaystyle \|(x,y)\| = |x|+|y|$, the four vectors $\displaystyle (\pm1,0),\ (0\pm1)$ are all distance 2 from each other, so the sum of the squares of the six distances is 24 which is greater than 16.
Here's how to prove the result for a real vector space where the norm comes from an inner product $\displaystyle \langle\,,\,\rangle$.
$\displaystyle \sum_{1\leqslant i<j\leqslant n}||x_i-x_j||^2 = \tfrac12\sum_{i,j=1}^n\langle x_i-x_j,x_i-x_j\rangle$
. . . . . . . . . . . . . .$\displaystyle = \sum_{i=1}^n\langle x_i,x_i\rangle - \sum_{i,j=1\atop i\ne j}^n\langle x_i,x_j\rangle$
. . . . . . . . . . . .. . $\displaystyle \leqslant \sum_{i=1}^n\langle x_i,x_i\rangle + \sum_{i,j=1\atop i\ne j}^n\langle x_i,x_j\rangle$
. . . . . . . . . . . .. . $\displaystyle = \sum_{i,j=1}^n\langle x_i,x_j\rangle = \Bigl\|\sum_{i=1}^nx_i\Bigr\|^2 \leqslant n^2$
The proof for complex spaces is more or less the same, with complex conjugates inserted where appropriate.
Hi, thanks for your answer. You are right, i forgot the prerequisite euclidian space.
Why does the inequation $\displaystyle \leqslant \sum_{i=1}^n\langle x_i,x_i\rangle + \sum_{i,j=1\atop i\ne j}^n\langle x_i,x_j\rangle
$ hold? If $\displaystyle \sum_{i,j=1\atop i\ne j}^n\langle x_i,x_j\rangle
$ would be positive then it would be clear. But this is not the case. Can you explain this step to me please?
Greetings
Banach
$\displaystyle \sum_{1\leqslant i<j\leqslant n}||x_i-x_j||^2 = \tfrac12\sum_{i,j=1}^n\langle x_i-x_j,x_i-x_j\rangle$
. . . . . . . . . . . . . .$\displaystyle = \sum_{i=1}^n\langle x_i,x_i\rangle - \sum_{i,j=1\atop i\ne j}^n\langle x_i,x_j\rangle$
. . . . . . . . . . . .. . $\displaystyle =n-2\sum_{i<j}\langle x_i,x_j\rangle$
. . . . . . . . . . . .. . $\displaystyle \leq n+2\sum_{i<j}||x_i||\cdot ||x_j||$ by Cauchy-Schwarz
. . . . . . . . . . . .. . $\displaystyle n+2{n\choose 2}=n^2$
Alright, thank you both very much. Now everything is clear.
Another proof came to my mind:
One can show that $\displaystyle \sum_{1\leqslant i<j \leqslant n}||x_i - x_j||^2+||\sum_{i=1}^n x_i||^2=n*(\sum_{i=1}^n ||x_i||^2)$. Therefore the claim follows immediately.
Good night!
Banach