Let $A \otimes B$ be the algebraic tensor of two $C^{\ast}$ algebras, and an element x in $A\otimes B$ is positive if $x=yy^{\ast}$. Then is it always possible to write x in the form $x=\sum a_i\otimes b_i$, where $a_i$ and $b_i$ are positive elements?
I think the answer is no. The matrix $$ a=\begin{bmatrix} 1&0&0&1\\ 0&0&0&0\\ 0&0&0&0\\ 1&0&0&1 \end{bmatrix} $$ is positive in $M_4(\mathbb{C})$. When we see this algebra as $M_2(\mathbb{C})\otimes M_2(\mathbb{C})$, it cannot be obtained as a sum of elementary tensors with positive entries. . (ok, several hours later, here is the argument) First, $a$ is positive because it is selfadjoint and $a=\left(\frac1{\sqrt2}a\right)^2$. Now, if we have a sum of elementary tensors in $M_2(\mathbb{C})\otimes M_2(\mathbb{C})$, it will look like $$ \sum_j\begin{bmatrix} \alpha_j&\overline{\gamma_j}\\ \gamma_j&\beta_j\end{bmatrix} \otimes \begin{bmatrix}\alpha'_j&\overline{\gamma_j'}\\ \gamma_j'&\beta_j'\end{bmatrix} =\begin{bmatrix} \sum_j\alpha_j'\alpha_j& \sum_j \alpha_j'\overline{\gamma_j}& \sum_j\overline{\gamma_j'}\alpha_j&\sum_j\overline{\gamma_j'}\gamma_j\\ \sum_j\alpha_j'\gamma_j& \sum_j \alpha_j'\beta_j&*&*\\ *&*&*&*\\ *&*&*&* \end{bmatrix} $$ The assumption that each elementary tensor is made of the tensor of two positive matrices translates into $\alpha_j\geq0$, $\beta_j\geq0$, and $\alpha_j\beta_j\geq\gamma_j^2$ for all $j$ (and the "prime'' version too). Now if the matrix on the right is going to be our $a$ above, then the 2,2 entry forces the following: for each $j$, the product $\alpha_j'\beta_j=0$. If $\alpha_j'=0$, then $\gamma_j'=0$; and if $\beta_j=0$, then $\gamma_j=0$. That is, for each $j$, $\overline{\gamma_j'}\gamma_j=0$, and this forces the 1,4 entry to be $0$; but it is not zero in $a$. 


Further question: is the answer (to the original question) yes if we ask that all matrices are not only positive, but invertible? 


It is nearly yes as you need to use linear combinations rather then sums. If $y=\sum_i e_i \otimes b_i$ then $x=yy^* =\sum_{i,j} e_ie_j^* \otimes b_ib_j^*$. This leaves you with two types of summands whose positivity is clear: (1) $e_ie_i^*\otimes b_ib_i^*$ (2) $e_ie_j^* \otimes b_ib_j^* + e_je_i^* \otimes b_jb_i^*$ whose positivity is clear by the elementary calculation that boils down to multilinearization of $(\alpha e_i+\beta e_j)(\alpha e_i+\beta e_j)^* \otimes (\gamma b_i+\delta b_j)(\gamma b_i+\delta b_j)^*$. (Just write the second summand as a linear combination of these guys.) Clearly, you need to use subtractions to clear up the summands of type (2). 

