Proving Nullity in Linear Algebra: A < AB for m*n and n*n Matrices

[workerant]

Prove that for any m*n matrix A and any n*n matrix B, nullity A is less than or equal to nullity AB.

I know nullity of A is n-rank A and this is always greater than or equal to 0 and I figured nullity AB is like nullity A * nullity B, which are both greater than or equal to 0. Is this in the right direction?

 

[n00bhaus3r]

The nullity of a vector space is also known as the dimension of the nullspace, a fundamental subspace whose dimensions are defined by the rank of the nullspace basis. An easy way to compute the nullity is to subtract the number of pivots from the number of columns.

This could be a lemma in your proof (that is, perhaps, essential to your problem):

Claim: The rank of the product of any two matrices cannot exceed the rank of either matrix. (This is the first part of Syvester's Law of Nullity)

First, we need to understand that we can write any matrix in the form P^-1*N*Q^-1 where N is its row reduced form and P^-1 undos the column operations and Q^-1 undos the row operations.

Let A and B be m x p and p x n matrices. We can write A as P^-1*N*Q^-1.

The rank of AB is equal to the rank of P^-1*N*Q^-1*B. Knowing that the rank of a matrix A is unchanged by premultiplication (resp. postmultiplication) by a nonsingular matrix (1), we can rewrite the expression as:

N*Q^-1*B

We can verify that the first r rows of N*Q^-1*B are the same as those of Q^-1*B while the remaining m-r rows are zeroes. Using (1), we know that the rank of AB is less than or equal to the rank of B. Similarly, the rank of AB is also less than or equal to the rank of A.

Therfore, the rank of the product of two matrices A and B cannot exceed the rank of either factor. QED.

I think the proof of the claim is fairly hard to wrap your head around, but it's what I'd use to prove the same for the nullity. Hope it helps.