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?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.