6
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Marc Dinh
    Apr 20, 2020 at 13:14
  • 1
    $\begingroup$ @MarcDinh My half-spaces are always so that their boundary contains the origin. Otherwise, every finite set of points lies in a half-space. $\endgroup$
    – M. Rumpy
    Apr 20, 2020 at 13:17
  • $\begingroup$ OK, sorry for that. $\endgroup$
    – Marc Dinh
    Apr 20, 2020 at 13:18
  • $\begingroup$ 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... $\endgroup$ Apr 20, 2020 at 14:21

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.