Another question on ranks (linear algebra).

[MathematicalPhysicist]

i need to prove that for A square matrix: rank AA^t=rank A.
well rank AA^t<=rank A, but how do i show that rankAA^t>=rankA, i mean i need to show if x is a solution of AA^tx=0 then x is a solution of Ax=0 or of A^tx=0, but how?

 

[Mindscrape]

You are trying to show that the transpose of an nxn multiplied by itself has the same or less rank? I would use the definition of matrix multiplication, and then transpose, and do Gauss elimination (probably on a 2x2). There may be a more subtle way, but the forceful approach should work.

 

[radou]

i need to prove that for A square matrix: rank AA^t=rank A.
well rank AA^t<=rank A, but how do i show that rankAA^t>=rankA, i mean i need to show if x is a solution of AA^tx=0 then x is a solution of Ax=0 or of A^tx=0, but how?

Let U = {x : AA^t x = 0}, and V = {x : A^t x = 0}. Assume you have already shown that dim V <= dim U (which implies r(A) >= r(AA^t) ), and now assume dim U > dim V (which would imply r(A) > r(AA^t) ) and find a counterexample (it's simple). When you have shown that dim U > dim V can't hold, then dim U = dim V must hold, and hence r(A^t) = r(A) = r(AA^t). Hope this works.

 

[MathematicalPhysicist]

i don't think this would work, cause in ad absurdum proofs you need to get a logical contradiction, not a counter example, perhaps I am wrong here and you are right, but i don't think so.

 

[radou]

i don't think this would work, cause in ad absurdum proofs you need to get a logical contradiction, not a counter example, perhaps I am wrong here and you are right, but i don't think so.

Actually, that's what's bothering me, too. If we assume it holds for any matrix, could a 'proof by counterexample' work? Guess some of the PF mathematicians should take over on this one.

 

[AlephZero]

You can show this directly from the singular value decomposition of A.

Let the SVD of A be U.D.V^T where D is the diagonal matrix of singular values. Write the SVD of A.A^T in terms of U D and V, and show that A and A.A^T have the same number of zero singular values, hence the same rank.

There is a similar proof involving eigenvalues and eigenvectors.

There is probably a similar but more "elementary" proof involving choosing a set of basis vectors where a subset of the basis vectors spans the null space of A - but I haven't thought idea that right through.