# Minimizing the maximum dot product among k unit vectors in an n-dimensional space

Suppose, we are given a set of $k$ unit vectors $v_1,\ldots,v_k$ in $\mathbb{R}^n$. Consider all possible dot products among distinct vectors $v_i \cdot v_j$, where $i \ne j$. Let,

$$\alpha = \max_{1 \le i <j \le k} \{v_i \cdot v_j\}.$$

What is the minimum possible value of $\alpha$?

-
Is that an answer or a half-baked attempt? –  Arindam Pal Dec 15 '12 at 14:49
Also math.berkeley.edu/~noahgian/files/spheres.pdf seems relevant –  Squark Dec 15 '12 at 15:14
I haven't read the article in detail, but the problem of packing spheres on a sphere is exactly the same as selecting unit vectors s.t. all dot products are above some fixed value. Since this is an introductory article I suspect that the article and references therein should tell you about state-of-the-art in understanding this problem –  Squark Dec 15 '12 at 17:07
This may be better suited for math.SE or even MathOverflow. –  JɛﬀE Dec 16 '12 at 4:54
$\alpha = - 1 / (k-1)$. This value is attained when vectors $v_i$ are vertices of a regular simplex (centered at $0$). This fact is used a lot in the design and analysis of Semidefinite Programming algorithms. (This question is not a research-level question in TCS.) –  Yury Dec 16 '12 at 6:12

Answer: $\alpha = - 1/(k-1)$. This value is attained when vectors $v_i$ are the vertices of a regular simplex, centered at the origin.

This follows from symmetry: given a set of vectors $u_i$ consider new vectors $u_i'= \frac{1}{\sqrt{k}}\left( u_i \oplus u_{i+1} \oplus \dots \oplus u_{i-1} \right)$ (where we add up all vectors $u_i$ in the cyclic order starting from $u_i$). It is easy to show that vectors $u'_i$ form a better (or equal) solution than vectors $u_i$, and that vectors $u_i$ are vertices of a regular simplex (not necessarily centered at $0$). Symmetry arguments (like this one) are very useful in general for finding extreme configurations of vectors. In this case, it is very easy to find the value of $\alpha$ directly.

I. Let us first prove that $\alpha \geq -\frac{1}{k-1}$. We have, $$0 \leq \|v_1 + \dots + v_k\|^2 = \sum_i \|v_i\|^2 + 2\sum_{i < j} v_i \cdot v_j \leq \sum_i 1 + 2\sum_{i<j} \alpha = k + k(k-1) \alpha.$$ We get that $\alpha \geq - 1/(k-1)$.

II. Now we prove that $\alpha \leq -\frac{1}{k-1}$. Consider a $k\times k$ matrix $A = (a_{ij})$ with $a_{ii} = 1$ and $a_{ij} = {-1/(k-1)}$ for $i\neq j$. This matrix is (non-strictly) diagonally dominant and thus is positive semidefinite. (Note also that $A$ is the normalized Laplacian matrix of $K_k$.) Therefore, there exist a set of vectors $v_i$ with $v_i \cdot v_j = a_{ij}$. We get that $$\alpha \leq \max_{i\neq j} a_{ij} = -1/(k-1).$$

We proved that $\alpha = -1/(k-1)$. Note that vectors $v_i$ are vertices of a regular simplex since the distance $\|v_i - v_j\| = \sqrt{2- 2v_i \cdot v_j} = \sqrt{2k/(k-1)}$ is the same for all pairs $i,j$ (where $i\neq j$), and $\sum v_i =0$ since $\|\sum v_i\|^2 = 0$.

What we computed equals $$-\frac1{\vartheta(\text{empty graph on } k \text{ vertices})-1},$$ where $\vartheta$ is the Lovász Theta Function; see the Wikipedia article on the Lovász Theta Function for details.

-
That was a great answer and one I was looking for. Thanks a lot, Yury! –  Arindam Pal Dec 17 '12 at 2:27
What happens when $k>n+1$? –  Klaus Draeger Dec 18 '12 at 12:08
@KlausDraeger: That's a much more difficult problem! There is no closed form expression for $\alpha$ in this case. Extreme configurations of vectors are known only for certain values of $n$ and $k$. A configuration of vectors on the unit sphere in $n$ dimensions s.t. $\langle v_i, v_j \rangle \leq t$ is known as $(n,k,t)$ spherical code. The question asks to find the best possible $t$ s.t. an $(n,k,t)$ spherical code exists. See table 1 on p. 102 in [Cohn, Kumar. Universally optimal distribution of points on spheres. J. of AMS, vol. 20, n. 1; available on arXiv] for the list of known results. –  Yury Dec 18 '12 at 16:42
This problem is closely related to the graph coloring problem. The problem is to color the vertices of a $k$-colorable graph with as few colors as possible. The following vector program is a relaxation of the graph coloring problem.
$$minimize \qquad \alpha \qquad \qquad \\ subject \ to \quad v_i \cdot v_j \le \alpha \quad \; \; \, \forall (i,j) \in E \\ \qquad \quad \ v_i \cdot v_i = 1 \quad \quad \forall i \in V \\ \qquad \qquad \quad \ v_i \in \mathbb{R}^n \quad \forall i \in V$$
The claim is that $-\frac{1}{k-1}$ is the minimum possible value of $\alpha$.