5
$\begingroup$

I believe the following statement should be true but somehow I don't see an argument:

For every integer $d>1$ there exists a constant $C=C(d)>1$ such that whenever $A$ is a $d \times d$ matrix with all entries integers $>0$, then

$$ \frac{1}{C} \|A\| \le \sigma(A) \le C \|A\|.$$

Here $\sigma(A)$ is the spectral radius of $A$ (which in this case is the Perron-Frobenius eigenvalue of $A$), and $\|A\|=\sup_{\|v\|=1} \|Av\|$ is the operator norm of $A$.

Does anyone see how to prove (or disprove) this statement?

Many thanks,

Ilya.

Improve this question
$\endgroup$
15
  • 6
    $\begingroup$ What about $A=\begin{pmatrix} 1 & n\\ 1 &1\end{pmatrix}$? $\endgroup$
    – Mike Jury
    Commented Aug 22, 2014 at 13:09
  • 1
    $\begingroup$ You can (and should) use $\TeX$ in your questions, answers and comments. $\endgroup$
    – abx
    Commented Aug 22, 2014 at 13:11
  • 2
    $\begingroup$ A slightly different way to view Mike's counterexample: if such a bound were true for positive matrices, then by taking limits it would also hold for positive semi-definite matrices, and then a nilpotent matrix would be a counterexample. But this also suggests that one can salvage some bound if one also controlled the condition number of the matrix. Indeed, since the product of the absolute values of the eigenvalues is equal to the product of the singular values (both are equal to $|\hbox{det}(A)|$), one can get some inequality involving the condition number. $\endgroup$
    – Terry Tao
    Commented Aug 22, 2014 at 15:08
  • 2
    $\begingroup$ The weaker conjecture is also false; for instance, conjugate $\hbox{diag}(1,2)$ by a large element of $SL_2({\bf Z})$, e.g. $\begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$. Note again that ill conditioning is the culprit. For integer non-singular matrices one has $|\hbox{det}(A)| \geq 1$, which doesn't give the bounds you want, but may give some other useful inequality for you. $\endgroup$
    – Terry Tao
    Commented Aug 22, 2014 at 15:21
  • 5
    $\begingroup$ In fact, your weaker conjecture is true! Let $a_{ij}$ be the $ij$ component of $A$, then $A e_j \geq a_{ij} e_i$ and $A e_i \geq e_j$ using the product partial ordering on ${\bf R}^d$. Iterating, we have $A^{2n} e_j \geq a_{ij}^n e_j$ for any $n$; sending $n$ to infinity we conclude that $a_{ij} \leq \sigma(A)^2$, and so $\|A\| \leq d \sigma(A)^2$ by Schur's test. $\endgroup$
    – Terry Tao
    Commented Aug 22, 2014 at 16:07

1 Answer 1

Reset to default
9
$\begingroup$

In fact, one can improve a little bit Terry's bound to show that $\|A\|\le(\sigma(A))^2$, and therefore $$ \sigma(A) \le \|A\| \le (\sigma(A))^2. $$ Indeed, this is an immediate consequence of the fact that for a matrix $A=(a_{ij})_{1\le i,j\le n}$ with positive integer entries one has $(\sigma(A))^2\ge\sum_{i,j=1}^n a_{ij}$, and the observation that if $x=(x_1,\ldots,x_n)$ is a unit-length vector, then $$ \|Ax\|^2 = \sum_{i=1}^n \Big( \sum_{j=1}^n a_{ij} x_j \Big)^2 \le \sum_{i=1}^n \Big( \sum_{j=1}^n a_{ij} \Big)^2 \le \Big( \sum_{i,j=1}^n a_{ij} \Big)^2, $$ implying $\|A\|\le \sum_{i,j=1}^n a_{ij}$.

Notice that by Mike Jury's example above, with $\sigma(A)=\sqrt n+1$ and $\|A\|>n$, the estimate $\|A\|\le(\sigma(A))^2$ is essentially best possible.

Also notice that the argument just presented actually works for any matrix $A$ with all entries greater than or equal to $1$; the assumption that the entries are integer is not really used.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .