Why is $\mathbf\Phi^{\top}\mathbf\Phi$ a positive definite matrix?

Question

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

Answer 1

Note we have $$ v^\top \left(\Phi^\top\Phi\right) v = \left(v^\top \Phi^\top\right) \left(\Phi v\right) = \left(\Phi v \right)^\top \left(\Phi v\right) = \|\Phi v \|_2^2 \geq 0 $$ for all $\Phi \in \mathbb{R}^{N \times M}, v \in \mathbb{R}^M; M, N \in \mathbb{N}_{>0}$. This establishes the general positive-semidefiniteness of $\Phi^\top\Phi$.
Moreover, $$ \|\Phi v \|_2^2 = 0 \iff \|\Phi v \|_2 = 0 \iff \Phi v \ = 0_{\mathbb{R}^N}, $$ which means that $\Phi^\top\Phi$ and hence $\beta\Phi^\top\Phi$ (with $\beta \in \mathbb{R_{>0}}$) is positive-definite if (and only if) the columns of $\Phi$ are linearly independent.

Answer 2

Observation $1.$ A symmetric matrix $\mathbf A^\mathsf T\mathbf A$ is positive semi-definite.

Note that

$$\mathbf v^\mathsf T\mathbf A^\mathsf T\mathbf A\mathbf v= (\mathbf A\mathbf v)^\mathsf T\cdot ( \mathbf A\mathbf v)\geq 0.\tag 1$$

Also, $\mathbf A\mathbf v=\mathbf 0$ implies $\mathbf A^\mathsf T\mathbf A$ being positive definite when $\mathcal N(\mathbf A) =\{\mathbf 0\}$, i.e., when $\mathbf A$ has linearly independent columns.