Is every correlation matrix positive semi-definite? I am generating correlation matrix by some new algorithm. Generated matrix is non positive semi-definite matrix.
I'm getting a few negative eigenvalues. The rest of eigenvalues are quite equal to the ideal matrix.
Can I use that non positive semi-definite matrix? If not, why?
If my estimated correlation matrix has all positive but complex value and imaginary terms are close to zero then is it possible? 
 A: A correlation matrix is really the covariance matrix of a bunch of variables which have been rescaled to have variance one.
But every population covariance matrix is positive semi-definite, and if we rule out weird cases (such as with missing data, or "numerical fuzz" turning a small eigenvalue to a negative one), so is every sample covariance matrix.
So if a matrix is supposed to be a correlation matrix, it should be positive semi-definite.
Note that the semi-definite is important here. In the bivariate case, take your two variables to be perfectly positively correlated and then the correlation matrix is $\pmatrix{1 & 1 \\ 1& 1}$ which has eigenvalues of $2$ and $0$: the zero eigenvalue means it is not positive definite.
A: Negative eigenvalues would imply that by the diagonalizing transformation the random vector would have negative variance in some components. Negative variances do never exist. 
A: A correlation matrix is positive semi-definite, period.  Numerics, however, might refuse to acknowledge that mathematical fact depending on how you arrive at the numeric representation of the correlation matrix.
The solution is to choose a representation of your matrix that cannot fail to be positive semi-definite by representing the matrix in a suitable decomposed form.  I am not up to scratch, but there are things like LUD decompositions or square root forms that essentially are unable to represent anything but truly positive semi-definite matrices and which you can usually update incrementally similarly to how you would update the full matrix, possibly even easier.
