Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
I assume you're looking for a condition considerably weaker than "A is invertible". –  Anton Geraschenko Oct 3 '09 at 14:49
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.