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

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?

• What is your definition of an autocorrelation matrix? How one shows the matrix is PSD depends on the definition we're starting from. – Omnomnomnom Nov 10 '14 at 19:03
• OK, I did not know there were many definitions. I am just learning this stuff. I am learning signal processing and would be defined like this: en.wikipedia.org/wiki/Autocorrelation_matrix – user1876942 Nov 10 '14 at 19:08
• Are you aware that a matrix of the form $xx^T$ (or $xx^H$ if we allow complex entries) is necessarily positive semidefinite? – Omnomnomnom Nov 10 '14 at 19:09
• I have read it and I am aware of that. I would like to know why that is true. Also, it would be good to turn a semidefinite to a positive definite so that I could use square root Cholesky. Otherwise I need to use pivoting, which is slower. – user1876942 Nov 10 '14 at 19:13

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).