Are there cases in which the Rouché–Capelli theorem does not hold?

Question

I have written a program which solves an $m \times n$ system of linear equations by using Gaussian elimination with pivoting. After I reduce the augumented matrix $[A~|~B]$ to echelon form using elementary row transformations, I use the Rouché–Capelli theorem in order to find out if the system has a solution, and if so, whether the solution is unique or there are infinitely many solutions.

Namely, I compare the ranks of the augumented matrix and the coefficient matrix, and state that the system has solutions iff the two ranks are equal. After that is established, I check whether the rank of the coefficient matrix is equal to the number of unknowns. If that's the case, I say that there is a unique solution and print it out, and if not, I say that there are infinitely many solutions.

However, some automated tests I ran (unfortunately, I am unable to see the input these tests use) show that, in two cases (out of 15 or so) the output of my program is wrong – it says that there are infinitely many solutions when it should say that there are no solutions.

So, my question is, are there some specific cases in which the Rouché–Capelli theorem does not hold? Or perhaps there is a logical error in my code or something (alas, that is never out of the question).

Have a great day, everyone.

Answer 1

Assuming there are no bugs in your code:

Short Answer: Don't use finite precision numerical evidence to refute Theorems.

Long Answer: Most computer languages support Finite Precision Arithmetic. They abide by IEEE 754 standards for storing floating point numbers. So, you might have upto 16 digits of accuracy and no more. When this happens, zero determinants and non-invertible matrices suddenly become invertible. In fact, I encourage you to try this very simple code in MATLAB: 0.1+0.1+0.1==3. Ideally, it should return $1$. After all, $0.3$ is equal to $0.1+0.1+0.1$. See what MATLAB tell's you. Rouche-Capelli (or for that matter any theorem) is a theorem. There are certain assumptions under which the claim must hold true. There is absolutely no room for ambiguity there. Going back to your question on linear systems, extensive research has been done in the field of Numerical Linear Algebra. Concepts like condition number have devised in order to better understand (and predict) how linear systems behave to perturbations and numerical errors. I highly encourage you to read this article (which was quite eye-opening for me): What Every Computer Scientist Should Know About Floating-Point Arithmetic

Answer 2

Rouche' Capelli is a Theorem. No doubt about that. Its conclusion holds true whenever its hypothesis are satisfied. So, using your words: No, R-C-Theorem holds always.