Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Is that an answer or a half-baked attempt? –  Arindam Pal Dec 15 '12 at 14:49
1  
Also math.berkeley.edu/~noahgian/files/spheres.pdf seems relevant –  Squark Dec 15 '12 at 15:14
2  
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
1  
This may be better suited for math.SE or even MathOverflow. –  JɛffE Dec 16 '12 at 4:54
4  
$\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
show 5 more comments

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
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
2  
@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
    
See also neilsloane.com/packings/index.html . –  Yury Dec 18 '12 at 16:54
add comment

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

share|improve this answer
6  
Is this an answer or a clarification to the question ? Also, are you asking how to understand a claim ? if so, pointing to the original source is helpful. –  Suresh Venkat Dec 16 '12 at 5:04
    
One of my friends asked me this question. I don't know from where he got this. –  Arindam Pal Dec 16 '12 at 9:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.