Question

Prove that if A is M by N and M<N, then there is a non-zero x with Ax = 0.

Answer 1

Every solution of Ax=0 is thesolution to Bx=0, where B is row echelon form, j=rankA=rankB. For B we have n-j
last zero rows, and these corresponding x_i 's can be choosen linearly
independent, and other will be automatically computed, so there will be n-j linearly
independent solutions.
So, choosing last coordinate one will obtain nonzero solution.