25
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ Note that (almost) this question arises in showing that the simple roots of a Lie algebra are linearly independent. $\endgroup$ Jul 11, 2010 at 20:48
  • $\begingroup$ 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) $\endgroup$ Jul 12, 2010 at 10:51

3 Answers 3

43
$\begingroup$

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\tag{$*$}\label{star}$$ 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 \eqref{star} is negative, but that contradicts it being the square of the length of the left side.

$\endgroup$
6
  • 1
    $\begingroup$ Nice argument! $\endgroup$ Jul 11, 2010 at 18:12
  • 3
    $\begingroup$ 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. $\endgroup$
    – Will Jagy
    Jul 12, 2010 at 1:25
  • $\begingroup$ @WillJagy I think that comes basically for free by just computing dot products on the canonical coordinates in $\mathbb{R}^{n+1}$. $\endgroup$ Apr 20, 2020 at 16:25
  • $\begingroup$ 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. $\endgroup$
    – Wlod AA
    Apr 20, 2020 at 17:13
  • $\begingroup$ Could you elaborate about why the 2D space is giving enough room to manoeuvre and 1D is not? $\endgroup$
    – Michael
    Aug 3, 2021 at 19:32
12
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Note that the lower bound holds by Robin Chapman's argument, of course. $\endgroup$ Jul 11, 2010 at 18:10
  • $\begingroup$ 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. $\endgroup$
    – Wlod AA
    Apr 20, 2020 at 17:17
  • $\begingroup$ 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. $\endgroup$ Apr 20, 2020 at 19:58
  • $\begingroup$ @WlodAA, re, there and there you mention an argument by @‍YuichiroFujiwara, but I can't find it. Where is it? $\endgroup$
    – LSpice
    Jan 6 at 16:52
9
$\begingroup$

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 (and let us assume that $\|v_i\|=1$). 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$, where $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, the diagonal of $X$ consists of 1-s, and the off-diagonal entries of $X$ are negative.

The matrix $Y:=2I-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).

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.