Skip to main content
added 202 characters in body
Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

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]$, eigenvalues of $A^{-1}$these bounds may be exponential be in $n$.

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$. I did not check carefully, but it seems that for $A$ with entries in $[-n,n]$, eigenvalues of $A^{-1}$ may be exponential be in $n$.

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$.

Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

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$. I did not check carefully, but it seems that for $A$ with entries in $[-n,n]$, eigenvalues of $A^{-1}$ may be exponential be in $n$.