Another matrix rank proof


by radou
Tags: matrix, proof, rank
radou
radou is offline
#1
Feb5-07, 07:13 AM
HW Helper
radou's Avatar
P: 3,225
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.
Phys.Org News Partner Science news on Phys.org
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
MathematicalPhysicist
MathematicalPhysicist is offline
#2
Feb5-07, 08:18 AM
P: 3,177
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
radou is offline
#3
Feb5-07, 09:04 AM
HW Helper
radou's Avatar
P: 3,225
Quote Quote by loop quantum gravity View Post
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
MathematicalPhysicist is offline
#4
Feb5-07, 10:05 AM
P: 3,177

Another matrix rank proof


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
MathematicalPhysicist is offline
#5
Feb5-07, 10:07 AM
P: 3,177
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
radou is offline
#6
Feb5-07, 10:28 AM
HW Helper
radou's Avatar
P: 3,225
Ok, I got a grip on it now. Thanks!
matt grime
matt grime is offline
#7
Feb5-07, 12:56 PM
Sci Advisor
HW Helper
P: 9,398
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
radou is offline
#8
Feb5-07, 01:11 PM
HW Helper
radou's Avatar
P: 3,225
Quote Quote by matt grime View Post
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
morphism is offline
#9
Feb5-07, 02:43 PM
Sci Advisor
HW Helper
P: 2,020
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
radou is offline
#10
Feb5-07, 02:53 PM
HW Helper
radou's Avatar
P: 3,225
Quote Quote by morphism View Post
The image of AB is a subet of the image of A.
How is the image of a matrix defined?
morphism
morphism is offline
#11
Feb5-07, 03:11 PM
Sci Advisor
HW Helper
P: 2,020
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
matt grime is offline
#12
Feb5-07, 03:12 PM
Sci Advisor
HW Helper
P: 9,398
Quote Quote by radou View Post
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.
radou
radou is offline
#13
Feb6-07, 04:26 AM
HW Helper
radou's Avatar
P: 3,225
Quote Quote by matt grime View Post
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).
mooniitk
mooniitk is offline
#14
Nov15-07, 07:51 AM
P: 1
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[i]= A[i][1]*b[1] + A[i][2]*b[2] +...+ A[i][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)}
trambolin
trambolin is offline
#15
Nov29-07, 03:30 PM
P: 341
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...


Register to reply

Related Discussions
Proof Help - Rank of the transpose of a Matrix Calculus & Beyond Homework 9
Rank of a matrix Calculus & Beyond Homework 3
Matrix manipulations/rank of a matrix Calculus & Beyond Homework 2
Rank of a Matrix Calculus & Beyond Homework 6
rank of a matrix proof Linear & Abstract Algebra 9