  Computing the null space of a large sparse matrix $A$ is a challenging
computational problem, especially if the nullity -- the dimension of the null
space -- is large. When using a block Lanczos method for this purpose,
conventional wisdom suggests to use a block size $d$ that is not smaller than
the nullity. In this work, we show how randomness can be utilized to allow for
smaller $d$ without sacrificing convergence or reliability. Even $d = 1$,
corresponding to the standard single-vector Lanczos method, becomes a safe
choice. This is achieved by using a small random diagonal perturbation, which
moves the zero eigenvalues of $A^{\mathsf{T}} A$ away from each other, and a
random initial guess. We analyze the effect of the perturbation on the
attainable quality of the null space and derive convergence results that
establish robust convergence for $d=1$. As demonstrated by our numerical
experiments, a smaller block size combined with restarting and partial
reorthogonalization results in reduced memory requirements and computational
effort. It also allows for the incremental computation of the null space,
without requiring a priori knowledge of the nullity.
