Another matrix rank proof (1 Viewer)

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

radou

Homework Helper
3,085
6
Let A and B me matrices such that the product AB is defined. One has to proove that r(AB) <= r(A) and r(AB) <= r(B).

My first thoughts are: let A be 'mxn' and B be 'nxp', so AB is 'mxp'. Further on, we know that r(A) <= min{m, n}, r(B) <= min{n, p} and r(AB) <= min{m, p}. I'm stuck here, although I tried to work something out with the inequalities, but without success. Any hints would be appreciated.
 

MathematicalPhysicist

Gold Member
4,024
117
you should look on the vector space of the homogenous solutions of Bx=0.
and use the fact that dim of this space equals n-rankB, also you should look on ABx=0.
from this you can easily prove that rank(AB)<=rank(B).
now i forgot how to prove the second inequality.
 

radou

Homework Helper
3,085
6
you should look on the vector space of the homogenous solutions of Bx=0.
and use the fact that dim of this space equals n-rankB, also you should look on ABx=0.
from this you can easily prove that rank(AB)<=rank(B).
now i forgot how to prove the second inequality.
Hm, I can't exactly say I follow.

The only way that r(AB) <= r(A) would follow from this is that d2 >= d1, where d2 is the dimension of the vector space of solutions to ABx=0, and d1 the dimension of the vector space of solutions to Ax=0. But why would I conclude that d2>=d1?
 

MathematicalPhysicist

Gold Member
4,024
117
ok, you need to show that U={x|Bx=0} is a subset of V={x|ABx=0}, then
dim U<=dim V
and dim U=n-rankB and dimV=n-rankAB, n is the number of columns of the matrix, the number of columns of AB is the same as of B.
the same way you can prove that rankAB<=rankA, with the use of rankAB=rank(AB)^t=rank(B^tA^t).
and rankA=rankA^t.
 

MathematicalPhysicist

Gold Member
4,024
117
if you ask why dimU<=dimV, then it follow from a thoerem that if U is subspace of V then (and V is finite) the inequality holds.
 

radou

Homework Helper
3,085
6
Ok, I got a grip on it now. Thanks! :wink:
 

matt grime

Science Advisor
Homework Helper
9,392
3
Woah, boys, you're making this way way to complicated. What is the rank? Just the dimension of the image. This is cleary a submultiplicative function (take some linearly independent vectors, applying a linear map can only make it more dependent).
 

radou

Homework Helper
3,085
6
Woah, boys, you're making this way way to complicated. What is the rank? Just the dimension of the image. This is cleary a submultiplicative function (take some linearly independent vectors, applying a linear map can only make it more dependent).
Ok, the definition of the rank of a mxn matrix A is r(A) = dim [{C1, ..., Cn}], where C1, ..., Cn are the columns of the matrix. What exactly does it mean 'to be a submultiplicative function' and how exactly do I apply this to the problem?
 

morphism

Science Advisor
Homework Helper
2,013
4
The image of AB is a subet of the image of A. So r(AB) <= r(A).

The second inequality follows from the first, as
r(AB) = r((AB)^t) = r(B^t A^t) <= r(B^t) = r(B)
 

radou

Homework Helper
3,085
6

morphism

Science Advisor
Homework Helper
2,013
4
The set { Av in R^m : v is in R^n }, if A is mxn, which is the same as the image of the linear transformation T : R^n -> R^m given by Tv = Av. So a matrix can simply be thought of as a linear transformation.
 

matt grime

Science Advisor
Homework Helper
9,392
3
What exactly does it mean 'to be a submultiplicative function' and how exactly do I apply this to the problem?
Forget it: it wasn't important, and wasn't used in the technical sense, just a suggestive one.
 
Last edited:

radou

Homework Helper
3,085
6
Forget it: it wasn't important, and wasn't used in the technical sense, just a suggestive one.
Yes, perhaps a bit too nonsuggestive for my level (no offence, of course). :smile:
 
solution :

let C=AB [ A=m*k , B= k*n, C= m*n]
now let the rows be C and B be: {c[1],c[2],....c[m]} , { b[1],b[2]....b[k]
thus we can write :
c= A[1]*b[1] + A[2]*b[2] +...+ A[m]*b[m]

therefore the row space of C is a subspace of row space of B
therefre Rowrank(C)=rank(C) <= Rank (B)
similarly proceed wid column rank argument for
Column rank (C)=Rank(C) <= Colum rank (A)=Rank(A)
hence Rank(C)<= {Rank(A),Rank(B)}
 
You can think this as ''how can the dimension of the nullspace of the product increase ?" For a little intuition, think about how can (AB)x = 0 be satisfied with a nonzero x vector, either it is because x is in the nullspace of B or (Bx) is in the nullspace in A. It is very useful to experiment these kind of stuff with full rank rectangular matrices...
 

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top