Minimize sum of inner products of a set of vectors

303 Views Asked by At

Please forgive me if this question has already been asked. I am not a mathematician and I expect I am missing some of the relevant vocabulary.

Consider a set of six vectors $\{v_1,v_2,v_3,v_4,v_5,v_6\}\in\mathbb{R}^3$. Additionally $|v_i|=1$ for $i=1,2,3,4,5,6$. How can I choose all $v_i$ such that the sum $$\sum_{i,j>i}v_i\cdot v_j=v_1\cdot v_2+v_1\cdot v_3+v_1\cdot v_4+v_1\cdot v_5+v_1\cdot v_6+v_2\cdot v_3+v_2\cdot v_4+v_2\cdot v_5+v_2\cdot v_6+v_3\cdot v_4+v_3\cdot v_5+v_3\cdot v_6+v_4\cdot v_5+v_4\cdot v_6+v_5\cdot v_6$$ is minimized.

The best approach I can think of at the moment is to define some function $$f(x_1,y_1,z_1,x_2,\cdots,x_6,y_6,z_6)=\sum_{i,j>i}v_i\cdot v_j$$ and then find the solution to $0=\nabla f$. However, I don't know how to constrain this solution so that $|v_i|=1$. I am interested in learning how to constrain the solution to this case, and if alternative methods exist for minimizing $f$.

Also, if there is a specific term used to denote the sum $\sum_{i,j>i}v_i\cdot v_j$, please let me know!

1

There are 1 best solutions below

0
On

This is not a full answer but something to consider in terms of symmetry. Since the dot product is symmetric, we expect the resulting configuration of vectors to possess some kind of symmetry, and in some sense to be maximally symmetric. The "maximally symmetric" configuration of $6$ vectors in $\mathbb{R}^3$ is something like $\{e_1,e_2,e_3,-e_1,-e_2,-e_3\}$. You can check that $f$ here is equal to $-3$. I do not claim that this is the minimum yet, but we can see what happens when we perturb a chosen vector out of this symmetric state.

For example, let me perturb $e_3$. Rotating it about the $e_1$ axis, let us consider what happens to $f$. The dot products of $e_3$ with $e_1$ and $-e_1$ remain unchanged. Curiously, the dot products with $e_2$ and $-e_2$, while now non-zero, cancel each other out exactly. Thus the only term affected is the dot product with $-e_3$ whose value becomes less negative. A similar argument works for rotations about the $e_2$ axis. This hints toward the fact that perturbing in any direction will only make $f$ less negative. Here's why: suppose you perturb $e_3$ slightly so that the projection onto the $xy$-plane falls in the 1st quadrant, then you can decompose the perturbed $e_3$ into a the $z$ component and the $xy$. By symmetry in the $xy$ plane, the dot product of the $xy$ portion with $e_1,e_2,-e_1,-e_2$ cancel out, so all that's left is the $z$ component which contributes to a less negative value for (perturbed $e_3$) $\cdot -e_3$. Okay so what does this establish? It establishes that this configuration is a local minimum for $f$ with $f = -3$.

This isn't the only such maximally symmetric state for which $f = -3$ either. Suppose you continuously move $e_3$ to $\frac{1}{\sqrt{2}}(e_1+e_2)$ and similarly $-e_3$ to $-\frac{1}{\sqrt{2}}(e_1+e_2)$, such that at each step, the $e_3$ and $-e_3$ are always opposite. Throughout this entire transformation, $f$ is unchanged at $-3$. So now you end up with $6$ vectors in the $xy$ plane. You can go even further and deform so that all $6$ lie on a line, $3$ in one direction and $3$ in the other. $f$ is still $-3$. So not only are these states all local minima, there is a continuous path in the configuration space that connects a lot of these states.

The one thing that remains the same in all these configurations is that every vector is accompanied by its negative. You can easily show that given these constrains, $3$ pairs of vectors and their negatives will always give you an $f = -3$. Since your configuration space is compact (product of $6$ spheres), any global extrema will occur at local extrema (there is no boundary). We are just shy of completing this proof. We need to establish that there are no other local minima. I have not yet figured out how to show this. Hopefully this helped with the intuition however! It's a highly geometric problem.