# Minimum basis for the nullspace of sparse matrices

Let $$A\in\mathbb{F}_2^{m\times n}$$ and denote its nullspace as $$V=\{x\in\mathbb{F}_2^m:xA=0\}$$. The weight of a basis $$B=\{b_1,\dots,b_l\}$$ for $$V$$ is the total weight of vectors in the basis, denoted $$|B|=\sum_{b\in B}|b|$$, where $$|b|$$ is the Hamming weight of vector $$b\in\mathbb{F}_2^m$$. Out of all bases for $$V$$, some bases have the minimum weight. We call these the minimum bases for $$V$$.

In general, finding a minimum basis is NP-hard, because it would allow one to calculate the distance of the binary, linear code with codespace $$V$$. However, given some sparsity constraints on $$A$$, the problem of finding a minimum basis for $$V$$ can be easy.

For example, if each row of $$A$$ has exactly two non-zero entries (two 1s), then a minimum basis for $$V$$ can be produced in $$\text{poly}(m,n)$$ time. This is because $$A$$ can then be interpreted as the incidence matrix for a graph $$G$$ with $$m$$ edges and $$n$$ vertices. Then, the minimum basis problem is equivalent to finding a minimum cycle basis for $$G$$, a task that can be performed by e.g. Horton's algorithm.

This brings me to my main question. Can anything be said about the time complexity of finding a minimum basis for $$V$$ when each row of $$A$$ has exactly three non-zero entries?