There is an easy lower bound which is ceil(log(N)/log(2)).
The lower bound can't also be the answer though because consider (N,M)=(5,4)
Each column has exactly one 0. Therefore if we try to construct with lower bound of 3 columns, we must have at least two rows filled with 1's, thus we need 4 columns.
Possibly a generalization can be found from here.