# Find NullSpace of a very sparse symbolic matrix

Below is a matrix diagram, produced in Mathematica. In this case it's a $956\times 950$ rectangular matrix. The white parts are all zero.

sa = Import["https://pastebin.com/raw/fiErKrhU", "Package"];
MatrixPlot[sa]

I'm wondering if there is a way to efficiently compute the null space of this matrix. From a different calculation entirely (using a Molien series), I know in advance there should be 6 linearly independent vectors in this null space, and I already know one of them.

The NullSpace routine takes too long to be feasible. I am hoping that there is a better way. I know that using NullSpace[N[m]] will return the answer rather quickly, but I am hoping to be able to do this symbolically.

Any help would be appreciated.

## Update

Added SparseArray data for this matrix. It was too large for this message so I put it on pastebin.

https://pastebin.com/raw/fiErKrhU

• What happens if you try SingularValueDecomposition[] on it? It's really hard to say anything meaningful otherwise without seeing your matrix. – J. M.'s discontentment Sep 26 '17 at 3:20
• If the nonzero entries are approximate numbers then it should be quite fast. Really hard to say more without the actual input (which can be added explicitly to the question as a SparseArray) – Daniel Lichtblau Sep 26 '17 at 14:13
• @J.M. SingularValueDecomposition doesn't seem to give any output in a reasonable time (~30m). – oscarafone Sep 26 '17 at 20:06
• @DanielLichtblau I'd be happy to post the matrix. How should I do it? – oscarafone Sep 26 '17 at 20:08
• I think it would be good to create it as SparseArray[{{rowi,rowj}->valueij,...}] and put that in your question. From the picture there should be "only" a few thousand values so that should not overly bloat the question. – Daniel Lichtblau Sep 26 '17 at 21:24

Turns out this can be done with exact methods and a good option setting. And a dose of patience. I won't copy the matrix itself. In my session I named it mat as below.

AbsoluteTiming[
nullspace = NullSpace[mat, Method -> "OneStepRowReduction"];]

(* Out[18]= {1839.141297, Null} *)

Check size and correctness:

Length[nullspace]

(* Out[19]= 6 *)

LeafCount[nullspace]

(* Out[20]= 50803 *)

Max[Abs[mat.Transpose[N[nullspace]]]]

(* Out[21]= 1.00182351685*10^-10 *)

I also have tried the method here but with no luck thus far. Oh well (I blame the author...)

• Excellent, Daniel! Thanks! But how did you figure out that that setting would speed things up? – oscarafone Sep 27 '17 at 22:10
• General experience. Possibly it should be the default when the matrix is exact and NumericQ, I'm not sure. – Daniel Lichtblau Sep 27 '17 at 23:20

I think you're having problems because the numbers in the array are rationals. I copy/pasted your matrix, it gives a sparse array object that I named 's'. Then N[ ] transforms it into floating point numbers, and

NullSpace[N[s]] // Length

returns 6.

• Yes, I know this. In fact this is what I meant when I said "using machine precision resolves the issue but I am aiming for a symbolic solution." I used clumsy wording and that's probably why you didn't realize I said that. Anyway, I appreciate the help regardless. – oscarafone Sep 26 '17 at 22:11
• OK -- but it seems a stretch to say that this is a "different calculation entirely". Also, you are misusing the term "symbolic", your matrix has no symbols, only rationals. – bill s Sep 26 '17 at 22:18
• I didn't say it was a different calculation entirely, I'm not sure why you quoted that. Also forgive me, I'm not sure what the appropriate word to use is in this case. Perhaps "non-decimal"? – oscarafone Sep 26 '17 at 23:03
• @oscarafone, might be a bit more accurate to say that you have a sparse matrix with exact number entries. – J. M.'s discontentment Sep 26 '17 at 23:06
• @bills I understand now. I actually computed the rank of the null space by using a Molien series -- that's how I got the number 6. That is what I meant by "different calculation entirely". Sorry for the confusion. – oscarafone Sep 27 '17 at 2:36