Given a $n\times m$ integer matrix $A$, we can consider its row span $span(A)$, that is, the minimal sublattice of $\mathbb{Z}^m$ containing all rows of $A$.
Given a subset of the rows of $A$ it is possible to check in polynomial time whether they already span $span(A)$. Hence one can determine whether a given row subset is minimal (with regard to inclusion) with the property that it spans the row space of $A$ (simply try removing any row and see if the result still spans the row space of $A$). But since we work over the integers, it is possible that there are other, strictly smaller row subsets with the same property. As an example, consider the "vectors" 2, 3 and 1. Then {2,3} and {1} both are minimal generating sets for $\mathbb{Z}$ of differing size. This leads to my first question:
Is there a polynomial time algorithm to verify whether a given subset of rows spanning the row space of $A$ is globally minimal with this property?
With "globally" minimal I mean that no other subset of smaller size with the desired property exists. And regarding "polynomial time", I know that I am a bit vague here; but I'd already be happy if there was something polynomial in $nm$, never mind the size of the coefficients in $A$.
I have the suspicion that this is the not the case. But if it is, then the natural next questions is:
Is there a polynomial time algorithm which, given $A$, computes a globally minimal subset of rows which span the full row space of $A$?
An interesting special case arises for $m=1$:
Given a set $N$ of integers, is there a polynomial algorithm for computing a globally minimal subset $M$ of $N$ such that $gcd(N)=gcd(M)$ ?
The context where this problem arises for me is that of abelian groups: Given a set of generators of an abelian group, how can one find a globally minimal subset of these generators which still generate the whole group? Finding a minimal generating set in this case is easy, but the restriction that I need to use a subset of the original generators seems to make things quite a bit more difficult.
