If $A^TA$ is invertible, then $A$ has linearly independent column vectors

For each $i$, let $A_i$ be the $i$th column of $A$. Let $A_1 x_1 + \cdots + A_n x_n = 0$ be a linear dependence relation. Then $Ax = 0$, where $x$ is the column vector $(x_1\cdots x_n)^T$. So $A^TAx = 0$. Invertibility of $A^T A$ implies $x = 0$. Thus $x_1 = \cdots = x_n = 0$, showing that $\{A_1,\ldots, A_n\}$ is linearly independent, as desired.

We have a theorem: $rank(AB) \leq min(rank(A),rank(B))$

In our case, we have $rank(A^TA) \leq min(rank(A^T),rank(A))$

Since row rank is equal to column rank, we can infer that $rank(A^T)=rank(A)$, and so $rank(A^TA) \leq rank(A)$.

But we also know that $A^TA$ is invertible, so it has full rank, so $rank(A^TA)=n$.

So we have $rank(A) \geq n$. but $A$ only has $n$ columns, so the rank can't possibly be more than $n$, overall we have $rank(A)=n$. so $A$ has $n$ independent column (and row) vectors.