Only trivial solutions to system of linear diophantine equations possibly related to hamiltonian cycles in graphs This might be related to counting hamiltonian cycles.
@Peter Taylor gave negative result about the one dimensional case, but we believe his attack is
not directly applicable to this question.
Given positive integer $n$, find integer $m$ and $m \times n$
matrix $A = a_{i,j}$ with positive integer entries.
Let $y_1,...,y_n$ be integer variables.
Consider the following integer program with constraints:

*

*$0 \le y_i \le n$

*$\sum_{j=1}^n y_j = n$

*For $ 1 \le i \le m$: $\sum_{j=1}^n y_j a_{i,j}= \sum_{j=1}^n a_{i,j}$
We require the integer program to have unique solution
of $y_i$ all ones for chosen $(m,A)$. Let the solution be $(m_0,A_0)$.

Q1: How small the unique solution can be in terms of $n$? Can we get
$2^{m_0} \max ( a \in A_0)=\exp(o(n))$?

Getting $O(\exp(n))$ is easy by taking $m=1,a_{1,i}=2^i$.
 A: Below I show that $m$ cannot be constant.
The given system of $m$ equations can be reduced to the case of $m=1$, that is, to a single equation:
$$\sum_{j=1}^n y_j a'_{j} = \sum_{j=1}^n a'_{j}$$
where $a'_{j} := \sum_{i=1}^m a_{ij}b^{i-1}$ with $b:=n\cdot \max a_{ij}+1$. The key observation is that both sides of each equation
$$\sum_{j=1}^n y_j a_{ij} = \sum_{j=1}^n a_{ij}$$
is less than $b$ (under the constraint $\sum_j y_j=n$).
Then, by the negative result of Peter Taylor, we have
$$\frac{(n\cdot\max a_{ij} + 1)^m}{n} > \max a_{ij}\cdot \frac{b^m-1}{b-1} \geq \max a'_{j} \in \Omega( n^{-3/2} 2^n ),$$
implying that $\max a_{ij} \in \Omega( n^{-1-1/(2m)} 2^{n/m} )$, which would contradict the given asymptotic bound if $m$ is constant.
A: Yes, we can get $\exp(\omicron(n))$.
Assume for a moment that $n$ is a perfect square and $m=\sqrt{n}$.
The general case is essentially the same, just a bit more complicated.
The idea is to partition those $n=m^2$ variables $y_1,\ldots\, y_n$ in $m$ blocks of $m$ digits in base $b=n+1$. Define
$$a_{ij} = \left\{  
  \begin{array}{ll} 
     b^{\,j-m(i-1)-1} & \text{if } \; m(i-1) \lt j \leq mi \\ 
     0 & \text{otherwise}
  \end{array} 
  \right.
$$
For example if $n=9$ we have $m=3$ and $b=10$ and
$$ A = \left( 
       \begin{array}{rrr|rrr|rrr}
         1 & 10 & 100 & 0 & 0 & 0 & 0 & 0 & 0 \\
         0 & 0 & 0 & 1 & 10 & 100 & 0 & 0 & 0 \\
         0 & 0 & 0 & 0 & 0 & 0 & 1 & 10 & 100 \\
       \end{array}  
       \right) $$
It is not hard to see that such $A$ only admits the trivial solution where all the $y_j$ are equal to $1$, because $0 \le y_j \lt n + 1 = b$.
Now $\max a_{ij} = b^{m-1} \le b^m$  and thus
$$
2^m \cdot \max a_{ij} \le 2^m b^m = (2b)^m 
= \exp(m \, \ln(2b))
= \exp(\sqrt{n} \,\ln(2n+2)) 
$$
and $\sqrt{n} \,\ln(2n+2)$ is in $\omicron(n)$.
The question actually asked for positive integer entries $a_{ij}$ rather than just non-negative entries.
But because $\sum_{j=1}^n y_j = n$, we can instead use $a'_{ij} = a_{ij} + 1$, and since
$\,\max a'_{ij} = b^{m-1} + 1 \le b^m$
we arrive at the same bound.
Edit (based @joro's comment)
In summary, we have $\sqrt{n}$ equations with $\max a_{ij} \sim n^{\sqrt{n}}$.
