Why is an autocorrelation matrix always positive(semi)definite?

Question

Can someone help me understand why an auto-correlation matrix is always positive definite or positive semidefinite?

Can adding some value down the main diagonal convert it from a semi definite to a positive definite?

Answer 1

Hints. For the first one, you know that $C= E(x x^T)$ where $x$ is a random column vector. Hence, show that, for any vector $y\ne0$, $y^T C y$ is non-negative.

For the second, see that $y^T (C +\epsilon I) y = y^T C y + \epsilon y^T y $; because the second term is strictly positive (for $\epsilon>0$ and $y \ne 0$) this implies that $C +\epsilon I$ is stricly definite positive (if $C$ is at semi definite positive).