# When does a matrix equation have a solution?

Given a matrix equation Ax = b where A is a matrix and b is a column vector, what is a condition that would ensure that there is a column vector x that satisfies the equation?

Assume the dimensions are sensible, and feel free to provide multiple conditions.

-
I assume you're looking for a condition considerably weaker than "A is invertible". –  Anton Geraschenko Oct 3 '09 at 14:49

Aside from imposing a strong condition like "the rank of A is equal to the length of b" (which implies that Ax=b has a solution for all b), you have to check if b is in the subspace spanned by the columns of A (since Ax is a linear combination of the columns of A).

The easiest algorithmic way I can think of to do that is to perform column operations (multiplying columns by non-zero scalars and adding multiples of one column to another) to get a new set of vectors with the same span, but in "reduced column-echelon form" (i.e. with as many rows as possible consisting of a single non-zero entry). Then it is easy to read off what the coefficients of b would have to be if it were a linear combination of the columns, and you can just check if that linear combination works.

-