$A^TA$ need not be invertible. If columns of a matrix A are linearly independent, then $A^TA$ is invertible.
Let's say $A^TA$ isn't invertible:
Gauss-Markov seems to hinge on $A^TA$ being invertible. Suppose that A is $mxn$ real matrix. If $m<n$, then the inverse of $A^TA$ does not exist.
But you can minimize the sum of squared differences, regardless (use some iterative algorithm). The proof for Gauss-Markov that I know won't work anymore. (BLUE: best linear unbiased estimator, OLS: ordinary least squares). In this situation I could see having multiple solutions. And for any of these solutions, are they the OLS? Are they BLUE? Why, if Gauss-Markov doesn't work anymore.
Gauss-Markov: https://en.wikipedia.org/wiki/Gauss%E2%80%93Markov_theorem Convexity of Linear Regression: Convexity of linear regression