# Largest number of vectors with pairwise negative dot product

What is the largest $$m$$ such that there exist $$v_1,\dots,v_m \in \mathbb{R}^n$$ such that for all $$i$$ and $$j$$, $$1\leq i< j\leq m$$, we have $$v_i \cdot v_j < 0$$.

Also, the preview screen is not displaying set braces for LaTeX. Is that just the preview, or does it mean the site wouldn't display them after the question had been posted either? (I formatted this question without the braces in case it's the latter.)

• you could try using \lbrace .. \rbrace if \{ \} doesn't work – Suresh Venkat Jul 11 '10 at 17:54
• It's a markdown issue. Try puttig backticks round the whole LaTeX block and see if that helps? – Yemon Choi Jul 11 '10 at 18:09
• I went in and added backticks, as in Yemon Choi's suggestion --- here on MO, it's good style to put backticks around all TeX, because it tells Markdown "don't process this part, leave it for jsMath". In this case, without the backticks, Markdown sees \{ and converts it to {, and then jsMath sees { and thinks its just a brace. Another reason for the habit of protecting TeX in backticks is that Markdown and jsMath have very different ideas about what an underscore _ means, and can get into conflict. – Theo Johnson-Freyd Jul 11 '10 at 18:38
• Note that (almost) this question arises in showing that the simple roots of a Lie algebra are linearly independent. – Allen Knutson Jul 11 '10 at 20:48
• That $m\lt n+2$ is equivalent to Lemma 8 in R. A. Rankin, On the Closest Packing of Spheres in n Dimensions, Ann. of Math. 48 (1947), pp. 1062-1081. jstor link (needs subscription) – Konrad Swanepoel Jul 12 '10 at 10:51

You can have $m=n+1$. Take the vertices of a regular simplex with centre at the origin.

You can't have $m=n+2$. There is at least a two-dimensional space of vectors $(a_1,\ldots,a_{n+2})$ such that $$\sum_{i=1}^{n+2} a_i v_i=0.$$ This gives enough room for manoeuvre to ensure some $a_i>0$ and some $a_j<0$. Thus we get some nontrivial relation $$\sum_{i\in I}a_i v_i=\sum_{j\in J}b_j v_j\qquad\qquad(*)$$ where all the $a_i>0$ and $b_j>0$ and $I$ and $J$ are disjoint non-empty sets of indices. It follows that the dot product of the two sides of $(*)$ is negative, but that contradicts it being the square of the length of the left side.

• Nice argument! – Benoît Kloeckner Jul 11 '10 at 18:12
• Side note, I get that the (central) angle between two of the $n+1$ vectors at the regular simplex vertices is $$\arccos \frac{-1}{n}.$$ It is probably somewhere in Coxeter's "Regular Polytopes" but I couldn't find it. – Will Jagy Jul 12 '10 at 1:25
• @WillJagy I think that comes basically for free by just computing dot products on the canonical coordinates in $\mathbb{R}^{n+1}$. – Steven Stadnicki Apr 20 at 16:25
• This is a very simple theorem (see @YuichiroFujiwara). For this reason, the shortcut "This gives enough room for maneuver" is a hole in the proof under the given circumstances. – Wlod AA Apr 20 at 17:13

Let us prove by induction that this number is $n+1$. The result is obvious for $n=1$. Assume it for some $n$ and consider a set of mutually negative dot product vectors $v_0,v_1,\ldots, v_k$ in $\mathbb{R}^{n+1}$. Then all of $v_1,\ldots,v_k$ lie in the open half-space $\{\,v\mid v_0\cdot v<0\,\}$. $\ \ \ \$

Now the orthogonal projections $v_i'$ of $v_i$ ($1\leqslant i\leqslant k$) on the hyperplane $\{\,v\mid v_0\cdot v=0\,\}$ satisfy $v_i'\cdot v_j'\leqslant v_i\cdot v_j$ by a direct computation (assuming $v_i$ are unitary, one has $v_i'=v_i-(v_i\cdot v_0)v_0$ so that $v_i'\cdot v_j' = v_i\cdot v_j-(v_i\cdot v_0)(v_j\cdot v_0)$). By induction $k$ is at most $n+1$ and we are done.

• Note that the lower bound holds by Robin Chapman's argument, of course. – Benoît Kloeckner Jul 11 '10 at 18:10
• Actually, you don't need to know about the perfect example for n+1 vectors. The above Yuichiro argument induces plenty of specific generic examples. For the sake of the theorem, these generic examples are much simpler. – Wlod AA Apr 20 at 17:17
• Another way of saying this geometrically: op is asking about covers of an n-1 sphere by hemispheres satisfying a certain property. If n>1, you can assume no two hemispheres are opposite. Now observe that such a cover induced another cover of the boundary of a given hemisphere, satisfying the same property. It follows that the maximal number of hemispheres can grow by at most 1 when you add 1 to the dimension. – Dmitry Vaintrob Apr 20 at 19:58

A proof from matrix theory

Let $$V=(v_1,...,v_m)\in\Bbb R^{n\times m}$$ be the matrix with the $$v_i$$ as columns. The matrix $$X:=V^\top V\in\Bbb R^{m\times m}$$ has the following properties:

• $$X$$ is positive semi-definite, that is, all eigenvalues are real and $$\ge 0$$. Furthermore, the multiplicity of the eigenvalue zero is equal $$m-d$$, wehre $$d$$ is the rank of $$X$$ and equals $$d:=\dim \mathrm{span}\{v_1,...,v_m\}\le n$$.
• $$X_{ij}=v_i\cdot v_j$$, in particular, all off-diagonal entries of $$X$$ are negative.

The matrix $$Y:=I-X$$ has only positive entries, and by Perron-Frobenius, its maximal eigenvalue has therefore multiplicity one. Hence, the minimal eigenvalue of $$X$$ has multiplicity one. Thus, the multiplicity of zero as eigenvalue of $$X$$ is at most one (it could be that zero is not an eigenvalue at all, but if it is one, it is the smallest).

Conclusively $$m-d\le1\implies m\le d+1\le n+1$$.