Bounds on Non-Positive Inner Product Sets in Real Vector Space

Proposition

In ${\mathbb{R}}^n$, the maximum number of vectors $v_1,\dots ,v_m$ such that $⟨v_i,v_j⟩<0$ for all $i\ne j$ is $m=n+1$.

\begin{proof} Suppose $m$ vectors in ${\mathbb{R}}^n$ satisfy the condition. We show any $m-1$ vectors are linearly independent. Otherwise, assume that ${\sum }_{i=1}^k{c}_i{v}_i=0$ for $k<m$. Separate coefficients into positive ($P$) and negative ($N$) indices:

$$\sum _{i\in P}{c}_i{v}_i=\sum _{j\in N}\left(-c_j\right)v_j=w$$

Then $\Vert w{\Vert }^2=⟨{\sum }_{i\in P}{c}_i{v}_i,{\sum }_{j\in N}\left(-c_j\right)v_j⟩={\sum }_{i\in P}{\sum }_{j\in N}-c_i{c}_j⟨v_i,v_j⟩$. Since $c_i,-c_j>0$ and $⟨v_i,v_j⟩<0$, each term is $\le 0$. Thus $\Vert w{\Vert }^2\le 0⟹w=0$.

Notice that $0=⟨w,v_m⟩={\sum }_{i\in P}{c}_i⟨v_i,v_m⟩$. Since all $⟨v_i,v_m⟩<0$, this implies all $c_i=0$. Thus, any $m-1$ vectors are linearly independent, so $m-1\le n$, which means $m\le n+1$. \end{proof}

Lemma

In ${\mathbb{R}}^n$, the maximum number of vectors $v_1,\dots ,v_m$ such that $⟨v_i,v_j⟩\le 0$ and $v_i\ne -k{v}_j$ for all $i\ne j$ and $k\ne 0$ is $m=n+1$.

\begin{proof} Since there does not exist anti-parallel pairs, for such $v_1,\cdots ,v_m$, we can get $v_1(ϵ),\cdots ,v_m(ϵ)$ such that $⟨v_i(ϵ),v_j(ϵ)⟩<0$. Then by ^gwjb1o, $m=n+1$. \end{proof}

Proposition

In ${\mathbb{R}}^n$, the maximum number of vectors $v_1,\dots ,v_m$ such that $⟨v_i,v_j⟩\le 0$ for all $i\ne j$ is $m=2n$.

\begin{proof} By Induction on $n$. In ${\mathbb{R}}^1$, if $x\cdot y\le 0$, we can have at most one positive and one negative number (e.g., $\{1,-1\}$), which deduces that $m=2$. Now assume the bound $2(n-1)$ holds for ${\mathbb{R}}^{n-1}$. Let $V$ be a set in ${\mathbb{R}}^n$ satisfying the condition. If no two vectors are anti-parallel $\left(v_i\ne -k{v}_j\right)$, the bound is smaller by ^70d15f. If there exists a pair of opposite vectors $u$ and $-u\in V$, then for any other vector $w\in V\backslash \{u,-u\}$, we must have $⟨w,u⟩=0$.

This forces all remaining $m-2$ vectors to lie in the $(n-1)$-dimensional subspace orthogonal to $u$. By the inductive hypothesis, there are at most $2(n-1)$ such vectors. Then total $m\le 2(n-1)+2=2n$.

\end{proof}