Linear algebra over natural numbers I am given a $m\times n$ matrix $M$ and a $m$-vector $y$.  I want to find a $n$-vector $x$ such that $Mx=y$ (or determine that no solution exists).  However, I have an extra constraint: all entries of $x$ are required to be non-negative integers.  All of the entries of $M,y$ are non-negative integers as well.
Is there a general technique to solve this kind of problem? Is there an efficient algorithm for this?
 A: Your problem is a version of the multi-dimensional knapsack problem.
To make things precise, put $y = (y_1, \ldots, y_m)^t$ and $M=(m_{i,j})_{1\leq i\leq m, 1\leq j\leq n}$.  Then your problem, formulated as a knapsack problem, would be:
$$
\textrm{maximize} \quad \sum_{i=1}^m\sum_{j=1}^n m_{i,j}x_j \\
\textrm{subject to} \quad \forall i\in\{1,\ldots, m\}, \sum_{j=1}^n m_{i,j}x_j \leq y_i \ \textrm{and} \ \forall j\in\{1, \ldots n\}, x_j\geq 0. \\
$$
If there is a solution such that the quantity to maximize is equal to $\sum_{i=1}^m y_i$, then it is a solution to your problem.
Judging from this paper, it is not so easy to solve the multi-dimensional knapsack problem.  Some algorithms are described in this Wikipedia page, the keyword being integer linear programming.
Note that if you remove the constraint that the solution is given by non-negative integers, then your problem becomes that of solving a system of linear Diophantine equations, and this can be done by finding the Smith normal form of the matrix $M$ (the precise method is described in the above link).
