1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving col rank = row rank

  1. May 1, 2008 #1
    [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) [itex]\vec{y}\cdot\vec{y} = \vec{0} \Leftrightarrow \vec{y} = \vec{0}[/itex]
    (b) [itex]A\vec{x} = \vec{0} \Leftrightarrow A^TA\vec{x} = \vec{0}[/itex]
    (c) [itex]\dim R(A) = \dim R(A^TA)[/itex]
    (d) col rank A = col rank [itex]A^T[/itex] = 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 [itex]A\vec{x} = \vec{0}[/itex], [itex]A^TA\vec{x} = A^T\vec{0} = \vec{0}[/itex]. Given [itex]A^TA\vec{x} = \vec{0}[/itex], suppose [itex]A\vec{x} \ne \vec{0}[/itex]. Then [itex]A^TA\vec{x} \ne A^T\vec{0} = \vec{0}[/itex]. 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. jcsd
  3. May 1, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. May 1, 2008 #3
    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.
     
  5. May 1, 2008 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Umm. Still haven't quite got (b). Multiply x^(T) times A^(T)*A*x and think about (a).
     
  6. May 1, 2008 #5

    Vid

    User Avatar

    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.
     
  7. May 1, 2008 #6
    Woah, not so fast. It's possible that [itex]Ax=0[/itex] without either [itex]x=0[/itex] or [itex]A[/itex] being the zero matrix. All that's required is that [itex]A[/itex] have a non-trivial nullspace, and [itex]x[/itex] lie in it. Same goes for [itex]A^TA[/itex].
     
  8. May 1, 2008 #7
    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.
     
  9. May 1, 2008 #8
    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...?
     
  10. May 1, 2008 #9
    You're right. Back to the drawing board.
     
  11. May 1, 2008 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  12. May 1, 2008 #11
    Wow, I didn't notice that. That is much easier. Now what about (c)? Are my previous thoughts in the right direction?
     
  13. May 1, 2008 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    (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.
     
  14. May 1, 2008 #13
    Sorry, I don't understand why they have the same domain. Is it because they have the same number of columns?
     
  15. May 1, 2008 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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
  16. May 1, 2008 #15
    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.
     
  17. May 2, 2008 #16
    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...
     
  18. May 8, 2008 #17
    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.
     
  19. May 8, 2008 #18
    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.
     
  20. May 8, 2008 #19

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  21. May 8, 2008 #20
    You're right. I understand clearly now. Thanks.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?