This might be related to [counting hamiltonian cycles](https://mathoverflow.net/questions/429025/counting-hamiltonian-cycles-in-graph-and-finding-a-coefficient-of-polynomial).


@**Peter Taylor** gave [negative result](https://mathoverflow.net/a/428266/12481) 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$.



Only trivial solutions to system of linear diophantine equations possibly related to hamiltonian cycles in graphs
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}}$.


