# Check Whether an Overdetermined Linear Equation System is Consistent: General Approach?

I have the following overdetermined linear equation system:

$$Ax=b$$

where $A$ is a matrix of $n \times k$, $x$ is of $k \times 1$,$b$ is of $n \times 1$, where $n>k$.

We all know this is an overdetermined linear equation system.

The question is how to check whether the solve for $x$, and check that the vector is consistent in this case? Consistent as in the sense that when we plug in the $x$ vector value into the above linear equation systems, then the above matrix will be satisfied.

I can separate out the $k$ linear equations and find $x$ from $x_1$ to $x_k$, and then substitute in the remaining equations to check for consistency.

I afraid that this method can be numerically unstable; I would like to implement this on a computer, so I would prefer a solution that fully works here. Let us consider one pitfall of my above solution:

$$A=\begin{bmatrix} 10 & 10 \\ 0 & 0 \\0 & 10 \end{bmatrix}$$

Note that if you separate the $1$ and $2$ rows out, and compute the solution, you may not be able to even solve it ( equation $2$ is an equation here with no unknown terms, after you times in the $0$ factor)!

Is there other method?

-
"Consistency" means that the system has a solution. What you are asking is not how to check for consistency, but rather how to check if a particular $x$ is a solution. What's wrong with plugging it in? It's pretty straightforward, and pretty quick. – Arturo Magidin Dec 15 '10 at 6:20
Why do you not like the approach that you mentioned in your last sentence? – J. M. Dec 15 '10 at 6:20
@Arturo, I afraid that it can be numerically unstable; I would like to implement this on a computer, so I would prefer a solution that fully works here. – Graviton Dec 15 '10 at 6:54
@J.M., see the updated question – Graviton Dec 15 '10 at 7:20
You can still swap rows. Gaussian elimination routines generally swap rows for stability purposes anyway. Look up "partial pivoting". – J. M. Dec 15 '10 at 9:20

If you are worried about the numerical stability do QR decomposition of matrix $A$. Then $A=QR$, where $Q$ is orthogonal and $R$ is triangular. Then you need to check whether $x$ satisfies the equation

$$Rx=Q^Tb$$

Now since $R$ is triangular and $n>k$ we will have that the last $n-k$ rows of $R$ are zero. Since $Ax=b$ it follows that the last $n-k$ elements of $Q^Tb$ should be zero also. If they are not, then $x$ is not a solution.

Furthermore since we have an overdetermined matrix the solution exists only if $b$ lies in the linear space spanned by columns of $A$. So the real question is, how do we reliably check whether $b$ is in linear space spanned by columns of $A$.

Update 2

Since $n>k$, the $R$ matrix will look like:

\begin{align*} R=\begin{bmatrix} R_1\\ 0 \end{bmatrix} \end{align*} where $R_1$ is $k\times k$ upper triangular matrix. If the solution exists, then

\begin{align*} Q^Tb=\begin{bmatrix} b_1\\ 0 \end{bmatrix} \end{align*} where $b_1$ is $k\times 1$ vector. The solution for our system is then $$x=R_1^{-1}b_1$$

-
mpiktas, that's for least squares. For instance: if you QR decompose the 3-by-2 example of Ngu (call the original matrix $\mathbf A$), and let $\mathbf b=(2\quad 3\quad 4)^T$ and $\mathbf x=\left(0\quad \frac1{10}\right)^T$ , your equation doesn't work, even if the $\mathbf x$ I gave minimizes $\|\mathbf A\mathbf x-\mathbf b\|_{\infty}$ – J. M. Dec 15 '10 at 9:03
@mpiktas, how to compute the $x$ in this case? – Graviton Dec 15 '10 at 9:16
Yes, you are right. You cannot even multiply $Q$ by $b$, since the dimensions do not match. The answer I think still lies in decomposition of $A$, but it should be rephrased better. – mpiktas Dec 15 '10 at 9:16
OK, I fixed the answer. Actually there is a slight typo in the question, $b$ should be $n\times 1$ vector, not $k\times 1$. – mpiktas Dec 15 '10 at 9:36
@Ngu Soon Hui. When we get to the matrix $R_1$ and vector $b_1$ we get the square linear system. Since determinant of $R_1$ is non zero, the solution always exists. If $Q^Tb$ is not of the form I mentioned, then the solution of the original system does not exist. – mpiktas Dec 15 '10 at 11:43

I am not sure why I cannot comment, but anyway, you can always do an RREF and then you should be fine.

-
let's say if there is no matlab involved? – Graviton Dec 15 '10 at 7:43
Manually doing an RREF is not that difficult. How else do you invert a matrix? (assuming you do not know LR decomp) – picakhu Dec 15 '10 at 8:03
ah, I get your point. But how does RREF helps to find the $x$? – Graviton Dec 15 '10 at 8:26
perform a GJ elimination to solve for x – picakhu Dec 15 '10 at 16:26

Consider the related least squares question: find x minimizing $||Ax-b||_2$. In the unlikely scenario that the overdetermined system has a solution, then we in fact have $||Ax-b||_2=0$.

The x solving the least squares problem can be found via the Moore-Penrose pseudoinverse:

$$x=(A^tA)^{-1}A^tb$$

So, one algorithm would be as follows:

1) Solve $(A^tA)x=A^tb$ via your favorite linear solver.

2) Check if $Ax-b=0$.

-
1. If $\mathbf A$ is rank deficient, the normal equations method fails. 2. I've mentioned the Lauchli example in here and other places on why the normal equations isn't always a good idea. The QR and singular value decomposition are safer alternatives. – J. M. Dec 16 '10 at 10:56
If you use a krylov solver like conjugate gradient and the initial guess is not in the null space of A, then it should work even with rank-deficient A (I think), though the point on stability is a good one. – Nick Alger Dec 16 '10 at 11:15
Krylov methods are appropriate only for large sparse systems. For small dense problems, QR and SVD remain standard. – J. M. Dec 16 '10 at 11:49