Just some comments that are well-known in the theory of toric varieties (and no
doubt to other areas as well). What we are asked to determine is membership in a
finitely generated submonoid $\Gamma$ of $\mathbb N^k$ with more than $k$
generators. The last condition is is a red herring, we can always replace
$\mathbb R^k$ by the vector space spanned by the vectors (and the price of
possibly replacing $\mathbb N^k$ by some uglier monoid but as we shall see
$\mathbb N^k$ will quickly exit the picture).
The first question (which is part of the assumptions of the question) is whether it
lies in the subgroup $N$ generated by the same elements. Provided this has a
positive answer the next question is whether it lies in the saturation
of $\Gamma$, i.e., the submonoid $\Gamma'$ of elements $x$ of $N$ for which
$mx\in\Gamma$ for some integer $m>0$. The point about asking this question is
that is much easier to answer: The saturation is the intersection of $N$ with
the real (or rational) cone spanned by the original vectors. Duality for cones
implies that such a cone is the intersection of a finite number of rational half
hyperplanes (which can be reasonably efficiently be determined from the original
generators, see for instance Ziegler: Lectures on polytopes) and thus that
condition can be checked rather easily.
[[ Correction: I claimed that $\Gamma'\setminus\Gamma$ is finite which is wrong. ]]
The step from $G'$ to $G$ can also be quite tricky. It is a fact that $G'$ is
finitely generated as $G$-module, i.e., there are $x_1,x_2,¼,x_mÎG'$ such that
$G'=È_i(G+x_i)$ but the complement $\Gamma'\setminus\Gamma$ may be infinite. An
example is given by the monoid generated by $(0,2)$, $(0,3)$ and $(1,0)$ where
$(m,1)$ is not in the monoid genated by then but $2(m,1)$ always is.
The relation between $G$ and its saturation can be described in terms of
commutative algebra as follows. Consider the monoid algebra $k[G]$, where $k$ is
some field. The inclusion $GÍG'$ gives an algebra inclusion $k[G]Ík[G']$ and it
makes $k[G']$ the normalisation of $k[G]$ (this gives one way of showing that
$G'$ is finitely generated as $G$-module as the same is true for the
normalisation). The question of whether $\Gamma'\setminus\Gamma$ is finite or
not then has the following interpretation. We have a grading $G®\mathbb N$ of
$G$ given by $(m_i)e \sum_im_i$ which induces a grading of $k[G]$ allowing to
pass to a projective variety $\mathrm{Proj}k[G]$. Then $\Gamma'\setminus\Gamma$
is finite precisely when $\mathrm{Proj}k[G]$ is normal. The example above was
constructed using this; $\mathrm{Proj}k[G]$ is $1$-dimensional with a cusp and
hence is not normal.
