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.

$\endgroup$
15
  • 6
    $\begingroup$ What about $A=\begin{pmatrix} 1 & n\\ 1 &1\end{pmatrix}$? $\endgroup$
    – Mike Jury
    Aug 22 '14 at 13:09
  • 1
    $\begingroup$ You can (and should) use $\TeX$ in your questions, answers and comments. $\endgroup$
    – abx
    Aug 22 '14 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
    Aug 22 '14 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
    Aug 22 '14 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
    Aug 22 '14 at 16:07
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.