Relationship: Rank of a matrix $\leftrightarrow$ # of eigenvalues

Can someone tell, why the number of the nonzero eigenvalues (counted according to their algebraic multiplicities) of a matrix of type $A^{*}A$, where $A$ is an arbitrary real or complexvalued matrix, is equal to the rank of $A$ ? Here, in step 2, it seems to me that exactly this assertion is made, and I can't quite understand it.

I get, that if $$\text{rank}\left(A^{*}A\right)=r$$

then $$\ker\left(A^{*}A\right)=n-r,$$ if it happens that $A^{*}A$ is an $n\times n$ matrix. But how can I conclude from this, that the multiplicity of the $0$ eigenvalue is $n-r$, i.e. that there are $n-r$ that are mapped to $0$ (couldn't it by that only linear combination of $n-r$ eigenvectors are mapped to $0$, since the kernel doesn't have to necessarily be spanned by the eigenvectors themselves, as far as I know) ?

-
@rschwieb of course; typo... – user19822 Jun 17 '12 at 13:52

The matrix $A^*A$ is self-adjoint, hence every eigenvalue is real and the matrix is diagonalizable. That means that the algebraic and geometric multiplicities of every eigenvalue agree. In particular, the nullity of $A^*A$ equals the algebraic multiplicity of the eigenvalue $0$; since the sum of the algebraic multiplicities of all eigenvalues must equal $n$ (since the characteristic polynomial of $A^*A$ must split, as all eigenvalues are real) it follows that the rank of $A^*A$ equals the sum of the algebraic multiplicities of the nonzero eigenvalues.

Now, all that remains is to show that the rank of $A^*A$ equals the rank of $A$. Since the nullspace of $A$ is contained in the nullspace of $A^*A$, we have that $\mathrm{nullity}(A)\leq\mathrm{nullity}(A^*A)$. On the other hand, if $\mathbf{v}\notin \mathrm{nullspace}(A)$, then $$0\lt \langle A\mathbf{v},A\mathbf{v}\rangle = \langle A^*A\mathbf{v},\mathbf{v}\rangle$$ so $A^*A\mathbf{v}\neq\mathbf{0}$. Thus, $\mathrm{nullspace}(A^*A)=\mathrm{nullspace}(A)$, which gives $\mathrm{nullity}(A^*A)=\mathrm{nullity}(A)$.

Since $A$ and $A^*A$ have the same number of columns, it follows as well that $\mathrm{rank}(A^*A) = \mathrm{rank}(A)$.

-
This shows that the number of nonzero eigenvalues is equal to the rank of $A^{\ast} A$, but it doesn't show that this is equal to the rank of $A$. To show this, observe that $A^{\ast} Av = 0 \Rightarrow \langle v, A^{\ast} Av \rangle = 0 \Rightarrow \langle Av, Av \rangle = 0 \Rightarrow Av = 0$, so the two operators have the same nullspace. – Qiaochu Yuan Jun 16 '12 at 22:16
@Qiaochu: Thanks for pointing it out (I failed to notice it); was adding that bit when you edited the comment. – Arturo Magidin Jun 16 '12 at 22:26

I have a hint, which I hope is not beyond your current coursework.

Did you notice $A^*A$ is a Hermitian matrix? It would be diagonalizable then...

-
Strange... Arturo answered 23 minutes ago? It didn't show on my screen and I only got the new answer alert less than a minute ago :/ – rschwieb Jun 16 '12 at 22:31
Because I had deleted the answer pending fixing it (it was missing the second part). When you undelete, the original posting time is displayed, not the time in which you undeleted. – Arturo Magidin Jun 16 '12 at 23:28
@ArturoMagidin OK! No gremlins involved then... – rschwieb Jun 16 '12 at 23:40

Consider the singular value decomposition $A=U \Sigma V^*$. If you multiply it out in this form you immediately get an eigenvalue decomposition, $A^*A=V \Sigma^2 V^*$.

So, the nonzero squared singular values of $A$ are exactly the eigenvalues of $A^*A$, with the eigenvectors being the corresponding columns of $V$. The number of nonzero singular values of $A$ is of course the rank of $A$.

Edit: If you are not familiar with the singular value decomposition, the intuition behind it is as follows. Any matrix $A$ maps the unit sphere to an ellipsoid. In the singular value decomposition, the columns of $V$ are the orthonormal vectors on the sphere that get mapped to the axes of the ellipsoid, the columns of $U$ are the orthonormal axes of the ellipsoid, and the singular values (entries in the diagonal matrix $\Sigma$) are the scaling lengths of the ellipsoid's axes. If $A$ is rank-deficient, that means the ellipsoid is completely flattened in some directions, which is to say some of the singular values are zero.

-
The goal here is exactly to prove that the number of nonzero singular values of $A$ is the rank of $A$. – Qiaochu Yuan Jun 16 '12 at 23:12
@Nick: Unfortunately, the write-up that the OP directs to is in fact establishing the singular value decomposition, so that this line of argument would be circular in that context. – Arturo Magidin Jun 16 '12 at 23:30
Hmm didn't read the linked page when I wrote the answer. One could, of course, construct the singular values as the constrained maxima of $v^*Au$ over successively smaller subspaces - then the reasoning would not be circular. – Nick Alger Jun 16 '12 at 23:43