Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Probably a simple question, but I can't find an answer anywhere, not even in the suggested questions with similar titles. It might also be that I just don't get the correct terminology. This is not really a field with which I'm familiar.

I have a system of equations of the form $aw+bx+cy+dz=e$ and I want to now whether there is a solution. More specific I have this situation:


where $A$ is a matrix of $n\times 4$, $x$ is of $4 \times 1$ and $b$ is of $n\times 1$ with $n>4$. $A$ consists solely of non-negative integers, and for my case $b=\begin{bmatrix} 2 \\ \vdots \\2 \end{bmatrix}$.

The question is how I can efficiently implement an algorithm to check whether these equations are consistent, i.e. whether the solution space is non-empty. I'm satisfied with an approximate solution but it may never say that there are no solutions when there are. The other way around is allowed, but I want to exclude as many inconsistent systems as possible.

share|cite|improve this question
up vote 2 down vote accepted

If you just have one matrix $A$ and one $b$, the simplest thing to do is Gaussian elimination to reduce the augmented matrix to echelon form. You can use a fraction-free version of Gaussian elimination to take advantage of the entries being integers. The system is inconsistent iff the echelon form has a leading entry in the augmented column.

share|cite|improve this answer

Basically, you need a description of the range of $A$ and check, whether $b$ lies in or out.

A projection onto the range of $A$ can be computed by several means, e.g. the QR decomposition. If you have $P$ as a projection matrix onto the range of $A$, just check of $Pb=b$.

share|cite|improve this answer

Your Answer


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.