I don't know if this works or not, a lot of it is intuitive, but I think there might be some good ideas in there. First of all, if the vectors $\vec {u_i}=(a_{i1},\ a_{i2},\ a_{i3})$ are coplanar, then it's easy to show that all the three components of the non-zero solution of the system $a_{i1}c_i+a_{i2}c_2+a_{i3}c_3=0$ have the same sign. In this case we find positive $c_i$ s.t. all of those expressions are equal to $0$. We may thus assume that the three vectors are not coplanar (or, in other words, we may assume they're independent). We have to find three positive numbers $t_i$ s.t. all the components of the solution of the system $a_{i1}c_1+a_{i2}c_2+a_{i3}c_3=t_i$ have the same sign. In other words, we have to find positive $t_i$ s.t. the three determinants obtained from $\left |\begin{array}{ccc}a_{11}&a_{12}&a_{13}\\ a_{21}&a_{22}&a_{23}\\ a_{31}&a_{32}&a_{33}\end{array}\right |$ by replacing a column with $\left (\begin{array}{c}t_1\\ t_2\\ t_3\end{array} \right )$ have the same sign. This translates to the point $T(t_1,t_2,t_3)$ being on the interior of the trihedron determined by the lines $OP_1,OP_2,OP_3$, where $P_i(a_{1i},a_{2i},a_{3i}$. It really isn't hard to show that such a point $T$ exists (by "trihedron" I understand the figure formed by three lines in space, not three rays, as we usually understand). This is the part I'm not convinced about. It's related to the fact that the oriented volume of a tetrahedron which has $O$ as a vertex depends on the direction in which we consider the three vertices different from $O$ (clockwise/anticlockwise direction). Opinions?

In the official solution (and maybe grobber's reply), it says that it suffices to show that if we set $ O(0,0,0)$, $ P(a_{11},a_{21},a_{31})$, $ Q(a_{21},a_{22},a_{23})$, $ R(a_{31},a_{32},a_{33})$ in 3d space then there exists a point in the interior of $ \triangle PQR$ all of whose coordinates are all positive, negative, or zero. It does not give justification, though. Can someone explain this? I am just a beginner .

1. dgreenb801 wrote: In the official solution (and maybe grobber's reply), it says that it suffices to show that if we set $ O(0,0,0)$, $ P(a_{11},a_{21},a_{31})$, $ Q(a_{21},a_{22},a_{23})$, $ R(a_{31},a_{32},a_{33})$ in 3d space then there exists a point in the interior of $ \triangle PQR$ all of whose coordinates are all positive, negative, or zero. That's because every point inside the triangle $ PQR$ has coordinates $ \left( a_{11}c_{1}+a_{12}c_{2}+a_{13}c_{3}, a_{21}c_{1}+a_{22}c_{2}+a_{23}c_{3}, a_{31}c_{1}+a_{32}c_{2}+a_{33}c_{3} \right)$ for some positive reals $ c_1$, $ c_2$, $ c_3$. In fact, you can take $ c_1$, $ c_2$, $ c_3$ as the barycentric coordinates of the point with respect to triangle $ PQR$ (normalized to satisfy $ c_1+c_2+c_3=1$). 2. I remember having solved this problem some years ago (alas, not on the TST) using some casebash and Helly. Now I know there is a solution on a few lines, alas using analysis: Let $ A$ be the matrix $ \left(a_{ij}\right)_{1\leq i\leq 3,\ 1\leq j\leq 3}$. Let $ K$ be a real which is greater than $ \max\left\{a_{11},a_{22},a_{33}\right\}$. Then, all entries of the matrix $ K\cdot I_3-A$ are strictly positive. Hence, after the Perron-Frobenius theorem, there exists a right eigenvector $ v$ of $ A$ such that all three components of $ v$ are strictly positive. This vector $ v$ then satisfies $ \left(K\cdot I_3-A\right)v=\mu v$, where $ \mu$ is the corresponding eigenvalue. This rewrites as $ Av=\left(K-\mu\right)v$. Hence, the three components of $ Av$ are proportional to those of $ v$, so they are either all negative, or all zero, or all positive. Now, if we write $ v$ in the form $ v=\left(\begin{array}{c} c_1\\ c_2\\ c_3 \end{array}\right)$, then $ Av=\left(\begin{array}{c} a_{11}c_{1}+a_{12}c_{2}+a_{13}c_{3} \\ a_{21}c_{1}+a_{22}c_{2}+a_{23}c_{3} \\ a_{31}c_{1}+a_{32}c_{2}+a_{33}c_{3} \end{array}\right)$, and we are done. This generalizes to $ n$-vectors. darij

This might be slightly flawed somewhere. As stated above, it suffices to find positive $d_1,d_2,d_3$ such that the values \[\left |\begin{array}{ccc}d_1&a_{12}&a_{13}\\ d_2&a_{22}&a_{23}\\ d_3&a_{32}&a_{33}\end{array}\right |,\left |\begin{array}{ccc}a_{11}&d_1&a_{13}\\ a_{21}&d_2&a_{23}\\ a_{31}&d_3&a_{33}\end{array}\right |,\left |\begin{array}{ccc}a_{11}&a_{12}&d_1\\ a_{21}&a_{22}&d_2\\ a_{31}&a_{32}&d_3\end{array}\right |\]all have the same sign. There are four cases to consider now. Case 1: $a_{22}a_{33}\ge a_{23}a_{32}$ and similarly for the other pairs. Then we must have that all three values are positive. Case 2: Only $a_{22}a_{33}<a_{23}a_{32}$. Then the second and third values are still positive; thus, we may set $d_2$ and $d_3$ to be very large. Case 3: Only $a_{22}a_{33}\ge a_{23}a_{32}$. Then the other two values need to be positive. We can achieve this by simply setting $d_1$ to be very large. Case 4: $a_{22}a_{33}<a_{23}a_{32}$ and similarly for the other pairs. Then the determinants are equal to \[d_1(a_{22}a_{33}-a_{23}a_{32})+d_2(a_{13}a_{32}-a_{12}a_{33})+d_3(a_{12}a_{23}-a_{13}a_{22})\]\[d_1(a_{31}a_{23}-a_{21}a_{33})+d_2(a_{11}a_{33}-a_{31}a_{13})+d_3(a_{13}a_{21}-a_{23}a_{11})\]\[d_1(a_{21}a_{32}-a_{31}a_{22})+d_2(a_{12}a_{31}-a_{32}a_{11})+d_3(a_{11}a_{22}-a_{21}a_{12})\]so it suffices to show that we can make $d_2$ and $d_3$ very large while satisfying \[d_2(a_{11}a_{33}-a_{31}a_{13})+d_3(a_{13}a_{21}-a_{23}a_{11})\ge 0\iff d_3(a_{13}a_{21}-a_{23}a_{11})\ge d_2(a_{13}a_{31}-a_{11}a_{33})\]\[d_2(a_{12}a_{31}-a_{32}a_{11})+d_3(a_{11}a_{22}-a_{21}a_{12})\ge 0\iff d_2(a_{12}a_{31}-a_{32}a_{11})\ge d_3(a_{12}a_{21}-a_{11}a_{22}).\]Then we have that \[\frac{a_{12}a_{21}-a_{11}a_{22}}{a_{12}a_{31}-a_{32}a_{11}}\le \frac{d_2}{d_3} \le \frac{a_{13}a_{21}-a_{23}a_{11}}{a_{13}a_{31}-a_{11}a_{33}}\]so it suffices to show that \[(a_{12}a_{21}-a_{11}a_{22})(a_{13}a_{31}-a_{11}a_{33})\le (a_{12}a_{31}-a_{32}a_{11})(a_{13}a_{21}-a_{23}a_{11})\]which can be verified to be true by using bounding (positives and negatives) and the fact that $a_{23}a_{32}>a_{22}a_{33}$. We are done. $\blacksquare$

darij grinberg wrote: Now I know there is a solution on a few lines, alas using analysis: Let $ A$ be the matrix $ \left(a_{ij}\right)_{1\leq i\leq 3,\ 1\leq j\leq 3}$. Let $ K$ be a real which is greater than $ \max\left\{a_{11},a_{22},a_{33}\right\}$. Then, all entries of the matrix $ K\cdot I_3-A$ are strictly positive. Hence, after the Perron-Frobenius theorem, there exists a right eigenvector $ v$ of $ A$ such that all three components of $ v$ are strictly positive. This vector $ v$ then satisfies $ \left(K\cdot I_3-A\right)v=\mu v$, where $ \mu$ is the corresponding eigenvalue. This rewrites as $ Av=\left(K-\mu\right)v$. Hence, the three components of $ Av$ are proportional to those of $ v$, so they are either all negative, or all zero, or all positive. Now, if we write $ v$ in the form $ v=\left(\begin{array}{c} c_1\\ c_2\\ c_3 \end{array}\right)$, then $ Av=\left(\begin{array}{c} a_{11}c_{1}+a_{12}c_{2}+a_{13}c_{3} \\ a_{21}c_{1}+a_{22}c_{2}+a_{23}c_{3} \\ a_{31}c_{1}+a_{32}c_{2}+a_{33}c_{3} \end{array}\right)$, and we are done. This generalizes to $ n$-vectors. An analysis-free proof of this (replacing the use of Perron-Frobenius by some linear programming theory) can be found at https://mathoverflow.net/questions/299318/constructive-proof-of-a-rational-version-of-perron-frobenius .

Clearly we can assume that, $a_{11} = 2$, $a_{12} = -1$, $a_{13} = -1$ and $c_1 = 1$. Let, $R_i = a_{i1}c_{1}+a_{i2}c_{2}+a_{i3}c_{3}$ \begin{tabular}{ |c|c|c|c| } \hline 2 & -1 & -1 \\ \hline - & + & - \\ \hline - & - & + \\ \hline \end{tabular}Now, let's work with $c_2+ c_3 = 2$. Then $R_1 = 0$ and $R_2$ will be minimum and $R_3$ will be maximum for $c_2 \to 0$ on the other hand $R_3$ will be minimum for $c_3 \to 0$ Clearly both minimums of $R_2, R_3$ are negative. Now, if they don't reach $0$ then we can take any $c_2+ c_3 = 2$ and increase both them by $\epsilon > 0$ for small enough $\epsilon$ to get all of them negative. Now if they can reach $0$, WLOG let $R_2$ becomes $0$ for some $c_2+c_3 = 2$. If, $R_3 = 0$ then we are done. If it is negative then we will increase $c_3$ by $\epsilon > 0$ to get all negative. If it is positive then we will decrease $c_3$ by $\epsilon > 0$ to get all positive. $\blacksquare$

Note that this is equivalent to showing that the span of \[ \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix} \]in ${\mathbb R}^3$ over positive input vectors intersecting either the $(+, +, +)$ or $(-, -, -)$ quadrant. Let $A$, $B$, $C$ be the output vectors that the basis vectors are mapped too, which lie in the quadrants $(+, +, -)$, $(+, -, +)$, and $(-, +, +)$ in some order. If the span contains $(0, 0, 0)$, the result follows. As such, if $A$, $B$ and $C$ are linearly dependent, by the sign of the output vectors, it holds. If any of the lines $AB$, $BC$, or $CA$ cross through the $(+, +, +)$ quadrant the result follows. Else, it follows through considering projections that for each basis vector, either it or its additive inverse are in the span. As such, the span contains the entirety of one of the quadrants. The quadrant can't contain either $A$, $B$, $C$. It also can't contain their additive inverses by linear independence. Thus, the result follows.

Consider the vectors $\vec{a_1}=[a_{11},a_{12},a_{13}], \vec{a_2}=[a_{21},a_{22},a_{23}], \vec{a_3}=[a_{31},a_{32},a_{33}]$ and $\vec{c}=[c_1,c_2,c_3]$. Now, for any two vectors $\vec{c}$ and $\vec{a_i}$, $a_{i1}c_{1}+a_{i2}c_{2}+a_{i3}c_{3}$ is positive if and only if the angle between the vectors is acute, negative if and only if the angle is obtuse, and zero if and only if it is right. For each vector $\vec{a_i}$, draw the plane through the origin normal to the vector. Color the side containing the head of $\vec{a_i}$ blue and the other side red. Note that any point that is on all three planes, on all three red regions, or on all three blue regions satisfies the following: if we make $\vec{c}$ have this point as its head, then the angles are all acute, all obtuse, or all zero, as desired. Now, let's translate this onto the unit sphere. We project the entire space onto the surface of a unit sphere. Note that each plane is a great circle on this sphere, so for each $\vec{a_i}$, half of the sphere is colored red, and half colored blue. Note that all of $(+,-,-)$ is colored red by $\vec{a_1}$, $(-,+,-)$ is colored red by $\vec{a_2}$, and $(-,-,+)$ by $\vec{a_3}$. Clearly, our all-red region is a spherical triangle, and so it is connected, which means that since $(+,+,-)$, $(+,-,+)$, and $(-,+,+)$ all have blues, it must be a subset of the points with at least two negatives. If it were to be in two different octants, it must also be in the $(-,-,-)$ octant by connectedness. If it were only in one, say $(+,-,-)$, then there is a point in $(-,+,-)$, $A$, for which the distance from $A$ to any point in $(-,-,-)$ is longer than the distance from $A$ to any point in the all-red, clearly impossible. Thus, the all-red intersects with $(-,-,-)$. Since the all-blue is the antipode set of the all-red, it intersects with $(+,+,+)$ as desired.

oops? By scaling, we can assume $a_{ii}=1$ for $1\leq i \leq 3$ and $c_3=1$ Let $a_{i,j}$ for $i\neq j$ instead be positive, we negate the term in the respective expression. It remains to show there exist $c_1,c_2$ such that \[c_{1}-a_{12}c_{2}-a_{13},\qquad -a_{21}c_{1}+c_{2}-a_{23},\qquad -a_{31}c_{1}-a_{32}c_{2}+1\]are the same sign. We take two cases, one where they are all positive and one when they are all negative. If all are positive, then \begin{align*} c_1 > a_{12} c_2 + a_{13}\\ c_2 > a_{23} + a_{21}c_1 \\ 1> a_{31} c_1 + a_{32} c_2 \end{align*}Let $c_2 = a_{23} + a_{21}c_1 + \varepsilon$. Then the other two inequalities become \begin{align*} c_1 > a_{12} \cdot a_{23} + a_{12}a_{21} c_1 + a_{13} + \varepsilon\\ 1 > a_{31}c_1 + a_{23}a_{32} + a_{32}a_{21}c_1 + \varepsilon \end{align*}(we loosely use $\varepsilon$, it does not have a fixed value) If $a_{12}a_{21} \geq 1$ or $a_{23}a_{32}\geq 1$, it is easy to check the inequalities have no solutions. Otherwise, there are solutions when \[ \frac{a_{12}a_{23} +a_{13}}{1-a_{12}{21}} \leq \frac{1-a_{23}a_{32}}{a_{31}+a_{32}a_{21}}. \] Now repeat for the negative case. If $a_{12}a_{21} \geq 1$ or $a_{23}a_{32}\geq 1$, then making $c_1$ sufficiently large/small (depending on which one is true) suffices. Otherwise, it is easy to check there are solutions when \[ \frac{a_{12}a_{23} +a_{13}}{1-a_{12}{21}} \geq \frac{1-a_{23}a_{32}}{a_{31}+a_{32}a_{21}}. \] But one of these inequalities must be true, so we are done.

Letting $(a_{j1}, a_{j2}, a_{j3})$ by points for all $j$, we desire to show that there exists some point on the triangle formed by these points that lies in the space where $x,y,z$ all have the same sign. Consider the third point, say it has positive $x$ and $y$ coordinates but negative $z$ coordinates. Then consider the projection of this triangle to the $xy$ plane. The third point must lie in the first quadrant, then if this projection does not contain the origin it implies that part of the line through the other two points goes through the first quadrant, which easily finishes. Otherwise, we divide into cases as to whether the triangle is above the origin, below the origin, or lies on the origin. In the third case, we are obviously done. In the first case, there must be some point on the $z$ axis that intersects the triangle, then going epsilon upwards in both the $x,y$ directions and down in $z$ should still be in the triangle and it has all $3$ coordinates positive. The second case is analogous to the first case.