1. Inequation with unit vectors

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.

Banach

2. There are $\displaystyle {n\choose 2}$ ways to select two indices $\displaystyle i<j$. So
$\displaystyle \sum_{i<j}||x_i-x_j||\leq \sum_{i<j}||x_i||+||x_j||=2{n\choose 2}=n(n-1)<n^2$

3. Hi! Thanks for your answer. I realized that i forgot to square the norm, so it should be shown: $\displaystyle \sum_{i<j}||x_i-x_j||^2 \leq n^2$ and thus your idea does not work, since one has $\displaystyle 4*{n \choose 2}$? How can this be solved?

4. Originally Posted by Banach
Hi! I want to show that $\displaystyle \sum_{1\leqslant i<j\leqslant n}||x_i-x_j||^2 \leq n^2$ for any vector space over R or C, where x_i are unit vectors.
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.

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

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

7. Originally Posted by Banach
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.
You're right, that was a careless mistake. See watchmath's correction above.

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