Packing obtuse vectors in $\mathbb{R}^d$

Question

I came across this attractive theorem:

• Theorem. In $\mathbb{R}^d$, there can be at most $d+1$ vectors that form an obtuse angle with one another.

This was proved¹ as a corollary of a lemma about irreducible matrices. I am wondering if anyone knows of an alternative, more geometric proof that somehow more directly captures the sense that one cannot "pack" more than $d+1$ obtuse vectors in $\mathbb{R}^d$.

---

         

---

¹Lipeng Ning, Tryphon T. Georgiou, Allen Tannenbaum, Stephen P. Boyd. "Linear models based on noisy data and the Frisch scheme." SIAM Review. 57(2) 2015. arXiv preprint.

Answer 1

You can prove it by induction.

The case $d=1$ is obvious. Assume it's true for dimension $d \geq 1$, and consider any set of $d+3$ vectors in $\mathbb{R}^{d+1}$. Fix one of these, say $\vec{v}_0$, and consider the hyperplane $H$ perpendicular to it (which we can identify with $\mathbb{R}^d$). Any one of the remaining $d+2$ vectors must lie on the far side of H (i.e., not the same side as $\vec{v}_0$). No vector other than $\vec{v}_0$ can be perpendicular to $H$, since then no third vector could form an obtuse angle with both. Thus all of the remaining $d+2$ vectors lie on the same side of $H$ and each has a nonzero projection onto $H$. By hypothesis, two of them, say $\vec{v}_1$ and $\vec{v}_2$, have projections forming a non-obtuse angle. Since they lie on the same side of $H$ and their projections onto $H$ form a non-obtuse angle, the angle between them is non-obtuse. (To see that this last statement is true, consider the dot product $\vec{v}_1 \cdot \vec{v}_2$. If you compute this using a basis consisting of $\vec{v}_0$ and vectors in $H$, then the $\vec{v}_0$ term is positive (they're on the same side of $H$), and the rest of the dot product is non-negative (their projections form a non-obtuse angle).)

I don't know if this is exactly what you're looking for, but to me this proof is pretty intuitive: you can picture your vectors all pointing more or less away from $\vec{v}_0$, and then if there are too many two of them get crammed close together. The exact value of "too many" is then easily computed by induction.

Answer 2

I always give this as an exercise in my linear algebra class in the form:

If $k+1$ vectors in $\mathbb{R}^n$ form obtuse angles with one another, then after removing any one vector from that collection, the remaining vectors are linearly independent.

Proof. Assume that $v_1,\ldots,v_k$ are the remaining vectors, and that they are linearly dependent. Then $c_1v_1+\cdots+c_kv_k=0$ for some $c_1,\ldots,c_k$ not all of which are equal to zero. Without the loss of generality, $c_1,\ldots,c_m$ are positive, and $c_{m+1},\ldots,c_k$ are negative (we can remove the vectors with zero coefficients in front of them). Computing the scalar product with the vector $v$ we removed, we note that we cannot have $m=k$, so $m<k$. Now, $$ c_1v_1+\cdots+c_mv_m=-c_{m+1}v_{m+1}-\cdots-c_kv_k. $$ Therefore, $$ (c_1v_1+\cdots+c_mv_m,c_1v_1+\cdots+c_mv_m)= (c_1v_1+\cdots+c_mv_m,-c_{m+1}v_{m+1}-\cdots-c_kv_k)<0, $$ a contradiction.

Answer 3

In the context of spherical codes, this is an instance of Rankin's bound. The largest minimum distance between $m$ points on the $(n-1)$-sphere is achieved by:

(1) The vertices of a $(m-1)$-simplex inscribed in a great $(m-2)$-sphere when $m\le n+1$.

(2) Any $m$ of the $2n$ vertices of a cross-polytope inscribed in the sphere, if $n+1<m\le 2n$.

Therefore, any $n+2$ points will have to have at least one pair at a right angle or smaller.

Here is the reference to the original paper of Rankin: R. A. Rankin (1955). The Closest Packing of Spherical Caps in n Dimensions. Proceedings of the Glasgow Mathematical Association, 2, pp 139-144.

Answer 4

The proof I know of this result is essentially the same as Vladimir Dotsenko's, but in terms of Radon's lemma.:

Assume such a set exists with at least $d+2$ points. By Radon's lemma, given any $d+2$ points in $\mathbb{R}^d$ there is a partition of them into two sets $A$, $B$ such that $conv(A) \cap conv(B) \neq \emptyset$. Let $p$ be a point of this intersection. If we write $p$ as a convex combination of $A$ and one of $B$, and using the fact that the dot product of any two points in the original set is negative, we immediately obtain $p \cdot p < 0$, a contradiction.

Answer 5

Without loss of generality, the vectors are in general position. Take $d$ vectors with pairwise obtuse angles and rotate them so that they form the columns of a $d\times d$ upper-triangular matrix with nonnegative diagonal (à la $QR$ factorization). Then every entry on the diagonal is strictly positive, since otherwise the vectors would be linearly dependent, thereby violating general position. Next, in order for the columns to be pairwise obtuse, every entry above the diagonal must be strictly negative. At this point, observe that every vector which is obtuse with these $d$ columns necessarily has all strictly negative entries, but two vectors of this sort necessarily have a positive inner product with each other.