Conditions for Linear Diophantine Equations to always have a solution
Short answer: No.  Most likely, no useful constraint exists; and it can't be tested in polynomial time.



Detailed answer, with justification: It cannot be tested in polynomial time, unless P = NP.  In particular, if you could test for existence of a non-negative integer solution to such a system, you could solve integer linear programming (ILP).  Here's how the reduction works:

Suppose we have an ILP instance with variables $x_1,\dots,x_k$.  We'll modify it by introducing variables $x_1^+,\dots,x_k^+$ and $x_1^-,\dots,x_k^-$.  Then we'll replace each inequality

$$c_0 + c_1 x_1 + \dots + c_k x_k \ge 0$$

with the equality

$$c_0 + c_1 x_1^+ - c_1 x_1^- + \dots + c_k x_k^+ - c_k x_k^- = y_j$$

and the inequality $y_j \ge 0$, where $y_j$ is a fresh new variable.  Thus if the original ILP instance has $k$ variables and $m$ inequalities, the new instance will have $2k+m$ variables, $m$ equalities, and $2k+m$ inequalities $x_i^+ \ge 0$, $x_i^- \ge 0$, $y_j \ge 0$.

This now has the form of your problem, i.e., integer linear diophantine equations where we are looking for non-negative solutions, with $n=m$ linear equations and $v=2k+m$ variables.  Note in particular that we are guaranteed to have $v&gt;n$, since we must have $k&gt;0$.  Moreover, any solution to the original integer linear programming instance leads to a solution to this diophantine problem (take $x_i^+ = \max(0,x_i)$ and $x_i^- = \max(0,-x_i)$), and conversely, any solution to this diophantine problem leads to a solution to the original ILP instance (take $x_i = x_i^+-x_i^-$).  Therefore the derived diophantine problem is equivalent to the original ILP instance.

This reduces ILP to testing existence of a solution to a diophantine problem.  Since ILP is NP-hard, it follows that testing existence of solutions to this kind of diophantine problem is NP-hard, too.  That means there is not likely to be any polynomial-time algorithm to it (assuming you believe it is unlikely that P = NP).

For similar reasons, you should not expect a useful condition that is necessary and sufficient to ensure that a solution always exists: any such condition must be infeasible to check in the worst case, unless P = NP.  You can pick two out of any three: necessary; sufficient; efficiently checkable -- but you can't have all three, assuming P != NP (as many expect).