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?
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 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.
The SVD will both (1) tell you what the null space of your matrix is (2) give you the pseudo-inverse of the matrix in the event that it is singular. The SVD is, generally speaking, a very handy matrix factorization and for your stated purposes should definitely get the job done.
If you're determined to write the code yourself, Trefethen and Bau's book has enough details to work from, either implementing the really bad way of finding the eigendecomposition of A*A or the proper way using bidiagonalization.
However, if you just happen to be working in C and don't feel the need to do it yourself, the Wikipedia page for the SVD has a long list of libraries that will implement it for you, chief among which is the GNU Scientific Library. Or, a google search of "SVD c source code" turns up a couple results as well.