Maximum number of pairwise non-acute vectors in R^n

May 21, 2017

It is said to be well-known, but perhaps I've never seen it before: there are at most 2n2n non-zero vectors in RnRn such that the inner product of any two of them is not positive.

Proof:
We could always change the basis such that one of the vectors is (δ,0,…,0)(δ,0,…,0) where δ>0δ>0. Obviously there could not be any other vector with positive first coordinate, i.e. the rest of vectors are grouped into AA and BB, where AA consists of vectors with negative first coordinate, and BB zero first coordinate. Express each vector in (x,v)(x,v) where x∈Rx∈R. The vvs in AA do not have duplicate, because that would violate the assumption. Similary the vvs in BB are distinct. Moreover vvs from AA and BB are distinct as well. This means that these vvs in A∪BA∪B are all different and possess the property of pairwise non-positive inner product, except AA could have one zero vector. By induction this finishes the proof.
Q.E.D.

The induction proof also leads to another interesting and intuitive result: for n>1n>1 optimality happens only with nn mutual orthogonal vectors and their scaled negatives.

post by Shen-Fu Tsai