There are an infinite number of solutions to what you are trying to solve when N < 4. For example, let N and M be 1. That leaves us with 1x4 * 4x1 = 1x1. So Ax=b would basically be b = A1 * x1 + A2 * x2 + A3 * x3 + A4 * x4. For any given value of b, there are an infinite number of solutions of x that satisfy Ax=b. This is the case for any value of N < 4. When N = 4, x can be solved simply by calculating A-1b. When N > 4 and M=1, you have an overdetermined system. You can use Least Squares for that. I am not sure if least squares will work for you if M > 1.
EDIT: Upon further thought, I think least squares is what you are looking for. It should work when M > 1.