# Integer combination of $V\subseteq\mathbb{Z}^n = (1, 1, 1, \ldots)$?

What are the subsets $V\subseteq\mathbb{Z}^n$ such that there is an integer combination of vectors in $V$ equal to $(1, 1, 1, \ldots)$? (where $n \in \mathbb{Z}^+$ and $\mathbb{Z}^n$ is the n-ary Cartesian product over $\mathbb{Z}$)

By integer combination I mean a positive integer $p$ along with vectors $v_1,v_2,\ldots,v_p \in V$ and integers $z_1,z_2,\ldots,z_p$ such that $z_1v_1 + z_2v_2 + \cdots + z_pv_p = (1,1,1,\ldots)$ with componentwise multiplication and addition.

-
Please clarify what you mean by "integer combination". – Desiato May 4 '12 at 21:25
Given a finite subset of $\mathbb{Z}^n$ (and the span of any set is contained in the span of a subset of size at most $n$), you can use straighforward methods (e.g., parts of the algorithm to find the Smith Normal Form) to find a basis for the submodule they generate. Once you have a basis, determining whether $(1,1,\ldots,1)$ is in the span is straighforward. But giving an abstract description is likely to be difficult. – Arturo Magidin May 6 '12 at 3:21
Well, I can do the case $n=1$; you want the subsets $A$ such that there is no $d\gt1$ dividing every element of $A$. – Gerry Myerson May 6 '12 at 3:48
The way you've currently phrased the question, with an $A$ and a $V$, the answer is that none exist. $V=\emptyset$ is always a subset of any $A$, and this $V$ doesn't have the property you seek. Carefully chosen nonempty sets would almost always work too. - If you just mean that $A$ has this property, then you're asking whether the subgroup generated by $A$ contains $(1,\dots,1)$; in this case, @ArturoMagidin's answer applies. – Greg Martin May 6 '12 at 4:15
@Greg and Gerry: I think you both misread the question. $A$ is a subset of $\mathcal P(\mathbb Z^n)$, not of $\mathbb Z^n$, and $V$ is an element of $A$ and a subset of $\mathbb Z^n$, not a subset of $A$. Of course Gerry's comment still applies if you replace $A$ by $V$. The formulation of the question is unnecessarily complicated; it would be simpler to just ask about the subsets $V\subseteq \mathbb Z^n$ with this property. – joriki May 6 '12 at 5:17

Let's do another very small special case to get some idea of what the problem is. Take $n=2$ and $V$ of cardinality 2, so $V=\{{(a,b),(c,d)\}}$ and we want to know whether there are integers $x,y$ such that $$\pmatrix{a&c\cr b&d\cr}\pmatrix{x\cr y\cr}=\pmatrix{1\cr1\cr}$$ By Cramer's Rule, this happens if and only if $a-b$ and $c-d$ are both multiples of $ad-bc$.