# Finding the null space of a large sparse matrix

I am trying to compute the null space of a large $$n\times n$$ sparse matrix. No matter how large the dimension of the matrix is, it will always look like as below:

The figure on the left shows the version of the matrix for with 10-dimension and the right panel is the ~1700 version. As can be seen, it will always be a very sparse matrix and I'm trying to find its null space. Are there any suggestions on what would be the most efficient way to do so? Or at least, is NullSpace[] the most efficient tool in this case?

In terms of dimensionality, I'm aiming to go as high as the computational power of Mathematica allows me. I have already seen the question here and I also have tried RowReduce as well, but I'm always getting the error "Result for RowReduce of badly conditioned matrix". Nullspace seems to work fine (albeit slow), at least up to n~40000 that I've tried so far.

Update

Link to a notebook that generates the matrix.

• Indeed, NullSpace should be the way to go. Maybe Eigensystem[A, -1, Method->"Arnoldi"] with suitable shift might also help. But as always, it depends on your concrete matrix. Would you please share the code that generates it? Aug 1, 2019 at 0:14
• Hmm. Apparently, {lambda, u} = Eigensystem[NullMatrix, -1, Method -> {"Arnoldi"}]; works fine. u[[1]] seems to be the only null vector. Or do you expect more than one? Then you can do, e.g., {lambda, u} = Eigensystem[NullMatrix, -20, Method -> {"Arnoldi"}]; and check the vector lambda of eigenvalues for zero (or near-zero) entries. Aug 1, 2019 at 3:26
• Thank you very much for your comment! Really appreciate it. To answer your questions, yes, in the actual system (based on physical reasoning), I only expect one null vector. And the system is some sort of special generalization of steady-state mean-field theory for spins other than 1/2. Aug 1, 2019 at 4:42
• @DanielLichtblau Very interesting approach; I will keep it in mind (+1). However, I am not convinced that this will work out in OP's example: Szabolcs had a very tall matrix in the other post, so the nullspaces of top can be expected to be rather small. However, this matrix here is a square $n \times n$-matrix, so Nullspace[top] will have at least $n$ elements... and I doubt that Nullspace[top] will be particularly sparse. Aug 2, 2019 at 13:09
• @HenrikSchumacher All good points. The method I linked to would probably not be so good here, barring someone figuring out improvements that elude me (and perhaps simply do not exist). Aug 2, 2019 at 16:02

Turning a comment into an answer.

Apparently,

{lambda, u} = Eigensystem[NullMatrix, -1, Method -> {"Arnoldi"}];


works fine. u[[1]] seems to be the only null vector. Or do you expect more than one? Then you can do, e.g.,

{lambda, u} = Eigensystem[NullMatrix, -20, Method -> {"Arnoldi"}];


and check the vector lambda of eigenvalues for zero (or near-zero) entries.