1
$\begingroup$

I am doing some independent studying, and came across one note from a professor, which states that if $A$ is an $m \times n$ matrix with zero nullspace, $m \geq n$. I simply have no idea on how to prove it. Hopefully someone can help me out. Thank you.

  • 1
    @heber: Perhaps, now that you know that it is considered *very impolite* to post the way you did, you would be willing to edit your post to make it more polite? Also: I did *not* say "contradiction", I said [contrapositive](http://en.wikipedia.org/wiki/Contraposition). They are not the same thing. Do you know anything about systems of linear equations in which there are more equations than unknowns?2011-05-18

2 Answers 2

3

Finding the nullspace of $A$ is equivalent to finding all solutions to the matrix equation $A\mathbf{x}=\mathbf{0}$.

Solving the matrix equation $A\mathbf{x}=\mathbf{0}$ is equivalent to solving a homogeneous system of linear equations. You have as many equations as there are rows in $A$, and as many unknowns as there are columns in $A$.

So if $A$ is an $m\times n$ matrix, then you have a system with $m$ equations in $n$ unknowns.

Rather than proving the statement, let's prove the contrapositive. Remember that the contrapositive of "If $P$, then $Q$" is "If (not $Q$), then (not $P$)". In this case, rather than proving:

If $A$ has zero nullspace, then $m\geq n$.

we will look at

If $m\lt n$, then the nullspace of $A$ is not just the zero vector.

So, suppose you have a homogeneous system of linear equation with $m$ equations in $n$ unknowns, and there are more unknowns than equations. Do you know anything about solutions to such systems?

  • 0
    @Heber: If you were referring to the alternate solution presented by mac, you may perhaps try commenting in that solution, and preceding it with his name, rather than commenting on my solution and specifically invoking my name. That pings *me*, so the comment ends up calling the attention of the wrong person...2011-05-19
2

Hint: this follows from the rank-nullity theorem, using the fact that the rank of a matrix with $m$ rows is no greater than $m$.

  • 0
    Or we can reduce the matrix to reduced row-echelon. Then one can show that in this form, there will be at least one free variable. For every row there is at most(, since we may end up with an all-zero row) one leading variable , for an upper-bound of n leading variables. For each of the m columns we have a variable--either leading or free-- for a total of m variables .If we have m columns, with m>n, then m-n>0 , so that at least one variable is free, and the nullspace cannot be trivial.2011-05-19