I think this proof has some flaws. Linear Independence Let A be an $m \times n$ matrix such that $A^t A$ is invertible. Show that the columns of A are linear independent.
Proof
Assume that $A^t A$ is invertible and the columns of A denoted by $a_1,\dots,a_n$ are linear dependent and there exists scalrs $x_1,x_2,\ldots,x_n$, not all are zero such that
$$x_1a_1 + x_2a_2 + \cdots + x_n a_n=0.$$
In matrix form we have $Ax = 0$
$$\begin{align*}
Ax &= 0\\
A^t Ax &= A^t 0 = 0\\
(A^t A)^{-1} (A^t A)x &= (A^t A)^{-1} 0 = 0\\
x &= 0
\end{align*}$$
But this is a contradiction, hence the columns of A must be linearly independent.
Question
Doesn't make sense to me, we showed that all the scalars $x$ are 0s, but then we have
$$0a_1 + 0a_2 + \cdots + 0a_n = 0$$
How do know that the columns are not 0? The columns are technically "free" and it would make the columns linearly dependent.
 A: The columns are not "free" to be anything; they must be such that $A^tA$ is invertible after all.
If $a_i$ (the $i$th column of $A$) were the zero vector, then the $i$th column of $A^tA$ would also be the zero vector, which would ensure $\det(A^tA)=0$ and thus that $A^tA$ was not invertible, a contradiction.
A: You showed that the hypothesis $x_1a_1 + x_2a_2 + \cdots + x_n a_n=0$ implies $x_1=x_2=\cdots=x_n=0$ and this is precisely the property that by definition says that the columns $a_1,\ldots,a_n$ are linearly independent.
The converse statement, that $x_1=x_2=\cdots=x_n=0$ implies $x_1a_1 + x_2a_2 + \cdots + x_n a_n=0$, in other words that $0a_1 + 0a_2 + ... + 0a_n = 0$, is irrelevant to the question. In fact this converse statement is absolutely uninteresting, since it always holds, whether $a_1,\ldots,a_n$ are linearly dependent or not.
A: Here's an alternative way:
If $A^TA$ is invertible, then here exists a matrix $M$ such that $M(A^TA)=I$; hence, $(MA^T)A = I$.
Viewing the matrices as linear transformations, we have that $A$ is left invertible, hence $A$ must be one-to-one. Thus, the nullspace of $A$ is trivial. Therefore, the columns of $A$ must be linearly independent. 
Note that this generalizes easily (as does your own argument) to the following:

If $A$ is an $m\times n$ matrix for which there exists a matrix $B$ with $BA$ invertible, then the columns of $A$ are linearly independent.

In other words, there was nothing special about using $A^T$. 
