Largest number of vectors with pairwise negative dot product

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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