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.
Left inverse and nullspace
-
1Do you know what a contrapositive is? Can you show that if $m\lt n$ then the nullspace is nontrivial? – 2011-05-18
-
0Sorry, did not know the imperative form would be that offensive and did not mean to order anyone. It is my first time here :( I tried by contradiction as Arturo mentioned but could not get the conclusion that the nullspace is nontrivial. And this is not a homework question. I will restate that later then, thanx! – 2011-05-18
-
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
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?
-
0Arturo, thank you for your time. Actually, my professor did not consider the rank-nullity theorem as a given. – 2011-05-19
-
0Actually, I understood your solution. It was thorough. I was referring to the alternate solution presented by Mac, which mentioned the rank-nullity theorem. For the next time, I will make sure to post comments in the right section. Thank you, Arturo ! =) – 2011-05-19
-
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
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$.
-
2but we don't know (because heber hasn't told us) whether the question comes up before or after the presentation of that theorem. It may be a step on the way to the proof of that theorem, in which case, circular reasoning. – 2011-05-19
-
0Or 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