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?

Question

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\}$?

Answer 1

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

Answer 2

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.

Answer 3

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.