1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Do you mean "mutually nearly orthogonal?"? $\endgroup$ – Wlod AA Dec 19 '17 at 21:59
  • $\begingroup$ No. I mean mutually nearly opposite. Thx for response though :) $\endgroup$ – Bill Ancalagon the black Dec 19 '17 at 22:00
  • $\begingroup$ Under a reasonable definition of mutually nearly opposite, there can be only two. $\endgroup$ – Wlod AA Dec 19 '17 at 22:02
  • $\begingroup$ Exactly, if we put "strictly opposite". However, what if we loose the constraint to "close to opposite", does the answer blow up ? I think no, but wish to get some others' thoughts. $\endgroup$ – Bill Ancalagon the black Dec 19 '17 at 22:04
  • $\begingroup$ Only two. It's time for you to smile for a good reason. Thx for your question :). $\endgroup$ – Wlod AA Dec 19 '17 at 22:06
2
$\begingroup$

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".

$\endgroup$
  • $\begingroup$ Thanks. Make sense. And I noticed that this logic does not hold true for "close to mutual orthogonal", which is really good. $\endgroup$ – Bill Ancalagon the black Dec 21 '17 at 21:19
  • $\begingroup$ (I mean, in high dimensional space, when we loose the constraint from "strictly mutual orthogonal" to "mutually close to orthogonal", then the number of solutions blow up exponentially. --- When I propose this question of "close to opposite", I was wondering whether similar case hold true for "opposite") $\endgroup$ – Bill Ancalagon the black Dec 21 '17 at 21:25
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thanks a lot for the detailed answer. So the conclusion is ... yes or no (e.g., Yes means there are huge number of such vectors, No means there are not many) ? Thx :) $\endgroup$ – Bill Ancalagon the black Dec 21 '17 at 21:18
  • $\begingroup$ @BillAncalagontheblack No. $\endgroup$ – Milo Brandt Dec 21 '17 at 21:27

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.