# Numeric solution of simple but possibly singular linear system

I have a simple (and small) linear homogeneous system $Ax=0$, where the entries of the $N\times M$ matrix $A$ are small integers. I do not need fancy methods which efficiently solve almost singular matrices and treat roundoff errors etc. But I need to know if a system is singular and also the general solution for underdetermined systems. It must be rock-solid. Any reference to such an algorithm is welcome. I am coding in C. Is SVD the way to go?

-
Are you looking for integer solutions as well? What is the size of $N$ and $M$? By "general solution", do you mean a basis of the null space of $A$? –  Christian Clason Jan 4 at 22:30
Yes, essentially I mean a basis of the null space. Size of N and M can vary, where N>M and M>N is both possible . Typical size could be N,M\sim 10. I searched a bit further and found that 'reduced Row Echelon form' could be the solution. Since A has integer elements only rationals would appear and I could compute exact results. Anybody aware of an open implementation (any language). –  highsciguy Jan 4 at 22:38
I.e. I search an implementation of the Gaussian elemination for NxM matrices. I know that of Numerical recipies, but it is for NxN. I understand now that SVD would work. But it seems a bit overkill to me with the additional advantage that it would use floats and probably be to long to adopt it to integers/rationals. –  highsciguy Jan 4 at 23:00

The Integer Matrix Library is a C library that claims to be able to compute the null space of an integer matrix. See also this answer on MathOverflow to the exact same question, which gives a list of libraries (including PARI, which also can be called from C and is still being updated). You could also take a look at LinBox, even though it's written in C++.

-
The reference to IML was pretty useful to me. It does what I want. Also the question on MathOverflow is really the same. –  highsciguy Jan 6 at 15:06

The general solution of your underdetermined system is that $x$ is a member of the nullspace of $A$.

To find the nullspace of $A$, the most numerically stable method is to use an SVD. See Null-space of a rectangular dense matrix for further details.

-