# Anyone knows the algorithm used by NullSpace function?

NullSpace function gives a list of vectors that forms a basis for the null space of the input matrix.

When the rank of the input argument matrix $M_{m\times n}$ is exactly $n-1$, then the null space becomes the only non-zero null vector $Z$ of $M$ such that: $M\cdot Z=0$, which can also be obtained by singular value decomposition of $M$.

But by comparing the time consumption of SingularValueDecomposition and NullSpace, the latter is usually much faster, this indicates they are using different algorithms.

Then: what is the algorithm used by NullSpace function? It seems there is no clue here.

• Depends on the type of matrix. For example if it is exact and numeric e.g. all integers, NullSpace will use some manner of Gaussian elimination and that will be faster than (exact) SVD. Absent some indication of matrix type and size though everything is just speculation. – Daniel Lichtblau Dec 11 '14 at 15:44

## 1 Answer

NullSpace works on both numerical and symbolic matrices.

and implied by your link, under "Details" subsection, "Method" would sort of refer to the algorithm NullSpace uses.

Possible settings for the Method option include "CofactorExpansion", "DivisionFreeRowReduction", and "OneStepRowReduction". The default setting of Automatic switches among these methods depending on the matrix given.

So it depends on the matrix entries. So, as Daniel was saying, there is probably some form of Gaussian elimination at play.