How can we prove that If $A \in \mathbb{R}^{m\times n}$ is a full rank matrix and $m\ge n$, then $A^\top A$ is a positive definite matrix?

Question

I'm given the following problem: Consider the least mean squares problem: $$ \min_{x \in \mathbb{R}^n}\|Ax - b\|^2_2 $$ Suppose $A \in \mathbb{R}^{m\times n}$ is a full rank matrix and $m\ge n$. Find the closed-form solution of the least mean squares problem.

We are given the following Hint: If $A \in \mathbb{R}^{m\times n}$ is a full rank matrix and $m\ge n$, then $A^\top A$ is a positive definite matrix

We can then derive the following solution: $$ x = (A^\top A)^{-1}b^\top A $$

Here is my question: how can we prove the Hint? (If $A \in \mathbb{R}^{m\times n}$ is a full rank matrix and $m\ge n$, then $A^\top A$ is a positive definite matrix)

Answer 1

For any vector $v$ we have $v^\top (A^\top A) v = (Av)^\top (Av) = \|Av\|^2 \ge 0$. We then need to show that if $v \ne 0$, then this last inequality is strict, i.e. $\|Av\|^2 > 0$.

Suppose otherwise that $v \ne 0$ and $\|Av\| = 0$. Then $Av=0$, so the nullspace of $A$ contains a nonzero vector. By the rank-nullity theorem, the rank of $A$ is thus strictly less than $n$, so it cannot be full rank.

Answer 2

Hint

Using Singular Value Decomposition we obtain $$A=UDV$$therefore $$A^HA=V^HD^HDV$$which can very easily proved to be positive definite.