Welcome to our community

Be a part of something great, join today!

Maximize the sum of squared distances

lfdahl

Well-known member
Nov 26, 2013
719
Let $P_i$ denote the $i$thpoint on the surface of an ellipsoid: $\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2} = 1$, where the principal semiaxes obey: $0 < a < b < c$.

Maximize the sum of squared distances:

\[\sum_{1\leq i < j \leq 2n}\left | P_i-P_j \right |^2\]

- over alle possible choices of $2n$ points (centroid of the points is the origin)

Please prove your result.
 

lfdahl

Well-known member
Nov 26, 2013
719
Here´s the suggested solution:


\[\sum_{1\leq i<j\leq 2n}\left | P_i-P_j \right |^2 =\frac{1}{2}\sum_{i,j = 1}^{2n}\left | P_i-P_j \right |^2 =\frac{1}{2}\sum_{i,j = 1}^{2n}\left ( \left | P_i \right |^2+\left | P_j \right |^2-2P_iP_j \right )\\\\= \frac{1}{2}\left ( 2n\sum_{i=1}^{2n}\left | P_i \right |^2+2n\sum_{j=1}^{2n}\left | P_j \right |^2-2\sum_{i,j=1}^{2n}P_iP_j \right )\\\\=2n\sum_{i=1}^{2n}\left | P_i \right |^2-\sum_{i=1}^{2n}P_i\sum_{j=1}^{2n}P_j \\\\=2n\sum_{i=1}^{2n}\left | P_i \right |^2-\left |\sum_{i=1}^{2n}P_i \right |^2\]

The first term is clearly maximized when all points $P_i$ have the maximum distance from

the origin of $c$. The second term is minimized when $\sum P_i = 0$. We can satisfy both of

these simultaneously if $n$ points are chosen to be $(0, 0, c)$ and the other $n$ points are chosen

to be $(0, 0,−c)$. In this case,

\[\sum_{1\leq i<j\leq 2n}\left | P_i-P_j \right |^2 = 2n2nc^2-0 = 4n^2c^2.\]