1
$\begingroup$

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:

$Ax=b$

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.

2 Answers 2

2

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.

1

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$.