I had this question when reading section 3.5.3 on page 170 of "Pattern Recognition and Machine Learning" written by Christopher M. Bishop:
Here $\mathbf\Phi$ represents the design matrix and $\beta$ is precision which is positive.
My question is: why is $\mathbf\Phi^\top\mathbf\Phi$ a positive definite matrix?
I tried to prove it by showing that the error function defined in equation (3.80) of the same book has a local minimum at $\mathbf m_N$. But I don't have the luck (I can prove $\nabla E$ is zero at $\mathbf m_N$, but I cannot show further that $\mathbf m_N$ is necessarily a local minimum) and, even if it is the case, I cannot establish positive definiteness of $\mathbf\Phi^\top\mathbf\Phi$ from that of $\mathbf A$. So, can you please help me prove that $\mathbf\Phi^\top\mathbf\Phi$ is positive definite? Thanks a lot.
Edit: The columns of the design matrix $\mathbf\Phi$ are linearly independent almost surely, because the elements of this matrix are (functions of) random variables. This condition is essential in excluding positive semi-definiteness. As an aside, it is usually assumed that the number of samples $N$ is larger than the number of basis functions $M$.