Question

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.

Answer 1

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.

Answer 2

All answers to this are going to be essentially the same: use Gaussian Elimination to attempt to solve the equation Ax = b and if it works then there is a solution, whereas if it doesn't then there isn't. Exactly what form of this answer is best for you depends on what you know and what methods you are prepared to use. Any method that you could type into a computer will essentially be doing Gaussian Elimination.

A simple condition is that there is a solution if and only if the rank of A is the same as the rank of the augmented matrix [A b] (i.e. A with b adjoined as an extra column). However, to work that out in an actual problem would involve doing Gaussian Elimination on the original problem so it doesn't save you any work.