# Proving col rank = row rank

1. May 1, 2008

### e(ho0n3

[SOLVED] Proving col rank = row rank

The problem statement, all variables and given/known data
Demonstrate these four assertions to get an alternate proof that column rank equals row rank.

(a) $\vec{y}\cdot\vec{y} = \vec{0} \Leftrightarrow \vec{y} = \vec{0}$
(b) $A\vec{x} = \vec{0} \Leftrightarrow A^TA\vec{x} = \vec{0}$
(c) $\dim R(A) = \dim R(A^TA)$
(d) col rank A = col rank $A^T$ = row rank A

The attempt at a solution
I don't understand how assertions (a) through (c) are of any importance. The only one that needs demonstrating is (d).

(a) Trivial
(b) Given $A\vec{x} = \vec{0}$, $A^TA\vec{x} = A^T\vec{0} = \vec{0}$. Given $A^TA\vec{x} = \vec{0}$, suppose $A\vec{x} \ne \vec{0}$. Then $A^TA\vec{x} \ne A^T\vec{0} = \vec{0}$. Contradiction.
(c) No clue.
(d) I was thinking of using a "reduce to echelon form" proof, but that just defeats the purpose of this exercise.

2. May 1, 2008

### Dick

Using something along the line of the proof of (b), can you prove BAx=0 iff Ax=0? I hope not, because it's false. I don't think you've proved the 'only if' direction.

3. May 1, 2008

### e(ho0n3

Right. I screwed up. Given ATAx = 0 then either (i) x = 0, (ii) A is the zero matrix or (iii) A is not the zero matrix but ATA is.

(i) and (ii) both yield that Ax = 0. (iii) can't happen because if the the entry in the ith row, ith column of ATA is 0, then the ith row of A is 0 by (a). But this is not true for all i since A is not the zero matrix. Aha!

I'm assuming that (b) will be used to prove (c) and that (c) will be used to prove (d) now. Let me think...

Part (b) reminds me of nullspaces. It seems to me that both A and ATA yield the same nullspace. I know that the dimension of the nullspace plus the dimension of the rangespace equals the dimension of the domain. So if I show that both A and AT have the same domain, dimensionally, then (c) naturally follows.

But I can't think of any argument towards this.

4. May 1, 2008

### Dick

Umm. Still haven't quite got (b). Multiply x^(T) times A^(T)*A*x and think about (a).

5. May 1, 2008

### Vid

A is MxN
A^t is NxM
A^t*A is NxN

Use the theorem from the bottom of your post and c immediately follows.

6. May 1, 2008

Woah, not so fast. It's possible that $Ax=0$ without either $x=0$ or $A$ being the zero matrix. All that's required is that $A$ have a non-trivial nullspace, and $x$ lie in it. Same goes for $A^TA$.

7. May 1, 2008

### e(ho0n3

xTATAx = 0 since ATAx = 0. I don't understand how this relates to (a).

I don't see anything wrong with my previous argument. By letting x represent the ith column of A, then the ith row, ith column of ATA is xTx which is the dot product of x with itself. If xTx = 0, then by (a), x = 0.

8. May 1, 2008

### e(ho0n3

Sorry, I'm not following. I know that the dimensions of A place a limit on the dimension of A's rangespace but other than that...?

9. May 1, 2008

### e(ho0n3

You're right. Back to the drawing board.

10. May 1, 2008

### Dick

x^(T)*A^(T)*A*x is the same as (Ax).(Ax). You MAY be able to make your argument work. But it made me confused so I didn't pay a whole lot of attention to it. This is much easier.

11. May 1, 2008

### e(ho0n3

Wow, I didn't notice that. That is much easier. Now what about (c)? Are my previous thoughts in the right direction?

12. May 1, 2008

### Dick

(c) is pretty immediate from (b) isn't it. A^TA and A have the same domain. You've shown they have the same kernel. So? I'm a little vague on how that leads to (d), but I haven't been thinking about row and column rank much. Maybe it will be clearer to you.

13. May 1, 2008

### e(ho0n3

Sorry, I don't understand why they have the same domain. Is it because they have the same number of columns?

14. May 1, 2008

### Dick

If A and B are matrices, the domain of AB is the domain of B and the range (as codomain, the dimension of the space you are mapping into) of AB is the range of A. I don't understand why you don't understand? Or, if you want to think of it that way, yes, because they have the same number of columns.

Last edited: May 1, 2008
15. May 1, 2008

### e(ho0n3

I completely forgot that, because of the way linear maps are formed, the number of columns equals the dimension of the domain and the number of rows equals the dimension of the codomain. Sigh...

You wrote that the domain of AB is the domain of B. I disagree. AB represents the composition of two linear maps, say f and g. The domain of f(g(x)) is the codomain of g, i.e. the codomain of B.

Concerning (d), I know that rank ATA ≤ min{rank A, rank AT}. Hmm...this doesn't seem to help.

16. May 2, 2008

### e(ho0n3

I've forgotten a simple fact that I just reread today:

dim R(A) = col rank A

Applying this to ATA, and using (c) yields

col rank A = col rank ATA

Now all I need to do is show that col rank ATA = col rank AT somehow. Hmm...

17. May 8, 2008

### e(ho0n3

I just read the solution to this problem. I was on the right track in my last post:

col rank A = col rank ATA ≤ col rank AT ≤ col rank (AT)T = col rank A so col rank A = col rank AT.

I don't know why col rank AT ≤ col rank (AT)T is true though. I'll have to meditate on this a bit.

18. May 8, 2008

### e(ho0n3

I guess it makes sense because if for any matrix B, col rank B > col rank BT, then I could substitute B with BT and conclude that col rank BT > (BT)T = col rank B which is a contradiction.

19. May 8, 2008

### Dick

That's not really a proof. If you are talking about ALL matrices it isn't true that f(B)<=f(BT) and f(B)>f(BT) are the only two options. Which way the inequality goes might depend on the matrix B. On the other hand, once they get to: col rank A = col rank ATA ≤ col rank AT, then you are done. Because now you can interchange A and AT, as you suggest.

20. May 8, 2008

### e(ho0n3

You're right. I understand clearly now. Thanks.