# Hermite normal form and basis for the nullspace

Define the Hermite Normal form $$H$$ for a matrix $$A\in Z^{n\times n}$$ as following:

$$H=UA$$ which in Mathematica is given as {u, h} = HermiteDecomposition[a]

Then for a system of homogeneous equations $$Ax = [0]_{n}$$ we normally compute a basis for the Nullspace of $$A$$, so any vector $$x$$ in $$Ker(A)$$ satisfies the system.

It results that $$Ax=[0]_{n} \rightarrow U^{-1}Hx =[0]_{n} \rightarrow Hx = [0]_{n}$$

Then computing such a basis for $$A$$ can be done in terms of $$H$$, where $$H$$ is an upper triangular matrix, so at first glance NullSpace runs faster for $$H$$ instead of $$A$$.

But I'm not very familiarized with the time-complexity of Mathematica's implementation of HermiteDecomposition and Nullspace (this last one over a prime modulus). I don't think this would be a good idea for big dimensions, this is, big $$n$$.

The thing is that I need a $$\textit{fast}$$ and efficient method for computing a basis for the nullspace of $$A$$ over $$F_2$$ when $$n$$ is considerably big. What can I do?

P.D = As a recommendation from MarcoB the time lapses are given with an example matrix of size $$100\times 100$$:

NullSpace only call: $$0.010054$$s

HermiteDecomposition + NullSpace: $$0.071549$$s

LatticeReduce + NullSpace: $$0.258836$$s

where the NullSpace call is always taken over $$F_2$$.

• Well, since both functions HermiteDecomposition and Nullspace are already available, couldn't you just make up some fake number with which to try both out and compare timings (e.g. with RepeatedTiming)? Nov 19, 2019 at 20:39
• I thought the same on my way to home. Will post time lapses as soon as I return to my research. Thanks. Nov 19, 2019 at 21:04
• @MarcoB: New day, new tests. Included time lapses for my method with an example squared matrix with $n=100$. When $n=2500$ it takes $1$ minute approximately to compute such a basis over $F_2$, so what can I do to optimize this procedure in Mathematica? Any alternative that I can implement and you can point me to? Thanks for your kind help. Nov 20, 2019 at 12:03
• Thank you for running the tests. Please include the specific code and data you used in your question, so others can play around with it and chime in. Nov 20, 2019 at 13:51
• Why not just use NullSpace[mat,Modulus->2]? Nov 20, 2019 at 15:43

NullSpace[mat,Modulus->2]

Another method, which can be used in tandem with splitting, is to use bit strings to represent rows. The null space can then be extracted with ResourceFunction["BitStringNullSpace"], documentation for which is found here.