Cfrgtkky

Let $u_i, i= 1,cdots,p$ and $v_j, j= 1,cdots,s$ be finitely many vectors in $mathbb{R}^n$. Show that

$$
text{conv}(u_1,u_2,cdots,u_p)+text{conv}(v_1,v_2,cdots,v_s)=text{conv}{u_i+v_j mid i= 1,cdots,p, ,, j= 1,cdots,s}
$$

We need to show

$$
x+y in text{conv}{u_i+v_j mid i= 1,cdots,p, ,, j= 1,cdots,s}
$$

where $x in text{conv}(u_1,u_2,cdots,u_p)$ and $y in text{conv}(v_1,v_2,cdots,v_s)$. Also, we need to show

$$
z in text{conv}(u_1,u_2,cdots,u_p)+text{conv}(v_1,v_2,cdots,v_s)
$$

where $z in text{conv}{u_i+v_j mid i= 1,cdots,p, ,, j= 1,cdots,s}$.

I have tried the following for the first one:

Let $x in text{conv}(u_1,u_2,cdots,u_p)$ so $x=sum_{i=1}^plambda_iu_i$ where $sum_{i=1}^plambda_i=1$. Also, Let $y in text{conv}(v_1,v_2,cdots,v_s)$ so $x=sum_{j=1}^smu_jv_j$ where $sum_{j=1}^smu_j=1$.

Summing them

$$x+y=lambda_1u_1+lambda_2u_2+cdots+lambda_pu_p+mu_1v_1+mu_2v_2+cdots+mu_sv_s.$$

Now the question is how we can get something in the form of $text{conv}{u_i+v_j mid i= 1,cdots,p, ,, j= 1,cdots,s}$?

We can use the match-up procedure as follows. Set $$lambda_i^0:=lambda_itext{ for each }i=1,2,ldots,p,,$$ $$mu_j^0:=mu_jtext{ for each }j=1,2,ldots,s,,$$ and $$z_0:=x+y,.$$ Suppose that we have $$z_k=sum_{i=1}^p,lambda_i^k,u_i+sum_{j=1}^s,mu_j^k,v_j$$ for some nonnegative integer $k$ and for some $lambda_i^k,mu_j^kin[0,1]$ such that $$s_k:=sum_{i=1}^p,lambda_i^k=sum_{j=1}^s,mu_j^k,.$$

If $s_k=0$, then the process terminates at this point. If $s_k>0$, then we take $i_k:=min{i,|,lambda^k_ineq 0}$ and $j_k:=min{j,|,mu^k_jneq 0}$. Now define $w_k:=u_{i_k}+v_{j_k}$. Let $nu_k:=min{lambda_{i_k},mu_{j_k}}$. Then, set
$$lambda_i^{k+1}:=left{begin{array}{ll}lambda_i^k&text{if }ineq i_k,,\ lambda_i^k-nu_k&text{if }i=i_k,,end{array}right}text{ for every }i=1,2,ldots,p,,$$
$$mu_j^{k+1}:=left{begin{array}{ll}mu_j^k&text{if }jneq j_k,,\ mu_j^k-nu_k&text{if }j=j_k,,end{array}right}text{ for every } j=1,2,ldots,s,,$$
and $$z_{k+1}:=z_k-nu_k,w_k,.$$

Note that this algorithm cannot prolong indefinitely, since the number of nonzero coefficients amongst $lambda_1,lambda_2,ldots,lambda_p,mu_1,mu_2,ldots,mu_s$ decreases each step. When the loop is over (say, in $l+1$ steps, namely, with $s_1,s_2,ldots,s_l>0$ and $s_{l+1}=0$), we can see that $$x+y=sum_{k=1}^l ,nu_k,w_k,,$$
where $nu_kin[0,1]$ for each $k=1,2,ldots,l$ with $sumlimits_{k=1}^l,nu_k=1$, and each $w_k$ is of the form $u_i+v_j$ for some $i=1,2,ldots,p$ and $j=1,2,ldots,s$. (It is obvious that $lleq p+s$, by the way.) This proves that
$$begin{align}text{conv}left{u_1,u_2,ldots,u_pright}&+text{conv}left{v_1,v_2,ldots,v_sright}\&subseteq text{conv}big{u_i+v_j,big|,i=1,2,ldots,p text{and} j=1,2,ldots,sbig},.end{align}$$

To prove the reversed inclusion, it is actually easier. Let $$ain text{conv}big{u_i+v_j,big|,i=1,2,ldots,ptext{ and }j=1,2,ldots,sbig},.$$ Then, there exist $alpha_{i,j}in[0,1]$ for $i=1,2,ldots,p$ and $j=1,2,ldots,s$ such that
$$sum_{i=1}^p,sum_{j=1}^s,alpha_{i,j}=1text{ and }a=sum_{i=1}^p,sum_{j=1}^s,alpha_{i,j},left(u_i+v_jright),.$$

By taking $beta_i:=sumlimits_{j=1}^s,alpha_{i,j}$ for each $i=1,2,ldots,p$ and $gamma_j:=sumlimits_{i=1}^p,alpha_{i,j}$ for every $j=1,2,ldots,s$, we see that $beta_iin[0,1]$ for each $i=1,2,ldots,p$, $gamma_jin[0,1]$ for every $j=1,2,ldots,s$, $sumlimits_{i=1}^p,beta_i=1$, and $sumlimits_{j=1}^s,gamma_j=1$. Thus, $a=b+c$, where
$$b:=sum_{i=1}^p,beta_i,u_iin text{conv}left{u_1,u_2,ldots,u_pright}$$
and
$$c:=sum_{j=1}^s,gamma_j,v_jintext{conv}left{v_1,v_2,ldots,v_sright},.$$
Hence,
$$begin{align}text{conv}big{u_i+v_j,big|,i=1,2,ldots,p &text{and} j=1,2,ldots,sbig}\&subseteq text{conv}left{u_1,u_2,ldots,u_pright}+text{conv}left{v_1,v_2,ldots,v_sright},,end{align}$$
as desired.