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

<p>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.</p>

<p>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 &lt; j} v_i \cdot v_j \leq \sum_i 1 + 2\sum_{i&lt;j} \alpha = k + k(k-1) \alpha.$$
We get that $\alpha \geq - 1/(k-1)$.</p>

<p>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).$$</p>

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

<p>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 <a href="http://en.wikipedia.org/wiki/Lov%C3%A1sz_number">the Lovász Theta Function</a> for details.</p>

CC BY-SA 3.0
2012-12-17T02:27:42.507Z
That was a great answer and one I was looking for. Thanks a lot, Yury!
Arindam Pal
CC BY-SA 3.0
2012-12-18T12:08:02.737Z
What happens when $k>n+1$?
Klaus Draeger
CC BY-SA 3.0
2012-12-18T16:42:50.420Z
@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
CC BY-SA 3.0
2012-12-18T16:54:17.833Z
See also http://neilsloane.com/packings/index.html .
Yury
CC BY-SA 4.0
2020-04-05T04:03:51.937Z
what is a regular simplex? Is it not the convex hull of 0 and e_i's?
Karagounis Z
CC BY-SA 3.0
2012-12-16T15:18:24.370Z
2012-12-16T15:26:10.697Z
2012-12-16T15:26:10.697Z
Yury
<p>This problem is closely related to the <em>graph coloring</em> problem. The problem is to color the vertices of a $k$-colorable graph with as few colors as possible. The following <em>vector program</em> is a relaxation of the graph coloring problem.</p>

<p>$$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$$</p>

<p>The claim is that $-\frac{1}{k-1}$ is the minimum possible value of $\alpha$.</p>

CC BY-SA 3.0
2012-12-16T05:04:53.383Z
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
CC BY-SA 3.0
2012-12-16T09:44:44.447Z
One of my friends asked me this question. I don't know from where he got this.
Arindam Pal
CC BY-SA 4.0
2023-04-11T09:53:48.903Z
I believe the source may be Lemma 4.1 of [this paper](https://dl.acm.org/doi/10.1145/274787.274791). They don't show prove the upper bound, but give an explicit construction that reaches this bound.
BrockenDuck
CC BY-SA 3.0
2012-12-16T05:02:15.247Z
2012-12-16T05:02:15.247Z
Arindam Pal
<p>Suppose, we are given a set of $k$ <strong>unit</strong> 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,</p>

<p>$$\alpha = \max_{1 \le i &lt;j \le k} \{v_i \cdot v_j\}.$$</p>

<p>What is the <strong>minimum</strong> possible value of $\alpha$?</p>

CC BY-SA 3.0
2012-12-15T14:33:12.263Z
I'm not sure how is this related to computer science, but you can obtain a bound on this by drawing a spherical ball of radius $r$ around each of the $k$ points you have on the $n-1$-dimensional sphere. As long as the balls don't touch, the sum of their $n-1$-volumes has to be less than the total $n-1$-volume of the unit $n-1$-sphere. The maximal admissible $r$ is related to your $\alpha$ in the obvious way.
Vanessa
CC BY-SA 3.0
2012-12-15T14:49:50.583Z
Is that an answer or a half-baked attempt?
Arindam Pal
CC BY-SA 3.0
2012-12-15T14:53:36.597Z
It can easily be converted to a precise formula. It only yields a lower bound but the bound becomes tight up to a $k$-independent factor for $k >> n$
Vanessa
CC BY-SA 3.0
2012-12-15T15:14:37.533Z
Also http://math.berkeley.edu/~noahgian/files/spheres.pdf seems relevant
Vanessa
CC BY-SA 3.0
2012-12-15T15:16:58.290Z
Can you please point to the specific page number or theorem?
Arindam Pal
CC BY-SA 3.0
2012-12-15T17:07:17.150Z
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
Vanessa
CC BY-SA 3.0
2012-12-16T04:54:34.610Z
This may be better suited for math.SE or even MathOverflow.
Jeffε
CC BY-SA 3.0
2012-12-16T05:05:50.670Z
@JɛﬀE seems like a standard packing question on the sphere that has reasonable CS connections
Suresh Venkat
CC BY-SA 3.0
2012-12-16T06:12:06.067Z
$\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
CC BY-SA 3.0
2012-12-16T09:50:16.277Z
Thanks Yury. I want to understand why the least value is attained when the vectors are vertices of a regular simplex. Is it just symmetry or is there a formal proof? Can you please point me to some lecture notes or books where there is a proof?
Arindam Pal
<linear-algebra><convex-optimization><convex-geometry>
Minimizing the maximum dot product among k unit vectors in an n-dimensional space
Arindam Pal
# Minimizing the maximum dot product among k unit vectors in an n-dimensional space

(Asked by: username_0 on 2012-12-15)

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 

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

**Tags:** linear-algebra, convex-optimization, convex-geometry

> **Comments:**
> **username_1**: I'm not sure how is this related to computer science, but you can obtain a bound on this by drawing a spherical ball of radius $r$ around each of the $k$ points you have on the $n-1$-dimensional sphere. As long as the balls don't touch, the sum of their $n-1$-volumes has to be less than the total $n-1$-volume of the unit $n-1$-sphere. The maximal admissible $r$ is related to your $\alpha$ in the obvious way.  
> **username_0**: Is that an answer or a half-baked attempt?  
> **username_1**: It can easily be converted to a precise formula. It only yields a lower bound but the bound becomes tight up to a $k$-independent factor for $k >> n$  
> **username_1**: Also http://math.berkeley.edu/~noahgian/files/spheres.pdf seems relevant  
> **username_0**: Can you please point to the specific page number or theorem?  
> **username_1**: 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  
> **username_2**: This may be better suited for math.SE or even MathOverflow.  
> **username_3**: @JɛﬀE seems like a standard packing question on the sphere that has reasonable CS connections  
> **username_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.)  
> **username_0**: Thanks username_4. I want to understand why the least value is attained when the vectors are vertices of a regular simplex. Is it just symmetry or is there a formal proof? Can you please point me to some lecture notes or books where there is a proof?  

---

## 2 answers

### Answer by username_4 on 2012-12-16. Score: 7 | Accepted answer

**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

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](http://en.wikipedia.org/wiki/Lov%C3%A1sz_number) for details.

> **Comments:**
> **username_0**: That was a great answer and one I was looking for. Thanks a lot, username_4!  
> **username_5**: What happens when $k>n+1$?  
> **username_4**: @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.  
> **username_4**: See also http://neilsloane.com/packings/index.html .  
> **username_6**: what is a regular simplex? Is it not the convex hull of 0 and e_i's?  

---

### Answer by username_0 on 2012-12-16. Score: 0

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

> **Comments:**
> **username_3**: 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.  
> **username_0**: One of my friends asked me this question. I don't know from where he got this.  
> **username_7**: I believe the source may be Lemma 4.1 of [this paper](https://dl.acm.org/doi/10.1145/274787.274791). They don't show prove the upper bound, but give an explicit construction that reaches this bound.  

---

