Return to Revisions

It suffices to show that the $\mathbb{Q}$-span of the $a_i$'s has a $\mathbb{Q}$-basis where each $a_i$ has nonnegative coordinates. Assume that $a_1,\dotsc,a_n$ is a counterexample to this statement, with $n$ minimal. Then $n\geq 2$, and $$a_n=\sum_{i=1}^{n-1}q_ia_i$$ for some $q_i\in\mathbb{Q}$. Without loss of generality, the positive $q_i$'s precede the negative $q_i$'s, and the negative $q_i$'s precede the vanishing $q_i$'s. Moreover, without loss of generality, each non-vanishing $q_i$ is $\pm 1$. Hence we can assume that we have a relation of shape $$a_n=a_1+\dotsb+a_\ell-a_{\ell+1}-\dotsb-a_m$$ with some $1\leq\ell\leq m\leq n-1$. In particular, $a_{\ell+1}+\dotsb+a_m<a_1+\dotsb+a_\ell$. Using this inequality, it is straightforward to construct positive rational coefficients $q_{i,j}$ for $1\leq i\leq\ell$ and $\ell+1\leq j\leq m$ such that $$b_i:=a_i-\sum_{j=\ell+1}^m q_{i,j}a_j>0\qquad\text{and}\qquad \sum_{i=1}^\ell q_{i,j}=1.$$ This construction can be made recursively, first finding the $q_{i,j}$'s for $j=\ell+1$, then finding them for $j=\ell+2$, etc. Now our relation for $a_n$ becomes $$a_n=b_1+\dotsb+b_\ell,$$ where the $b_i$'s are positive numbers. Observe that each of $a_1,\dotsc,a_n$ is a nonnegative rational linear combination of the $n-1$ positive numbers $b_1,\dotsb,b_\ell,a_{\ell+1},\dotsb,a_{n-1}$. By the minimality of $n$, these $n-1$ numbers satisfy the initial requirement, hence $a_1,\dotsc,a_n$ satisfy the initial requirement as well. Contradiction.