“Smallest” non-zero linear combination of vectors to obtain a non-negative vector

Question

We say that a vector $\mathbf{x}$ in $\mathbb{Z}^j$ is non-negative if it is of the form \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_j \\ \end{bmatrix}

where $x_{i} \geq 0$ for all $i=1,\dots,j$.

Suppose that $A$ is a $j \times j$ integer valued matrix with entries in the interval $[-n,n]$. What is the smallest possible value of $\delta_{j} \geq 0$ so that if $\varepsilon > 0$ then there exists an integer valued vector $\mathbf{x}_{A} \neq \mathbf{0}$ such that $A\cdot\mathbf{x}_{A}$ is non-negative, and $|\mathbf{x}_{A}| \leq C_{\epsilon}n^{\delta_{j} + \varepsilon}$ (here $C_{\epsilon}$ is a positive constant dependent only on $\varepsilon$)?

Note that we can find candidate values $\delta_{j} < \infty$, but I have not proved that here. I mainly seek a “non-trivial” upper bound for $\delta_{j}$.

Answer 1

I will show that $\delta_j\le j-1$. I suspect that in fact $\delta_j=j-1$, but I don't have a complete argument for it and it might be wrong.

Let $L$ be the lattice spanned by the columns of $A$ and let $b_1,\ldots,b_j$ be a reduced basis for the lattice. Let $B$ denote matrix with columns $b_1,\ldots,b_j$. There is a combination $\sum_{i=1}^jc_jb_j$ with positive coordinates and $c_j=O(1)$. Denote $c=(c_1,\ldots,c_j)^T$.

We have $A=BC$ for some $C\in GL_j(\mathbb Z)$ and $C_{kl}=O(n)$ (since $|A_{kl}|\le n$, $B_{kl}\in\mathbb Z$ and $B$ is reduced). Therefore the coefficients of $C^{-1}$ are $O(n^{j-1})$ and so are the coefficients of the vector $x_A=C^{-1}c$ (note that $Bc=Ax_A$ has positive coordinates). This shows that $\delta_j\le j-1$.

Answer 2

It is not a rigorous argument but just a thought.

Let $y:=Ax_A$ be a non-negative integer vector, then $x_A = A^{-1}y$ and thus $$|\lambda_1|\leq |\lambda_1||y| \leq |x_A|\leq |\lambda_j||y|,$$ where $\lambda_1$ and $\lambda_j$ are the smallest and the largest (by absolute value) eigenvalues of $A^{-1}$, which are reciprocals of the largest and smallest eigenvalues of $A$.

Also, we may note that for some $i$ there exists a nonzero integer vector $z:=\mathrm{det}(A)A^{-1}e_i$ such that $Az$ is non-negative. It follows that $$|x_A| \leq |z| \leq \mathrm{det}(A) |\lambda_j|.$$

I did not check carefully, but it seems that for $A$ with entries in $[-n,n]$, these bounds may be exponential be in $n$.