Prove that $A^*A + I$ is invertible

Let $A$ be an $m\times n$ matrix. Prove that $A^*A + I$ is invertible.

I'm not sure what to do because everything I try ends up at $A^*A$ again and not $AA^*$.

• Hint: What would $A^{\ast} A + I$ being not invertible imply about the eigenvalues of $A^{\ast}A$? – Christopher A. Wong Apr 17 '13 at 2:21

Suppose $I+A^*A$ is not invertible, then there is some nonzero vector $x$ such that $$0=(I+A^*A)x = x+A^*Ax.$$ This implies $$0=x^*0 = x^*x+x^*A^*Ax = \|x\|^2+\|Ax\|^2\geq\|x\|^2,$$ which contradicts our assumption that $x\neq 0$. Thus $I+A^*A$ is invertible.
Let $B:=A^*A+I$. Using the Euclidean inner product $$(x,y)=x^*y=\sum_{j=1}^n\overline{x_j}y_j$$ of $\mathbb{C}^n$ or $\mathbb{R}^n$, depending on your assumptions, we get $$(x,Bx)=(x,x)+(x,A^*Ax)=(x,x)+(Ax,Ax)=\|x\|^2+\|Ax\|^2\geq \|x\|^2.$$ Therefore, if $Bx=0$, it follows that $\|x\|=0$, i.e. $x=0$.
So $B$ is a square matrix and $\mbox{Ker} B=\{0\}$, i.e. it is injective.
By the rank-nullity theorem, it follows that $B$ is invertible.