Prove that $I + A^{T}A$ is invertible

Question

I'm completely stuck with this seemingly simple problem. I'm trying to prove that matrix $I + A^TA$ is invertible, where $A \in \mathbb{R^{m \times n}}$. The book where this is from hasn't yet introduced determinants or eigenvalues or other such "fancier" results so I should do without those. I've tried to prove that $rank(A) = n$ or that $(I + A^TA)x=0 \implies x=0$, but none of my approaches seem to lead to any breakthroughs. Any hints?

Edit: Based on the replies from Will Jagy and Martin Argerami I was able to see the solution (without the use of eigenvalues). So, here's my formulation for the solution (I think):

Suppose that $(I + A^TA)x=0$ where $x$ is a nonzero vector. Then, we also have $x^T(I + A^TA)x=0$.

Because $x^T(I + A^TA)x=x^TIx+x^T(A^TA)x=x^Tx+(Ax)^TAx$
and $x^Tx=\sum_{k = 1}^{n} x^2_k>0$ (for $x \ne 0$)
and $(Ax)^TAx=\sum_{h=1}^n (\sum_{k=1}^n a_{hk}x_k)^2 \ge 0$,
then we have $x^T(I + A^TA)x=x^Tx+(Ax)^TAx>0$ which is a contradiction.

Thus, $x$ cannot be a nonzero vector and $(I + A^TA)x=0 \implies x=0$ which means that $I + A^TA$ is invertible.

Answer 1

Let us first look at the eigenvalues of $A^TA$. If $A^TAx=\lambda x$ for nonzero $x$, then $$ \lambda\,x^Tx=x^TA^TAx=(Ax)^TAx\geq0. $$ As $x^Tx>0$, this shows that $\lambda\geq0$.

If now $(I+A^TA)x=\lambda x$ for nonzero $x$, we can rewrite this as $A^TAx=(\lambda-1)x$. By the above, $\lambda-1\geq0$, that is $\lambda\geq1$. In particular, $0$ is not an eigenvalue of $I+A^TA$, which is thus invertible.

Answer 2

Since $A^TA$ is positive semidefinite, all its eigenvalues are non-negative and all the eigenvalues of $I_n+A^TA$ are $\geq 1$.