How many unit vectors can be “close to mutually opposite” in a high dimensional space?

Question

This is actually a follow-up of this previous question: How many vectors can be "close to mutual orthogonal like 80 degrees" in a high dimensional space?

To be specific: "almost opposite" means: e.g., two unit vectors, the inner product of them is close to -1, like [-0.9 ~ -1].

My limited intuition tells me that we cannot find huge number of such vectors. Because if A is opposite to B, and B is opposite to C, then A must be C

(This deduction does not hold true for orthogonal: A orthogonal to B and B orthogonal to C. A does not have to be C).

Note we talk about high-dimensional, e.g., 100-by-1 vectors. Pls share your wisdom. Thanks

Answer 1

If $x, y, z$ are nonzero vectors (in Euclidean space of any dimension), the angle between $x$ and $z$ is at most the sum of the angle between $x$ and $-y$ and the angle between $z$ and $-y$. In particular, if the angle between $x$ and $-y$ and the angle between $z$ and $-y$ are less than $\pi/4$, $x$ and $z$ can't be "close to opposite".

Answer 2

Consider the following inequality applying to any three vectors: $$0\leq \langle x+y+z,x+y+z\rangle=\langle x,x\rangle + \langle y,y\rangle +\langle z,z\rangle + 2\langle x,y\rangle + 2\langle x,z\rangle + 2\langle y,z\rangle$$ As these are unit vectors, this simplifies to: $$0\leq 3+2\langle x,y\rangle + 2\langle x,z\rangle + 2\langle y,z\rangle.$$ A particular consequence is that at least one of the inner products has to be greater than $-\frac{1}2$. That is, you can't have three vectors, all of the angles between the being greater than $2\pi/3$.

You might observe that adding more vectors makes this worse since $$0\leq \left\langle \sum_{i=1}^nx_i,\sum_{i=1}^nx_i\right\rangle=\sum_{i=1}^n\langle x_i,x_i\rangle + 2\sum_{1\leq i < j \leq n}\langle x_i,x_j\rangle$$ which implies, if we work things out, that there is some pair $\langle x_i,x_j\rangle$ such that $$\langle x_i,x_j\rangle\geq \frac{-n}{2{n\choose 2}}=\frac{-1}{n-1}$$ which, of course tends to zero with big $n$. That is, if you demand the angle between the vectors be at least $\theta$ for $\theta>\pi/2$, you put an absolute upper bound on the number of vectors that does not grow with dimension after a point.

---

One can check actually check that this bound is tight - that is, there do actually exist sets (in high enough dimension) with low inner products provided they do not violate the condition above; in particular, if we fix any $|\alpha|\leq \frac{1}{n-1}$, we can define an $n\times n$ matrix $M$ by setting $M_{ii}=1$ and $M_{ij}=\alpha$ for $i\neq j$. This matrix is (weakly) diagonally dominated, and therefore positive semidefinite, so we can define an product on $\mathbb R^n$ by $[v,w]=v^TMw$. Let $V$ be the subspace on which $[v,v]=0$. Then $\mathbb R^n/V$ is an inner product space. Since all inner product spaces of the same finite dimension are isomorphic, there is an inner product-preserving map from $\mathbb R^n$ under our semi-inner product to $\mathbb R^n$ with the usual inner product; the image of the canonical basis (i.e. vectors with exactly one entry, which is one) under this map will be a set of unit vectors, such that the inner product of any two is $\alpha$.