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

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

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

$\{C\}_{ij} = E\left\{(\mathbf{x}[i] - \bar{\mathbf{x}}[i])^\text{T}(\mathbf{y}[j] - \bar{\mathbf{y}}[j])\right\}; \,\,\,\,\,\,\,\,\,\,\,\, 1 \leq i,j \leq M $

Where, $E\{\}$ is the "expected value" operator.

What is the proof that, for all arbitrary values of $\mathbf{x}$ and $\mathbf{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)?

  • 3
    $\begingroup$ Positive semidefinite is not the same as "not negative definite", although you might say "nonnegative definite". $\endgroup$ Feb 27 '12 at 19:43
  • $\begingroup$ @RobertIsrael Oh, you are right. It is my mistake. $\endgroup$ 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).

  • 1
    $\begingroup$ Writing $C = E (X X^T)$ implies $X$ is a zero mean random vector? $\endgroup$
    – ironX
    Feb 15 '20 at 0:50
  • $\begingroup$ @ironX One can think of $X$ as $Y-E(Y)$, then $E(XX^T)$ will give the covariance matrix for the random vector $Y$ $\endgroup$ Mar 23 '20 at 13:27

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.

  • $\begingroup$ Interesting... Did you compare your approach to (a part of) an answer posted one year earlier? $\endgroup$
    – Did
    Apr 24 '14 at 6:19
  • 13
    $\begingroup$ Rereading this answer five years later, I realize it is actually completely wrong, confusing random variables with real numbers. Nice upvotes though... $\endgroup$
    – Did
    Nov 24 '18 at 19:51
  • $\begingroup$ @Did: Completely agree with you. No idea why this answer is even allowed here. $\endgroup$ Feb 15 '19 at 9:25
  • $\begingroup$ @Did what do you mean, what's the matter here ? reading that second answer made me understand that the whole proof of the first answer lies upon the fact that there is a number that is squared thus non negative. What's wrong with that second answer? $\endgroup$ Apr 16 '20 at 15:39
  • 1
    $\begingroup$ @MarineGalantin The incorrectness lies in that hkBattousai mixes the the stochastic variable "s" with the variance "sigma", that is, he treats them as they were equals. (That's at least how I understood it, I might be wrong.) $\endgroup$
    – aaa
    May 29 '20 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.