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

closed as off-topic by Andres Caicedo, Jeremy Rouse, Alex Degtyarev, András Bátkai, Joe Silverman Mar 7 at 15:48

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Andres Caicedo, Jeremy Rouse, Alex Degtyarev, András Bátkai, Joe Silverman
If this question can be reworded to fit the rules in the help center, please edit the question.

    
I assume you're looking for a condition considerably weaker than "A is invertible". –  Anton Geraschenko Oct 3 '09 at 14:49
    
I see that the research level considerably falls down. –  loup blanc Mar 7 at 15:33
    
@loupblanc Huh? This question is ancient. If one wants to see anything it might be that the level is higher than it was. (Or I missed your point completely.) –  quid Mar 7 at 18:28
    
@loupblanc This question was posted when MO was less than a month old, and the level of appropriate question had not at all be established. In fact, I was not asking the question because I needed to know the answer, but in a small effort to help populate the new site with questions. I would be quite satisfied to see this (and my other two questions) deleted, but I'll leave that question to folks that are active on the site. –  Eric Wilson Mar 7 at 20:42
1  
Less than a week old. If memory serves, MathOverflow debuted on Sep. 28. –  The Masked Avenger Mar 8 at 5:25

2 Answers 2

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

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

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