7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Take the gcd of all the determinants of the square matrices coming from $k$ vectors at a time. This will be 1 iff the set generates the standard copy of ${\bf Z}^k$. Worst possible case is that $n$ choose $k$ subsets will be required, but if it is a generating set, far fewer subsets should be required. $\endgroup$ – David Handelman Oct 9 '17 at 22:45
  • $\begingroup$ @DavidHandelman: I had the same idea (see my answer). But this does not seem much easier than the Smith normal form because the GCD is the largest diagonal element of the Smith form. $\endgroup$ – Mark Sapir Oct 9 '17 at 23:11
9
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Thanks Richard! At a glance it seems that the intermediate coefficients can be exponentially long, which makes it hard to use this method for large matrices. Can we "cheat" computing $B$ explicitly if we only want to check that diagonal elements of $B$ are $\pm 1$? $\endgroup$ – Mikhail Tikhomirov Oct 9 '17 at 0:51
  • 3
    $\begingroup$ Curiously LLL (or some other algorithm for lattice basis reduction) is often the most efficient way to deal with this issue. Also, SNF is implemented in several computer-algebra systems; e.g. in gp it's matsnf. $\endgroup$ – Noam D. Elkies Oct 9 '17 at 1:25
  • $\begingroup$ There is a lot of literature on this problem. There are certainly polynomial time versions of SNF but I believe that the LLL based methods are the fastest in practice. $\endgroup$ – Derek Holt Oct 9 '17 at 8:21
  • 1
    $\begingroup$ To get a polynomial time algorithm, you can calculate the Hadamard bound $d$ on the determinants of square submatrices of $B$, and then do your computations modulo $d$. For your application, you do not need the associated basis change matrices, but the Kannan-Bachem algorithm is a polynomial tiem method for doing this. $\endgroup$ – Derek Holt Oct 9 '17 at 9:22
  • $\begingroup$ The original reference for polynomial-time algorithm for SNF (and HNF) is doi.org/10.1137/0208040 . $\endgroup$ – Emil Jeřábek Oct 9 '17 at 11:32
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ But that only works for square matrices. $\endgroup$ – Derek Holt Oct 9 '17 at 17:15
  • 1
    $\begingroup$ What about e.g. $A=\binom23$? $\endgroup$ – Emil Jeřábek Oct 9 '17 at 20:48
  • $\begingroup$ @EmilJeřábek: OK. You are right. $A^T A$ does not help. The other method (first reduce A to reduced column-echelon form, then look at submatrices of rank $n$) is also more complicated than I thought: too many matrices to consider. So I left only the case $k=n$. $\endgroup$ – Mark Sapir Oct 9 '17 at 21:10
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.