# What is the proof that covariance matrices are always semi-definite?

Suppose that we have two different discreet signal vectors of $N^{th}$ dimension, namely $\textbf{x}[i]$ and $\textbf{y}[i]$, each one having a total of $M$ set of samples/vectors.

$\textbf{x}[m] = [x_{m,1} \,\,\,\,\, x_{m,2} \,\,\,\,\, x_{m,3} \,\,\,\,\, ... \,\,\,\,\, x_{m,N}]^T; \,\,\,\,\,\,\, 1 \leq m \leq M$
$\textbf{y}[m] = [y_{m,1} \,\,\,\,\, y_{m,2} \,\,\,\,\, y_{m,3} \,\,\,\,\, ... \,\,\,\,\, y_{m,N}]^T; \,\,\,\,\,\,\,\,\, 1 \leq m \leq M$

And, I build up a covariance matrix in-between these signals.

$\{C\}_{ij} = E\{(x[i] - \bar{x}[i])^T(y[j] - \bar{y}[j])\}; \,\,\,\,\,\,\,\,\,\,\,\, 1 \leq i,j \leq M \\ \mbox{Where, "E{}" is the "expected value" operator.}$

What is the proof that, for all arbitrary values of $\textbf{x}$ and $\textbf{y}$ vector sets, the covariance matrix $C$ is always semi-definite ($C \succeq0$) (i.e.; not negative definte; all of its eigenvalues are non-negative)?

-
Positive semidefinite is not the same as "not negative definite", although you might say "nonnegative definite". –  Robert Israel Feb 27 '12 at 19:43
@RobertIsrael Oh, you are right. It is my mistake. –  hkBattousai Feb 27 '12 at 20:18

A symmetric matrix $C$ of size $n\times n$ is semi-definite if and only if $u^tCu\geqslant0$ for every $n\times1$ (column) vector $u$, where $u^t$ is the $1\times n$ transposed (line) vector. If $C$ is a covariance matrix in the sense that $C=\mathrm E(XX^t)$ for some $n\times 1$ random vector $X$, then the linearity of the expectation yields that $u^tCu=\mathrm E(Z_u^2)$, where $Z_u=u^tX$ is a real valued random variable, in particular $u^tCu\geqslant0$ for every $u$.
If $C=\mathrm E(XY^t)$ for two centered random vectors $X$ and $Y$, then $u^tCu=\mathrm E(Z_uT_u)$ where $Z_u=u^tX$ and $T_u=u^tY$ are two real valued centered random variables. Thus, there is no reason to expect that $u^tCu\geqslant0$ for every $u$ (and, indeed, $Y=-X$ provides a counterexample).
Covariance matrix C is calculated by the formula, $$\mathbf{C} \triangleq E\{(\mathbf{x}-\bar{\mathbf{x}})(\mathbf{x}-\bar{\mathbf{x}})^T\}.$$ For an arbitrary real vector u, we can write, $$\begin{array}{rcl} \mathbf{u}^T\mathbf{C}\mathbf{u} & = & \mathbf{u}^TE\{(\mathbf{x}-\bar{\mathbf{x}})(\mathbf{x}-\bar{\mathbf{x}})^T\}\mathbf{u} \\ & = & E\{\mathbf{u}^T(\mathbf{x}-\bar{\mathbf{x}})(\mathbf{x}-\bar{\mathbf{x}})^T\mathbf{u}\} \\ & = & E\{s^2\} \\ & = & \sigma_s^2. \\ \end{array}$$ Where $\sigma_s$ is the variance of the zero-mean scalar random variable $s$, and it is a scalar real number whose value equals to, $$\sigma_s = \mathbf{u}^T(\mathbf{x}-\bar{\mathbf{x}}) = (\mathbf{x}-\bar{\mathbf{x}})^T\mathbf{u}.$$ Square of any real number is equal to or greater than zero. That is, $$\sigma_s^2 \ge 0.$$ Thus, $$\mathbf{u}^T\mathbf{C}\mathbf{u} = \sigma_s^2 \ge 0.$$ Which implies that covariance matrix of any real random vector is always semi-definite.