Checking a generating set of $\mathbb{Z}^k$

Question

Let $a_1, \ldots, a_n \in \mathbb{Z}^k$. I need to check if $a_1, \ldots, a_n$ is a generating set of $\mathbb{Z}^k$, that is, every vector $v \in \mathbb{Z}^k$ can be represented as an integer linear combination $v = \sum c_i a_i$ with all $c_i \in \mathbb{Z}$. Note that the set $a_1, \ldots, a_n$ may be redundant in the sense some $a_i$ may be a linear combination of other elements.

The question is: what is the fastest practical way to check this? It seems that LLL algorithm can be used in some way, but its complexity leaves something to be desired, also the present problem is very resticted compared to lattice reduction. I would appreciate any reference to a faster algorithm that solves this problem.

Answer 1

You can compute the Smith normal form $B$ of the matrix with rows $a_1,\dots,a_n$. The rows generate $\mathbb{Z}^k$ if and only if the main diagonal entries of $B$ are $1$. (SNF over $\mathbb{Z}$ is determined only up to multiplication of the diagonal entries by $\pm 1$, and conventionally they are chosen to be nonnegative.)

Answer 2

Edit: This works if $k=n$

If $a_i=(\alpha_{i1},...,\alpha_{in})$, then the index of the subgroup generated by $a_1,...,a_n$ is infinity if the determinant of the matrix $A=(a_{ij})$ is $0$ or the absolute value of that determinant. Thus the subgroup generated by $\{a_1,...,a_n\}$ is the whole $\mathbb{Z}^n$ if and only if the absolute value of the determinant $\det(A)$ is 1. I think that the problem of checking if the determinant is 1 should be very low.

Edit: For $n>k$ one needs to find out if the GCD of all $k\times k$ minors is 1. This is probably not much easier than finding the Smith normal form.

Answer 3

You can avoid checking all $\binom{n}{k}$ subsets of the rows by taking $k$ random combinations of the rows, that is, compute the determinant of $$ \left(\sum\xi_{1i}a_i, \sum\xi_{2i} a_i, \ldots, \sum\xi_{ki}a_i\right), $$ where $\xi_{ij}$ are independent random variables chosen from $[-N, N]\cap\mathbb{Z}$ with respect to the uniform distribution. If the $a_i$ generate $\mathbb{Z}^k$, then this matrix is essentially random, so it will most probably have a very large determinant. Repeat this procedure a few times to obtain determinants $D_1, D_2, \ldots, $, and compute the gcd of these determinants. If the $a_i$ generate $\mathbb{Z}^k$, then with high probability $(D_1, D_2)$ has only very small prime factors. If not ,compute a few more determinants, until either you can factor the result, or the sequence $(D_1,D_2), (D_1, D_2, D_3), \ldots, (D_1^, \ldots, D_k)$ seems to stabilize. In the frst case apply Gauss elimination modulo the product of all occurring prime factors, in the second case most probably the limit of the sequence equals the gcd of all $k\times k$-subdeterminants. This can again be shown by Gaus elimination. Note that while Gauss elimination is not a practical method for the original matrix, it works well modulo some integer, even if this integer is rather large.

Actually computing the probabilities occurring is difficult, as you can only prove good results if $N$ is absurdly large. However, in practice rather small values of $N$, say $10^6$ often work.