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
NASA's space station Robonaut finally getting legs
Free the seed: OSSI nurtures growing plants without patent barriers
Going nuts? Turkey looks to pistachios to heat new eco-city
MathematicalPhysicist
MathematicalPhysicist is offline
#2
Feb5-07, 08:18 AM
P: 3,174
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,174

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,174
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