# Rank theorem of linear algebra

Let $U$ be an orthogonal matrix consisting of eigenvectors of $AA^{T}$, and $V$ be an orthogonal matrix consisting of eigenvectors of $A^{T}A$. Here $A$ is an $m\times n$ matrix which has rank $r$.

I want to show that $\operatorname{rank}(AA^{T})=\operatorname{rank}(A^{T}A)$. It says that since $\dim(N(AA^{T}))=m-r$, we can find independent $u_1,\ldots,u_m$ from $N(AA^{T})$ such that $U=[u_1 \ldots u_m]$ is orthogonal.

But I can't understand why $\dim(N(AA^{T}))=m-r$ guarantees there exist $m$ independent column vectors and that the matrix $U$ is orthogonal.
I studied rank theorem before but a little confused in here.

-

Probably there is some mistake in the question. There can't be, in any case, $m$ independent columns in the matrix $AA^T$. Because, its rank is $r$ which means there should be only $r$ independent columns. But, the first $r$ columns of $U$ (which you have defined) will be a basis for the columns for $AA^T$ and rest of the $m-r$ columns will be a basis for $N(AA^T)$.

Let $B_1=AA^T$. Now according to rank-nullity theorem, $rank(B_1)+nullity(B_1)=number~of~columns~in~B_1$. Number of columns in $B_1$ is $m$. Rank of $B_1$ is $r$ (rank of A), so from that equation above, $nullity(B_1)=m-r$.

-
Yes, exactly. The proof's result is what you say above. I'm just wondering how can we say that the matrix U is orthogonal from that result. – thistime Dec 1 '12 at 14:12
It doesn't say it's columns are orthogonal. It just says that there is a orthogonal basis for the columns of $AA^T$. The thing is that the eigenvectors of $AA^T$ (which is $U$ as you defined) will form a orthogonal matrix. The last $m-r$ columns will give a orthogonal basis for $N(AA^T)$. – dineshdileep Dec 1 '12 at 14:28
Please question if you don't get it. By the way, are you familiar with SVD? Because then, explaining all this is very easy. – dineshdileep Dec 1 '12 at 14:30
Actually, it's a part of SVD. But, in SVD, matrix U is an orthogonal matrix and I can't get the meaning of "It doesn't say it's columns are orthogonal". Since U is an orthogonal matrix I think all of its columns should be orthogonal... – thistime Dec 1 '12 at 15:14
What I meant is there can't be $m$ independent columns as you have stated in your question. There will only be $r\leq m$ independent columns. $U$ will be a orthogonal matrix and its last $m-r$ columns will be a basis for its null space – dineshdileep Dec 1 '12 at 17:09

another way to approach:

assume $A\in M_{m\times n}(\mathbb{R})$, $\operatorname{rank}(A)=r$

step 1: $$\operatorname{rank}(AA^T)=\operatorname{rank}(A)$$

obviously, $\operatorname{rank}(AA^T)\leq\operatorname{rank}(A)$

for $\operatorname{rank}(A)=r$,so we can find a subdeterminant $\begin{vmatrix} a_{i_1j_1} &\cdots & a_{i_1j_r}\\ \cdots &\cdots & \cdots\\ a_{i_rj_1} &\cdots &a_{i_rj_r} \end{vmatrix}\not=0$

by Binet-Cauchy Formula: $$AA^T\bigl(\begin{smallmatrix} i_1 &i_2 &\cdots &i_r \\ i_1 & i_2 &\cdots &i_r \end{smallmatrix}\bigr)=\sum_{1\leq v_1<v_2<\cdots<v_r\leq n}A\bigl(\begin{smallmatrix} i_1 &i_2 &\cdots &i_r \\ v_1 & v_2 &\cdots &v_r \end{smallmatrix}\bigr)A^T\bigl(\begin{smallmatrix} v_1 &v_2 &\cdots &v_r \\ i_1 & i_2 &\cdots &i_r \end{smallmatrix}\bigr)=\sum_{1\leq v_1<v_2<\cdots<v_r\leq n}\left[A\bigl(\begin{smallmatrix} i_1 &i_2 &\cdots &i_r \\ v_1 & v_2 &\cdots &v_r \end{smallmatrix}\bigr)\right]^2>0$$

because at least one term of the above sum $\not=0$,we have found above.the subdeterminant of $A$ of order $r$.

so we have proved $\operatorname{rank}(AA^T) \geq r=\operatorname{rank}(A)$

then we get the conclusion: $\operatorname{rank}(AA^T)=\operatorname{rank}(A)$

step 2:

$$\operatorname{rank}(AA^T)=\operatorname{rank}(A)=\operatorname{rank}(A^T)=\operatorname{rank}(A^TA)$$

-