How to verify non-negativity of a density matrix? A density matrix, $\rho$ must be Hermitian, normalized ($Tr[\rho]=1$) and non negative. Non negativity means that it should have non negative eigenvalues. Given a density matrix, first two conditions are straightforward to check. But, how to verify the non negativity of a density matrix without explicitly calculating the eigenvalues? The eigenvalue calculation can be very difficult for an arbitrary dimensional density matrix. 
 A: A non-negative (aka. semi-positive) operator$^{1}$ $\rho:H\to H$ satisfies by definition
$$ \forall v\in H: \langle v, \rho v \rangle ~\geq~ 0. \tag{1}$$
For a complex Hilbert space, an operator $\rho$ is semi-positive iff 
$$ \exists B: ~~ \rho~=~B^{\dagger} B, \tag{2}$$
and iff
$$\rho \text{ is diagonalizable in an orthonormal basis with non-negative eigenvalues.} \tag{3} $$
The characterizations (1) & (2) are often simpler to use than determining the spectrum/eigenvalues (3).

$^{1}$We will ignore subtleties with unbounded operators, domains, selfadjoint extensions, etc., in this answer.
A: On a computer, (and probably also on paper for a matrix with no partiuclar structure), the fastest solution is computing a Cholesky factorization and seeing if the procedure fails. This in the end is a special case of the criterion in QMechanic's answer, since you are constructing a factorization $\rho = BB^\dagger$. (You may replace it with a LDL^T factorization to avoid the square roots.)
In some cases if the matrix has a special structure it may be easier to compute determinants and check Sylvester's criterion, as suggested by AccidentalFourierTransform.
