Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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$.

share|cite|improve this answer

Your Answer


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

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