Numerically verify a matrix is positive semidefinite

Question

I am trying to numerically (in Julia) verify that

A symmetric matrix $\mathbf{A}$ is positive semidefinite if and only if it is a covariance matrix.

Then I need to verify in both directions, i.e.

1. Given a positive semidefinite matrix $\mathbf{A}$, show that it is a covariance matrix.
2. Given a covariance matrix, show that it is positive semidefinite.

However, I am not sure

1. What properties should a matrix have to be a covariance matrix.
2. I know I could generate a covariance matrix using the following and I know that cov is positive semidefinite if and only if all of its eigenvalues are non-negative. But it turns out that minimum(eigvals(cov)) is a negative number close to 0 (on the order $\sim 10^{-15}$), I am not sure if I could conclude that cov is positive semidefinite since numerical reasons.

n = 100
u = randn(n);
cov = u * u'

Any input will be appreciated.

Answer 1

Maybe it's easier to verify that a covariance matrix is a Gram matrix (and vice versa) and to verify that a p.s.d. matrix is a Gram matrix (and vice versa). The numerical linear algebra step could then be the Cholesky decomposition.

But with any demonstration of this result on a computer whose computational model is some flavor of floating point arithmetic and not $\mathbb R$ arithmetic will suffer from roundoff error at some place or other.

Answer 2

The term "covariance matrix" comes from Probability Theory not from Linear Algebra. So, any positive semidefinite matrix can be assumed to be a covariance matrix of some distribution.

As for precision issue, having a minus eigenvalue in the order of 1e-15 is not problem because "double type" has a precision which is less than 15 digits. However, since matrices you are dealing with are positive semidefinite, i.e.: $$C = UU^T \Rightarrow x^TCx = \|U^Tx\|_2^2\geq 0 \quad \forall x$$ singular values will be equal to eigenvalues. Therefore you can use SVD which produces more stable and correct results.