Which non-negative matrices have negative eigenvalues?

For a real-valued and symmetric matrix $A$, then $A$ has negative eigenvalues if and only if it is not positive semi-definite. To check whether a matrix is positive-semi-definite you can use Sylvester's criterion which is very easy to check.

If your matrix is invertible and positive, then either it already has at least one negative eigenvalue, or you can get a matrix with a negative eigenvalue by exchanging two rows.

Proof:

If all eigenvalues are positive, then the determinant is positive. Exchanging two rows changes the sign of the determinant. Since the determinant is the product of the eigenvalues, a matrix with a negative determinant has at least one negative eigenvalue.