OK folks.
So, lets say we have a matrix A. The inverse of $A^TA$ exists iff the columns of A are linearly independent.
Then, we want to prove this by considering that the product $A^TA$ is positive definite, since, apparently, if $A^TA$ is positive definite and invertible, the columns are linearly independent.
I hope I explained this well. Otherwise, would appreciate somebody can provide some insight and intuition of what is going on.
Thank you all.
It is clear that $A^TA$ is symmetric. Let's prove that $A^TA$ is positive definite iff the columns are linearly independent.
Suppose that $A^TA$ is positive definite, then for all $x \neq 0$, we have $x^TA^TAx > 0$. Note that by definition we have $$\|Ax\|^2 = x^TA^TAx > 0$$ implying that $Ax \neq 0$, but $Ax$ is exactly a linear combination of the columns of $A$ (write down the multiplication to see this). Hence we find that $Ax \neq 0$ for all $x \neq 0$.
Let $x \neq 0$ and suppose the columns of $A$ are linearly independent. Then $Ax \neq 0$ (once again because of the fact that $Ax$ is exactly a linear combination of the columns of $A$). Since $Ax \neq 0$, we have $x^TA^TAx = \|Ax\|^2 > 0$, so $A^TA$ is positive definite.
This proves that $A^TA$ is positive definite iff the columns of $A$ are linearly independent.