Proving Equal Rank: A Shortcut to Demonstrating Column and Row Rank Equality

  • Thread starter e(ho0n3
  • Start date
  • Tags
    rank Row
In summary, the conversation discusses proving that column rank equals row rank using four assertions. The first three assertions are not important and the focus is on the fourth assertion. The conversation explores the use of a "reduce to echelon form" proof, but it is noted that this defeats the purpose of the exercise. Instead, the focus shifts to using the theorem that states the dimension of the nullspace plus the dimension of the rangespace equals the dimension of the domain. This leads to the conclusion that the dimension of the nullspace of A is the same as the dimension of the nullspace of A^T. Finally, the conversation concludes by discussing the relationship between the column rank of ATA and the column rank of AT, with the realization that they
  • #1
e(ho0n3
1,357
0
[SOLVED] Proving col rank = row rank

Homework Statement
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.
 
Physics news on Phys.org
  • #2
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
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
Umm. Still haven't quite got (b). Multiply x^(T) times A^(T)*A*x and think about (a).
 
  • #5
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
e(ho0n3 said:
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 [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].
 
  • #7
Dick said:
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.
 
  • #8
Vid said:
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...?
 
  • #9
quadraphonics said:
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].

You're right. Back to the drawing board.
 
  • #10
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
Dick said:
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?
 
  • #12
(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
Dick said:
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?
 
  • #14
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:
  • #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.
 
  • #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...
 
  • #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.
 
  • #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.
 
  • #19
e(ho0n3 said:
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.
 
  • #20
You're right. I understand clearly now. Thanks.
 

1. What is the difference between column rank and row rank?

Column rank refers to the maximum number of linearly independent columns in a matrix, while row rank refers to the maximum number of linearly independent rows in a matrix. In other words, column rank is the number of columns that can be used to span the column space of a matrix, while row rank is the number of rows that can be used to span the row space of a matrix.

2. Why is it important to prove that column rank equals row rank?

Proving that column rank equals row rank is important because it is a fundamental result in linear algebra that has many applications. It is used to determine the dimension of a vector space, to find the basis of a vector space, and to solve systems of linear equations. It also helps in understanding the properties of matrices and their transformations.

3. How can we prove that column rank equals row rank?

There are several ways to prove that column rank equals row rank. One method is to use Gaussian elimination to reduce the matrix to its reduced row echelon form. The number of non-zero rows in the reduced form will be the row rank, and the number of leading ones in the reduced form will be the column rank. Since the operations of Gaussian elimination do not change the row or column space of a matrix, the row rank and column rank will be equal.

4. Can column rank equal row rank in every matrix?

Yes, column rank can equal row rank in every matrix. This is because the number of linearly independent rows and columns in a matrix is always the same. However, the row and column rank may be different for rectangular matrices (matrices with different number of rows and columns).

5. What does it mean if column rank does not equal row rank in a matrix?

If column rank does not equal row rank in a matrix, it means that the matrix is not full rank. This indicates that there are linearly dependent rows or columns in the matrix, and the matrix does not span its entire row or column space. This can happen in rectangular matrices or in square matrices with repeated rows or columns.

Similar threads

  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Advanced Physics Homework Help
Replies
3
Views
287
  • Calculus and Beyond Homework Help
Replies
13
Views
1K
  • Special and General Relativity
Replies
1
Views
512
  • Introductory Physics Homework Help
Replies
25
Views
208
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
896
  • Introductory Physics Homework Help
Replies
1
Views
808
  • Differential Equations
Replies
2
Views
2K
Back
Top