# If $u_i\cdot u_j<0$ for all $u_0,...,u_n\in\Bbb R^n$, then the $u_i$ cannot lie in the same halfspace?

Given a set of $$n+1$$ vectors $$u_0,...,u_n\in\Bbb R^n$$ with pair-wise negative inner product, that is, $$u_i\cdot u_j<0$$ for $$i\not=j$$.

Question: what is a quick and clean way to see that the $$u_i$$ cannot all lie in the same half-space, that is, that there is no $$y\in\Bbb R^n \setminus \{ 0 \}$$ with $$y\cdot u_i\ge 0$$ for all $$i\in\{0,...,n\}$$?

• Are you sure this is correct ? In two dimension, if I take the vertex of an equilateral triangle whose center is the origin, I have $$u_i \cdot u_j = \|u_i\| \|u_j\| \cos(2*\pi/3) < 0 \ .$$ Now, taking any halfspace containing the triangle, all the vertex are contained in the same halfspace. Apr 20, 2020 at 13:14
• @MarcDinh My half-spaces are always so that their boundary contains the origin. Otherwise, every finite set of points lies in a half-space. Apr 20, 2020 at 13:17
• OK, sorry for that. Apr 20, 2020 at 13:18
• It can be done by induction on $n$. Assume you have proved the statement up to dimension $n-1$. In dimension $n$, let's say you can put all $u_0,\ldots,u_n$ into a half space $p\cdot u \ge 0$ for some unit vector $p$, look at those $v_k = u_k - (u_k\cdot p) p$ to derive a contradiction... Apr 20, 2020 at 14:21

Assume that there exists such $$y$$. Use the idea of @Calvin Lin: Denote $$u_{n+1} = -y$$. We have $$u_i\cdot u_j < 0$$ for $$0\le i < j \le n$$ and $$u_i\cdot u_{n+1}\le 0$$.

We have $$n+2$$ vectors in $$\mathbb{R}^n$$. Add the component $$1$$ as the $$n+1$$-th component to each vector. Now we get $$n+2$$ vectors in $$\mathbb{R}^{n+1}$$, so linearly dependent. Conclude that there exists $$a_0$$, $$\ldots$$, $$a_{n+1}$$ not all $$0$$ so that $$\sum_{i=0}^{n+1} a_i u_i=0$$ and $$\sum a_i= 0$$. Separate the numbers $$a_i$$ into positive and negative and ignore any zeros. We get an equality $$\sum_{i\in I} p_i u_i = \sum_{j \in J} q_j u_j$$ for some non-void disjoint subsets $$I$$, $$J$$ and positive numbers $$p_i$$, $$q_j$$. From here we get $$0\le (\sum p_i u_i) \cdot (\sum p_i u_i) = \sum_{ij} p_i q_j\ u_i \cdot u_j \le 0$$ so all of the terms above are $$0$$. It follows that $$I$$ or $$J$$ consists only of $$n+1$$, but then $$\|\sum p_i u_i\|^2>0$$, contradiction.

If we also require that the half-plane doesn't include the boundary, then ...

Proof by contradiction. Suppose such a such a half-plane defined by $$y$$ exists, then $$\{ u_i \} \cup \{-y\}$$ is a set of $$n+2$$ vectors with pairwise negative inner product.

This is not possible, e.g. See solution in mathoverflow

First of all, $$u_1, \dots, u_n$$ is a basis for $$\mathbb R^n$$. It sufficient to show $$u_1, \cdots, u_n$$ are linearly dependent. To see this, suppose $$\sum_{i=1}^n c_i u_i =0$$ for $$c_i \in \mathbb R$$. Put $$I^+ = \{ i \in \mathbb Z \cap [1, n] \mid c_i >0 \}$$ and similarly for $$I^-$$. Then $$\sum_{i \in I^+} c_i u_i = \sum_{i \in I^-} (-c_i)u_i$$ Thus $$0 \leq \left(\sum_{i \in I^+} c_i u_i \right) \cdot \left( \sum_{j \in I^+} c_j u_j \right) = \left( \sum_{i \in I^-} (-c_i)u_i \right) \cdot \left( \sum_{j \in I^+} c_j u_j \right)=\sum_{i \in I^- \\ j \in I^+}(-c_ic_j)(u_i \cdot u_j) <0$$ unless $$I^+ = \emptyset$$ or $$I^- = \emptyset$$.

Note that $$I^{+} \neq \emptyset$$ implies $$u_0 \cdot \sum_{i \in I^+} c_i u_i = \sum_{i \in I^+}c_i ( u_0 \cdot u_i)<0$$, but in this case $$I^-$$ must be empty so $$u_0 \cdot \sum_{i \in I^+} c_i u_i= u_0 \cdot \sum_{i \in I^-} (-c_i)u_i=u_0 \cdot 0 = 0$$; contradiction. The same argument is applied for the case $$I^- \neq 0$$. Therefore $$I^+ = I^- = \emptyset$$, i.e. $$c_i=0$$ for all $$i$$.

Now suppose there exists nonzero $$y \in \mathbb R^n$$ such that $$y \cdot u_i \geq 0$$ for all $$i=0,1, \dots, n$$. After renaming $$u_i$$'s, write $$y=c_1u_1 + \cdots + c_m u_m$$ ($$m \leq n$$) with all $$c_i \neq 0$$. Since $$0 \leq y \cdot u_0 = \sum_{i=1}^m c_i(u_i \cdot u_0)$$, at least one $$c_i$$ must be negative. After rearrangement, let $$c_1<0$$. Again, $$0 \leq y \cdot u_1 = \sum_{i=2}^{m} c_i(u_i \cdot u_1) + c_1 (u_1 \cdot u_1) < \sum_{i=2}^{m} c_i(u_i \cdot u_1)$$ implies that there exists $$i \geq 2$$ such that $$c_i<0$$. After rearrangement, set $$c_2<0$$. Inductively, if $$c_1, \dots, c_s$$ are all negative, then $$0 \leq y \cdot \left( \sum_{j=1}^s (-c_j)u_j \right) = \sum_{i=s+1}^{m} c_i \left( u_i \cdot \left( \sum_{j=1}^s (-c_j)u_j \right) \right) - \Big\lVert \sum_{i=1}^{s} c_i u_i \Big\rVert^2 \\ < \sum_{i=s+1}^{m} c_i \left(\underbrace{ u_i \cdot \left( \sum_{j=1}^s (-c_j)u_j \right) }_{<0}\right)$$ so there exists $$k$$ between $$s+1$$ and $$m$$ such that $$c_k <0$$. This shows that $$c_1, \dots, c_m$$ are all negative, yielding the following: $$0 \leq y \cdot y = y \cdot \sum_{i}c_iu_i = \sum_i c_i(y \cdot u_i) \leq 0$$ Hence $$y$$ must be zero.