Return to Answer

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 $k>n$ one needs to find out if the GCD of all $n\times n$ minors is 1. This is probably not much easier than finding the Smith normal form.

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.

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: 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 $k>n$ one needs to find out if the GCD of all $n\times n$ minors is 1. This is probably not much easier than finding the Smith normal form.

Edit: Case 1, 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: Case 2, k>n (taking from my comment)

Let $B=A^TA$. Then the subgroup generated by $a_i$ is equal to $\mathbb{Z}^n$ if and only if $\det(B)=1$.

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.