Let $A_{n\times n}$ be a real matrix. Is it true that $I+A^TA$ is invertible?

Let $M = I+A^tA$. Take $v$ in the kernel of $M$. Now,

$$ 0 = [I+A^tA]v, $$

and so we get $A^tAv = -v$. Right multiplying by $v^t$ once again, we have $v^tA^tAv = -v^tv$ and so $$ 0 \leq \|Av\|^2 = (Av)^t(Av) = v^tA^tAv = -v^tv = -\|v\|^2 \leq 0 $$

which proves that $v = 0$. Thus, $M$ is injective and since it is square, it is invertible.

If $I+A^TA$ is not invertible, then there exists a non-null vector $v$ such that:

$$(I+A^TA)v = 0.$$

This means that:

$$(I+A^TA)v = 0 \Rightarrow v + A^TAv = 0 \Rightarrow A^TAv = -v.$$

In other words, $v$ is an eigenvector of $A^TA$ with eigenvalue $\lambda = -1$.

Since $A^TA$ is by definition semidefinite positive, then there is no negative eigenvalue. That is, it is impossible that $I+A^TA$ is not invertible.

If $I + A^TA$ only has positive eigenvalues, then $I + A^TA$ is invertible.

We just need to show that $A^TA$ only has non-negative eigenvalues, which is the same as saying that $A^TA$ is positive semi-definite. $A^TA$ is of such type if

$$x^TA^TAx \geq 0\ \forall x$$

notice that $Ax$ is a vector and $x^TA^TAx = (Ax)^TAx = (Ax, Ax) = ||Ax||^2\geq 0$

hence $A^TA$ is positive semi-definite. Now assume $\lambda$ is an eigenvalue for $A^TA$ and $A^TAv = \lambda v$ for some $v$, then

$$(I + A^TA)v = Iv + A^TAv = v + \lambda v = (1 + \lambda)v$$

hence the eigenvalues of $I + A^TA$ are the same as the ones for $A^TA$ but shifted one unit. Hence, only if $A^TA$ had $-1$ as eigenvalue the matrix $I +A^TA$ wouldn't be invertible. But $-1$ cannot be an eigenvalue of $A^TA$, hence we have proved that $I + A^TA$ is invertible.