# Condition for a vector to be positive linear combination of others

Let $$V$$ be a real vector space, and let be given $$v \in V$$ and $$v_1, v_2, \dots, v_n \in V$$($$n \geq 1$$). Is it true that the statements below are equivalent?

1. $$v$$ writes as a positive linear combination of $$v_1, v_2, \dots, v_n$$, that is, there are $$\alpha_1, \alpha_2, \dots, \alpha_n \geq 0$$ such that

$$v = \sum_{1 \leq k \leq n}\alpha_kv_k$$

1. Given any linear functional $$L: V \rightarrow \mathbb{R}$$, if $$L(v_k) \geq 0$$ for all $$1 \leq k \leq n$$, then $$L(v) \geq 0$$.

That 1) $$\implies$$ 2) is clear. But is the converse 2) $$\implies$$ 1) true? If not, is it true if we require $$V$$ to be finite dimensional?

• It certainly seems to hold in any inner-product space, whether finite-dimensional or not. – Ted Shifrin Jul 22 at 0:42
• Finite-dimensional shouldn't matter, I would think, since one could just replace $V$ with the span of $\{v,v_1,\dots,v_n\}$. – Greg Martin Jul 22 at 0:42
• Consider particular linear functionals. Think of simple ones. – Paulo Jul 22 at 0:45
• Yes. Its a matter of writing $v$ conveniently. – Paulo Jul 22 at 1:02
• @Paulo, yes, as you said, it is only a matter of writting $v$ conveniently; I have just figured out how to prove this theorem – Lucas Jul 22 at 1:29

Yes, the converse is true. First, note that we may as well assume $$V$$ is finite-dimensional: just let $$V_0$$ be the subspace of $$V$$ spanned by $$v_1,\dots,v_n$$ and $$v$$ and then it suffices to prove the converse for $$V_0$$ in place of $$V$$ since every functional on $$V_0$$ can be extended to a functional on $$V$$.

So, we may assume that $$V=\mathbb{R}^m$$ for some $$m$$, with standard basis $$e_1,\dots,e_m$$. We can now prove that (2) implies (1) by induction on $$m$$. The base cases $$m=0$$ and $$m=1$$ are trivial.

Now suppose $$m>1$$ the result is known for $$\mathbb{R}^{m-1}$$, and suppose we have vectors $$v_1,\dots,v_n\in\mathbb{R}^m$$ and a vector $$v\in\mathbb{R}^m$$ which is not a positive linear combination of $$v_1,\dots,v_n$$. We wish to find a linear functional $$L:\mathbb{R}^m\to\mathbb{R}$$ such that $$L(v)<0$$ and $$L(v_i)\geq 0$$ for each $$i$$.

We may assume without loss of generality that $$v$$ lies in the subspace $$\mathbb{R}^{m-1}$$ of $$\mathbb{R}^m$$ (i.e., the last coordinate of $$v$$ is $$0$$). We would now like to apply the induction hypothesis on that subspace. To do so, note first that there is a finite set $$S$$ of elements of $$\mathbb{R}^{m-1}$$ such an element of $$\mathbb{R}^{m-1}$$ is a positive linear combination of $$v_1,\dots,v_n$$ iff it is a positive linear combination of elements of $$S$$. Namely, let $$S$$ consist of all the $$v_i$$ which are in $$\mathbb{R}^{m-1}$$, together with, for each pair $$i,j$$ such that $$v_i$$ and $$v_j$$ have last coordinates with opposite sign, some positive linear combination of $$v_i$$ and $$v_j$$ that cancels out their last coordinates. (Exercise: show that any positive linear combination of the $$v_i$$ which is in $$\mathbb{R}^{m-1}$$ can actually be written as a positive linear combination of elements of $$S$$. In fact, the proof below does not even need this exercise, since we will only actually use this fact for positive multiples of elements of $$S$$ themselves.)

So, applying the induction hypothesis to $$v$$ and this finite set $$S$$, we obtain a functional $$L_0:\mathbb{R}^{m-1}\to\mathbb{R}$$ such that $$L_0(v)<0$$ and $$L_0(x)\geq 0$$ for all $$x\in\mathbb{R}^{m-1}$$ which are positive linear combinations of the $$v_i$$. We now wish to extend $$L_0$$ to a functional $$L$$ on all of $$\mathbb{R}^m$$ such that $$L(v_i)\geq 0$$ for all $$i$$. Defining such a linear extension just amounts to picking a value for $$L(e_m)$$.

Write $$v_i=w_i+a_ie_m$$ where $$w_i\in\mathbb{R}^{m-1}$$ (so $$a_i$$ is the last coordinate of $$v_i$$). Without loss of generality, we may assume that $$a_i>0$$ for some $$i$$ (if $$a_i=0$$ for all $$i$$ our conclusion is immediate since each $$v_i$$ is actually in $$\mathbb{R}^{m-1}$$, and if $$a_i<0$$ for some $$i$$ we can flip the signs of all the last coordinates). Let $$c$$ be the maximum value of $$-L_0(w_i)/a_i$$ where $$i$$ ranges over all values such that $$a_i>0$$. I claim that if we set $$L(e_m)=c$$, then $$L$$ will satisfy $$L(v_i)\geq 0$$ for all $$i$$.

For $$i$$ such that $$a_i>0$$, this is immediate from the definition, since we have $$L(v_i)=L_0(w_i)+a_ic$$ and $$c\geq -L_0(w_i)/a_i$$. For $$i$$ such that $$a_i=0$$ we have $$v_i=w_i\in\mathbb{R}^{m-1}$$ so we already know that $$L(v_i)=L_0(v_i)\geq 0$$ by our choice of $$L_0$$. Finally, suppose $$i$$ is such that $$a_i<0$$. By our choice of $$c$$, there is some $$j$$ such that $$a_j>0$$ and $$c=-L_0(w_j)/a_j$$. For this $$j$$, we have $$L(v_j)=L_0(w_j)+a_jc=0$$. Now consider the vector $$x=v_i-\frac{a_i}{a_j}v_j$$. This is a positive linear combination of $$v_i$$ and $$v_j$$, and the coefficients are chosen such that the last coordinate cancels out and $$x\in\mathbb{R}^{m-1}$$. By our choice of $$L_0$$, we have $$L(x)=L_0(x)\geq 0$$. But since $$L(v_j)=0$$, we also have $$L(v_i)=L(x)$$, and thus $$L(v_i)\geq 0$$.

(Partial answer to $$2) \implies 1)$$)

If $$v_1, v_2, \dots, v_n$$ are linearly independent, then $$(v_1, v_2, \dots, v_n)$$ can be completed to a basis $$\mathcal{B}=(v_i)_{i\in I}$$ of $$V$$ where $$\{1,2,\dots,n\}\subset I$$, then we can write every $$v \in V$$ uniquely as a linear combination of $$(v_i)_{i\in I}$$, $$v= \sum\limits_{i\in I}x_iv_i \ , \$$ where only finitely many $$x_i$$'s are nonzero.

Let $$P_i:V\rightarrow\mathbb{R}, \ P_i(x)=x_i$$

For all $$i \in \{1,2,\dots,n\}$$ and $$j \in I \setminus \{1,2,\dots,n\}$$, we have $$\pm P_j(v_i)=0 \$$ then $$\pm P_j(v) \geq0 \$$ i.e $$P_j(v)=x_j=0$$.

For all $$i \in \{1,2,\dots,n\}$$ and $$j \in\{1,2,\dots,n\}$$, we have $$P_j(v_i)=\delta_{ij} \geq0$$ then $$P_j(v)=x_j \geq0$$.