View Full Version : [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.
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.
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.
Umm. Still haven't quite got (b). Multiply x^(T) times A^(T)*A*x and think about (a).
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.
quadraphonics
May1-08, 04:34 PM
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.
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.
Umm. Still haven't quite got (b). Multiply x^(T) times A^(T)*A*x and think about (a).
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.
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.
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...?
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.
You're right. Back to the drawing board.
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.
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.
Wow, I didn't notice that. That is much easier. Now what about (c)? Are my previous thoughts in the right direction?
(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.
A^TA and A have the same domain.
Sorry, I don't understand why they have the same domain. Is it because they have the same number of columns?
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.
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.
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...
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.
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.
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.
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.
You're right. I understand clearly now. Thanks.
vBulletin® v3.8.7, Copyright ©2000-2012, vBulletin Solutions, Inc.