Conditions for including cones

Question

Consider $N$ $n$-dimensional vectors, where the angle between any two vectors is acute and their starting point is at the origin. Can we rotate these vectors together so that the coordinate components of each vector are positive?

Answer 1

Iosif Pinelis already gave a nice solution to show that the answer is "no" for sets of infinitely many vectors, and thus for $N$ very large. I'll show that the answer is also "no" even for some set of just $N = 5$ vectors.

Consider the following set of $5$ vectors in $\mathbb{R}^3$ (you can just add two extra "0" entries at the end of these of these vectors if you want $n = N$): $$ S = \{(1,0,0), (1,1,0), (0,1,1), (0,0,1), (1,-1,1)\}. $$ It is straightforward to check that the angle between any pair of these vectors is acute. However, the Gram matrix of these vectors is $$ G = \begin{bmatrix} 1 & 1 & 0 & 0 & 1 \\ 1 & 2 & 1 & 0 & 0 \\ 0 & 1 & 2 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 3 \end{bmatrix}. $$ (Side note: these vectors having acute angles corresponds exactly to this Gram matrix having all entries non-negative. One of the nice features of Gram matrices is that rotating the vectors does not change the Gram matrix: the gram matrix of $S$ is the same as the Gram matrix of $US$ for any unitary matrix $U$. In other words, the Gram matrix encodes exactly the angles between the vectors, and their lengths, but not their absolute position in space.)

It is known that the Gram matrix $G$ above is not completely positive That is, it is not the Gram matrix of vectors with non-negative entries (vectors of any dimension; not just dimension 3), so $S$ cannot be rotated so that all vectors have non-negative entries.

The fact that $G$ is not completely positive is 6 or so decades old at this point, and I don't know the original reference, but there's a great book about these things. There are lots of known $5 \times 5$ Gram matrices with non-negative entries that are known to not be completely positive, and each of them give a set of $5$ vectors with acute angles that cannot be rotated to have positive entries. And $N = 5$ is minimal for such constructions.

Answer 2

$\newcommand\R{\mathbb R}$Update: Within the previously established framework, we now show that it is enough to have just $N=4$ points. This improves what seems to be the previous record, of $N=5$. It should be clear that this new record cannot be further improved. Details on this are given at the end of the answer.

---

The answer is no.

Let us use the terms "acute angle" and "positive" in the nonstrict sense, meaning "angle $\le\pi/2$" and $\ge0$, respectively. The "strict" modification should be straightforward. By approximation, we may also assume that the set of vectors is allowed to be infinite.

Now, for any vector $u$ in $\R^d$ ($d\ge3$) with Euclidean norm $|u|=1$, consider the set
\begin{equation*} S_u:=\{u+v\colon\, v\in\R^d,|v|=1,v\cdot u=0\}, \tag{10}\label{10} \end{equation*} with $\cdot$ denoting the dot product. (One may note that (say) for the $d=3$ the set $S_u$ is the unit-radius circle in $\R^d$ centered at $u$ and lying in the affine plane through $u$ perpendicular to $u$.)

Then for any vector $u+v\in S_u$ the angle between $u+v$ and $u$ is $\pi/4$ and hence, by the subadditivity of the angle measure, the angle between any two vectors in $S_u$ is acute. One can also show this algebraically: For any $u+v$ and $u+v'$ in $S_u$, we have $(u+v)\cdot(u+v')=1+v\cdot v'\ge0$, by the Cauchy--Schwarz inequality.

Moreover, any rotation of $S_u$ is of the same form, $S_u$, but maybe for another unit vector $u$.

It remains to show that $S_u\not\subseteq\R_+^d$ for any unit vector $u$. Take indeed any such vector $u=(u_1,\dots,u_d)$. Without loss of generality, $|u_1|$ is the smallest of all the $|u_j|$'s, so that $$|u_1|-\sqrt{1-u_1^2}<0.$$ Let now \begin{equation} v=v^* :=(v_1,\dots,v_d):=\Big(-\sqrt{1-u_1^2},\frac{u_1u_2}{\sqrt{1-u_1^2}},\dots,\frac{u_1u_d}{\sqrt{1-u_1^2}}\Big). \tag{15}\label{15} \end{equation} Then $u+v\in S_u$. However, $u_1+v_1<0$, so that $S_u\not\subseteq\R_+^d$. $\quad\Box$

---

The picture below shows the set $[0,1]S_u=\{tw\,\colon t\in[0,1],w\in S_u\}$ for $d=3$ and (the apparently "best") unit vector $u=\frac1{\sqrt3}\,(1,1,1)$. It is kind of seen that $[0,1]S_u\not\subseteq\R_+^d$ and hence $S_u\not\subseteq\R_+^d$.

---

Added: Since the OP wanted an explicit finite set of vectors (rather than the infinite set $S_u$), let us provide such a set. So, for $d=3$, let $S_{u,N}$ be the set of all $N$ vertices of a regular $N$-gon inscribed into the circle $S_u$. Then the shortest distance from the point $v^*$ defined in \eqref{15} (and actually from any point on the circle $S_u$) to the set $S_{u,N}$ will be no greater than the length $2\sin\frac{2\pi}{4N}$ of a side of a regular $2N$-gon inscribed into the unit circle $S_u$. So, following lines of above reasoning, we see that, to get $w_1<0$ for at least one vertex $w=(w_1,\dots,w_3)$ of $S_{u,N}$, it is enough that $\frac1{\sqrt3}-\sqrt{1-(\frac1{\sqrt3})^2}+2\sin\frac{2\pi}{4N}<0$. The latter inequality holds for all natural $N\ge14$. Thus, we get a counterexample with a set of $14$ vectors. This is worse than $N=5$ in Nathaniel Johnston's answer; however, here the reasoning is quite elementary. (The number $N=14$ can apparently be improved even within this elementary framework, using a bit more complicated consideration.)

---

Details on the update: As in the paragraph just above, let $d=3$ and consider the set $S_{u,4}$, that is, the set $S_{u,N}$ with $N=4$, so that $S_{u,4}$ is the set of the vertices of a square inscribed into the circle $S_u$, defined in \eqref{10}. So, \begin{equation*} S_{u,4}=\{u+V_j\colon j\in\{0,1,2,3\}\}, \end{equation*} where \begin{equation*} V_j:=a\cos\Big(t+\frac{2\pi j}4\Big)+b\sin\Big(t+\frac{2\pi j}4\Big)=(V_{j,1},V_{j,2},V_{j,3})\in\R^3, \end{equation*} $t\in[0,\pi/2]$ is the angle of the rotation of the vertices of the square about the axis through the vector $u$, and $u,a,b$ are orthonormal vectors in $\R^3$. To be specific, let \begin{equation*} a=\Big(\sqrt{1-u_1^2},-\frac{u_1u_2}{\sqrt{1-u_1^2}},-\frac{u_1 \sqrt{1-u_1^2-u_2^2}}{\sqrt{1-u_1{}^2}}\Big) \end{equation*} and \begin{equation*} b=\Big(0,\frac{\sqrt{1-u_1^2-u_2^2}}{\sqrt{1-u_1^2}},-\frac {u_2}{\sqrt{1-u_1^2}}\Big), \end{equation*} with \begin{equation*} u=(u_1,u_2,u_3). \end{equation*} Here it is assumed that $u_1^2\ne1$, which can be done without loss of generality (wlog) -- otherwise, rearrange the coordinate axes.

We want to show that \begin{equation*} S_{u,4}\overset{\text{(?)}}{\not\subseteq}\R_+^3 \tag{20}\label{20} \end{equation*} for any described choices of $u$ and $t$.

Wlog, \begin{equation*} u_1\le u_2\le u_3. \end{equation*}

Suppose for a moment that $u_1\le0$. Clearly, $V_{j,1}<0$ for at least one $j\in\{0,1,2,3\}$, and then $u+V_j\in S_{u,4}\setminus\R_+^3$, so that \eqref{20} holds.

So, wlog \begin{equation*} 0<u_1\le u_2\le u_3=\sqrt{1-u_1^2-u_2^2}. \tag{30}\label{30} \end{equation*} Note that \begin{equation*} \begin{aligned} &\{u_1+V_{j,1}\colon j\in\{1,2\}\} =\left\{u_1-\sqrt{1-u_1^2}\,\sin t,u_1-\sqrt{1-u_1^2}\,\cos t\right\}. \end{aligned} \end{equation*} So, if \eqref{20} fails to hold, then \begin{equation*} u_1\ge \sqrt{1-u_1^2}\,\max(\sin t,\cos t)\ge\frac1{\sqrt2}\,\sqrt{1-u_1^2} \tag{40}\label{40} \end{equation*} and hence $u_1\ge\frac1{\sqrt3}$, which implies \begin{equation*} u_1=u_2=u_3=\frac1{\sqrt3}, \end{equation*} in view of \eqref{30}. Moreover, if we had $t\in[0,\pi/2]\setminus\{\pi/4\}$, then \eqref{40} would imply $u_1>\frac1{\sqrt3}$, which would contradict \eqref{30}.

So, if \eqref{20} fails to hold, then \begin{equation*} u_1=u_2=u_3=\frac1{\sqrt3}\quad\text{and}\quad t=\pi/4. \end{equation*} But then \begin{equation*} V_{0,3}=\frac{\sqrt{1-u_1^2-u_2^2} \left(\sqrt{1-u_1^2}-u_1 \cos t\right)-u_2 \sin t}{\sqrt{1-u_1^2}}=-0.211\ldots<0. \end{equation*} Thus, in all cases, if \eqref{20} fails to hold, then it necessarily holds. $\quad\Box$