Why does correlation matrix need to be positive semi-definite and what does it mean to be or not to be positive semi-definite?

Question

I have been researching the meaning of positive semi-definite property of correlation or covariance matrices.

I am looking for any information on

• Definition of positive semi-definiteness;
• Its important properties, practical implications;
• The consequence of having negative determinant, impact on multivariate analysis or simulation results etc.

Answer 1

The variance of a weighted sum $\sum_i a_i X_i$ of random variables must be nonnegative for all choices of real numbers $a_i$. Since the variance can be expressed as $$\operatorname{var}\left(\sum_i a_i X_i\right) = \sum_i \sum_j a_ia_j \operatorname{cov}(X_i,X_j) = \sum_i \sum_j a_ia_j \Sigma_{i,j},$$ we have that the covariance matrix $\Sigma = [\Sigma_{i,j}]$ must be positive semidefinite (which is sometimes called nonnegative definite). Recall that a matrix $C$ is called positive semidefinite if and only if $$\sum_i \sum_j a_ia_j C_{i,j} \geq 0 \;\; \forall a_i, a_j \in \mathbb R.$$

Answer 2

The answer is quite simple.

The correlation matrix is defined thus:

Let $X = [x_1, x_2, ..., x_n]$ be the $m\times n$ data matrix: $m$ observations, $n$ variables.

Define $X_b= [\frac{(x_1-\mu_1 e)}{s_1}, \frac{(x_2-\mu_2 e)}{s_2}, \frac{(x_3-\mu_3 e)}{s_3}, ...]$ as the matrix of normalized data, with $\mu_1$ being mean for the variable 1, $\mu_2$ the mean for variable 2, etc., and $s_1$ the standard deviation of variable 1, etc., and $e$ is a vector of all 1s.

The correlation matrix is then

$$C=X_b' X_b$$

divided by $m-1$.

A matrix $A$ is positive semi-definite if there is no vector $z$ such that $z' A z <0$.

Suppose $C$ is not positive definite. Then there exists a vector w such that $w' C w<0$.

However $(w' C w)=(w' X_b' X_b w)=(X_b w)'(X_b w) = {z_1^2+z_2^2...}$, where $z=X_b w$, and thus $w' C w$ is a sum of squares and therefore cannot be less than zero.

So not only the correlation matrix but any matrix $U$ which can be written in the form $V' V$ is positive semi-definite.

Answer 3

(Possible looseness in reasoning would be mine. I'm not a mathematician: this is a depiction, not proof, and is from my numeric experimenting, not from books.)

1. A positive semidefinite (psd) matrix, also called Gramian matrix, is a matrix with no negative eigenvalues. Matrix with negative eigenvalues is not positive semidefinite, or non-Gramian. Both of these can be definite (no zero eigenvalues) or singular (with at least one zero eigenvalue). [Word "Gramian" is used in several different meanings in math, so perhaps should be avoided.]
2. In statistics, we usually apply these terms to a SSCP-type matrix, also called scalar product matrix. Correlation or covariance matrices are particular cases of such matrix.
3. Any scalar product matrix is a summary characteristic of some multivariate data (a cloud). For example, given $n$ cases X $p$ variables data, we could compute $p$X$p$ covariance matrix between the variables or $n$X$n$ covariance matrix between the cases. When you compute it from real data, the matrix will always be Gramian. You may get non-Gramian (non-psd) matrix if (1) it is similarity matrix measured directly (i.e. not computed from the data) or the similarity measure isn't SSCP-type; (2) the matrix values was incorrectly entered; (3) the matrix is in fact Gramian but is (or so close to be) singular that sometimes the spectral method of computing eigenvalues produces tiny negative ones in place of true zero or tiny positive ones.
4. An alternative and equivalent summary for the cloud is the matrix of euclidean distances. A scalar product (such as covariance) between a pair of items and the corresponding squared euclidean distance between them are tied by the law of cosines (cosine theorem, look at the picture there): $d_{12}^2 = h_1^2+h_2^2-2s_{12}$, where the $s$ is the scalar product and the $h$'s are the distances of the two items from the origin. In case of covariance matrix between variables $X$ and $Y$ this formula looks as $d_{xy}^2 = \sigma_x^2+\sigma_y^2-2cov_{xy}$.
5. As interim conclusion: a covariance (or correlation or other scalar product) matrix between some $m$ items is a configuration of points embedded in Euclidean space, so euclidean distances are defined between all these $m$ points.
6. Now, if [point 5] holds exactly, then the configuration of points is truly euclidean configuration which entails that the scalar product matrix at hand (e.g. the covariance one) is Gramian. Otherwise it is non-Gramian. Thus, to say "$m$X$m$ covariance matrix is positively semi-definite" is to say "the $m$ points plus the origin fit in Euclidean space perfectly".
7. What are possible causes or versions of non-Gramian (non-Euclidean) configuration? The answers follow upon contemplating [point 4].
   • Cause 1. Evil is among the points themselves: $m$X$m$ distance matrix isn't fully euclidean. Some of the pairwise distances $d$ are such that they cannot agree with the rest of the points in Euclidean space. See Fig1.
   • Cause 2. There is general (matrix-level) mismatch between $h$'s and $d$'s. For example, with fixed $d$'s and some $h$'s given, the other $h$'s must only vary within some bounds in order to stay in consent with Euclidean space. See Fig2.
   • Cause 3. There is localized (pair-level) mismatch between a $d$ and the pair of corresponding $h$'s connected to those two points. Namely, the rule of triangular inequality is violated; that rule demands $h_1+h_2 \ge d_{12} \ge |h_1-h_2|$. See Fig3.
8. To diagnose the cause, convert the non-Gramian covariance matrix into distance matrix using the above law of cosines. Do double-centering on it. If the resultant matrix has negative eigenvalues, cause 1 is present. Else if any $|cov_{ij}| \gt \sigma_i \sigma_j$, cause 3 is present. Else cause 2 is present. Sometimes more than one cause get along in one matrix.

Fig1.

Fig2.

Fig3.