I am trying to go in this direction only. Is this proof correct? ($A$ is an $m \times n$ matrix).
I am considering the contrapositive of the statement:
Suppose $A^TA$ is singular. Then $\det (A^TA) =0$. $\det(A^TA) = \det(A^T) \det(A)$ and since $\det (A^T) = \det(A)$, we must have $det(A) = 0$. In other words, the columns of $A$ are linearly dependent. $\blacksquare$