# 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

## 3 Answers

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

-

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

-

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 9, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9492892026901245, "perplexity_flag": "head"}