Why is the inverse matrix of $A^TA$ is guaranteed to exists? For a matrix $A$ of an arbitrary size $n{\times}m$ where $n>m$ and $rank\left(A\right)=m$, there is no guarantee that the inverse matrix $A^{-1}$ will exist. But for the multiplication of the matrix with its transpose $A^T{\cdot}A$ the inverse $\left(A^T{\cdot}A\right)^{-1}$ is guaranteed to exist.
Why is it so?
 A: Edit: After adding the rank condition, see this post: Prove rank $A^TA$ = rank $A$ for any $A_{m \times n}$
If you can prove that $\text{rank}( A^T A) = \text{rank}(A) = m$, you get that $A^T A$, being an $m \times m$ matrix now, has full rank and hence is invertible.
Here is a counter example for the quadratic case:
There, it is not guaranteed to exist. Consider the matrix
$$
A = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix},
$$
which is obviously not invertible. Then 
$$
A^T A = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}
$$
is also not invertible.
In fact, using the determinant formulas 
$$
\det A^T = \det A
$$
and
$$
\det AB = \det A \det B
$$
you get that
$$
\det A^T A = \det A^T \det A = (\det A)^2
$$
and this is not equal to zero if and only if $\det A \neq 0$, i.e. $A$ is invertible.
A: If $A$ is $n\times m$ and $n>m$, then the rank of $A$ cannot be $n$, because the rank is at most $\min(n,m)$.
The result is true if the rank of $A$ is $m$ (number of columns), because the rank of $A^TA$ is the same as the rank of $A$.
Actually you can say that $A$ has rank $m$ (number of columns) if and only if $A^TA$ is invertible.
Proof. Denote by $C(A)$ the column space and by $N(A)$ the null space of $A$. The rank-nullity theorem says that $m=\dim C(A)+\dim N(A)$. It is also easy to prove that $N(A)=N(A^TA)$. Therefore $\dim N(A^TA)=0$ (which is equivalent to $A^TA$ being invertible) if and only if $\dim C(A)=m$, that is, $A$ has rank $m$. QED
Dually, $A$ has rank $n$ (number of rows) if and only if $AA^T$ is invertible.
A: It is guaranteed only if the columns of A are Linearly Independent so in that case, the null space of A has only the Zero vector. 
Suppose $$X\in N(A^tA)\Rightarrow A^tAX=0 \Rightarrow <X,A^tAX>=0$$
$$X^tA^tAX=0\Rightarrow(AX)^tAX=0\Rightarrow\Vert AX\Vert^2=0$$
$$AX=0$$ as the columns of A are Linearly Independent $X=0$. 
We conclude that the null space of the square matrix $$A^tA$$ is  $$N(A^tA)=\{0\} \Rightarrow \text{the matrix is invertible(since it is square}$$
