I need to prove that $A^T$$A$ is an invertible matrix.
$$ A= \begin{bmatrix} \vec{a_1} & \vec{a_2} & \ldots & \vec{a_n} \\ \end{bmatrix} $$
Can I prove this using a vector $\vec{y}$ and numbers $k_1$, $k_2$, $\ldots$, $k_n$
$A^T$$A$$\vec{y}$ = $k_1$$\vec{a_1}$ + $k_2$$\vec{a_2}$ + $\ldots$ + $k_n$$\vec{a_n}$
i.e. can I get a linear combination from $A$'s columns?
$A$ $=$ $M$x$N$ , $M$ $>$ $N$, and $A$ is not a $zero$ matrix.
Your conditions with respect to the matrix $A$ are a little bit too vague to post a proper answer, but that might help. I will show, that a matrix $A^TA$ is invertible if and only if it $A$ has a trivial kernel, i.e if
$$ Ax = \vec{0}\Rightarrow x = \vec{0},\ x\in R^n. $$
Classical proof
Suppose $A^TAx$ is $\vec{0}$, then $$\vec{0} = A^TAx \Rightarrow 0 = x^TA^TAx = (Ax)^T(Ax) = \|Ax\|^2 \Rightarrow Ax = \vec{0}$$
On the contrary, if $Ax = \vec{0}$, it holds that $A^TAx = A^T\vec{0} = 0$.
Proof using columns
To show the same result using columns, denote the columns as you did in the question with $a_1,...,a_n$. The following orthogonality can be shown.
$$ A^TAx = [a_1|a_2|...|a_n]^TAx = 0\Rightarrow Ax\perp a_i,\ i= 1,...,n $$ Now, since the orthogonal space of $Ax$ is a linear space, we have that $$ Ax \perp \text{span}\{a_i,i=1,...,n\}. $$ Since $\text{span}\{a_i,i=1,...,n\}$ is exactly the image set of $A$ (if we regard it as a map). $$ Ax\in \text{span}\{a_i,i=1,...,n\}. $$ We can conclude $Ax=\vec{0}$. The contrary can be shown as above.