|
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$? |
|||||||||||||||||||||
|
|
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. |
|||||||||||
|
|
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$. |
|||||||
|
