Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.