The multidimensional Frobenius problem (Q656045)

In this paper the authors consider a multidimensional analogue of the linear Diophantine problem of Frobenius. A numerical semigroup is a submonoid of the natural numbers with finite complement and the Frobenius problem is to determine the largest element of this complement. This paper focuses on a matrix generalization of this problem. Much of the difficulty in this paper consists of coming up with the appropriate adaptations of concepts from the classical one-dimensional setting to more general submonoids of \(\mathbb{N}_0^n\). Let M be an \(n \times (n+m)\) matrix with integer entries and \(x\) a length \(n\) column matrix with entries in \(\mathbb{N}_0\). The goal of this paper is to analyze the vectors \(g\) so that \(M x = g\) has no solutions. This leads to the study of linear combinations of these \(n+m\) columns with nonnegative coefficients. The authors define a partial order on vectors and define an appropriate notion of what it should mean for such a vector \(g\) to be maximal among those not in the monoid derived from \(M\). They then give higher-dimensional analogues of several results and techniques for one-dimensional Frobenius numbers in terms of these `Frobenius vectors'. In certain special cases they are able to give a complete characterization of this set of vectors.