What is the best way to check whether a map $\Phi$ is positive, i.e., $$\Phi\left(x\right) \geq 0 \iff x \geq 0?$$
Is there a way to describe the modification of the eigenvalues of matrix argument $x$ by the map, in order to check whether they remain non-negative?
Also, a completely positive map in Kraus' decomposition $$\Phi\left(x\right) = \sum_i M_i x M_i^\dagger$$ must be positive, but how can this be demonstrated?
The question of how to check whether a map $\Phi$ is positive is an area of active research. One sufficient set of criteria is given in the paper Doherty, Parillo, Spedalieri A Complete Family of Separability Criteria (in particular, the paper discusses the equivalent problem of detecting an element of the dual cone).
If $\Phi:\mathcal M_m \to \mathcal M_n$ where $m=2$ and $n = 3$ or $n = 3$ and $m=2$, then it is known that $\Phi$ is positive if and only if it is decomposable. That is, we must be able to write $\Phi = \Phi_1 + \Phi_2$ where $x \mapsto \Phi_1(x)$ and $x \mapsto \Phi_2(x^T)$ are completely positive ($x^T$ denotes the transpose of $x$).
If $\Phi$ has a Kraus representation, then we note that for any $y \in \Bbb C^n$, we have $$ y^\dagger(\Phi(x))y = y^\dagger \left(\sum_{i} M_i x M_i^\dagger \right)y = \sum_{i}(M_i^\dagger y)^\dagger x(M_i^\dagger y) \geq 0 $$ It follows that $\Phi$ is a positive map.