8
$\begingroup$

Suppose that $M$ is an $n \times n$ matrix where each entry is a positive integer. Then $M$ is Perron-Frobenius and so has unique largest real eigenvalue $\lambda_{\textrm{PF}}$.

Does an upper bound on $\lambda_{\textrm{PF}}$ give an upper bound on each of the entries of $M$? That is, does $\lambda_{\textrm{PF}}$ being small imply that each entry of $M$ is too?

Note that when $n = 2$: $$ \lambda_{\textrm{PF}} = \frac{1}{2}\left(a + d + \sqrt{a^2 - 2ad + d^2 + 4bc}\right) $$ and so $a, b, c, d \leq \lambda_{\textrm{PF}}^2$.

Additionally, if we remove the requirement that the entries of $M$ be integers then the answer is no as for every $k \geq 1$ the matrix $$ \left( \begin{matrix} 1 & k \\ k^{-1} & 1 \end{matrix} \right) $$ has Perron-Frobenius eigenvalue 2.

$\endgroup$
19
$\begingroup$

This is true. Indeed, you can estimate the sum of all $n^2$ elements of $A$ rather than individual elements. (Thanks to thomashennecke for observing this, my original answer dealt with the row sums of $A$ instead of the sum of all $n^2$ elements of $A$.) Moreover, you do not need the elements to be integer; it suffices to have them uniformly bounded away from $0$.

Write $A=(a_{ij})$ and let $x=(x_1,\ldots,x_n)$ be an eigenvector corresponding to the eigenvalue $\lambda_{\rm PF}$. Suppose, for instance, that $a_{ij}\ge 1$ for all $i,j\in[n]$. For each $i\in[n]$ you then have $$ \lambda_{\rm PF} x_i=\sum_{j=1}^n a_{ij}x_j \ge \|x\|_1, $$ whence $x_i\ge\lambda_{\rm PF}^{-1}\|x\|_1$. As a result, letting $\xi:=\min\{x_j\colon j\in[n]\}$, $$ \lambda_{\rm PF}\|x\|_1 = \sum_{i=1}^n\lambda_{\rm PF}x_i = \sum_{i=1}^n\sum_{j=1}^n a_{ij}x_j \ge \xi \sum_{i,j=1}^n a_{ij} \ge \lambda_{\rm PF}^{-1} \|x\|_1 \sum_{i,j=1}^n a_{ij}. $$ Consequently, $$ \sum_{i,j=1}^n a_{ij} \le \lambda_{\rm PF}^2. $$

Equality is attained, for instance, for the all-$1$ matrix.

$\endgroup$
  • $\begingroup$ Thanks, Do you know of any reference for this result? $\endgroup$ – Mark Bell May 9 '14 at 13:17
  • $\begingroup$ No, I have never heard of it before. $\endgroup$ – Seva May 9 '14 at 13:25
  • 2
    $\begingroup$ Do we need the second step in the second row of inequalities? It seems we may sum over all entries of $Ax$ to get $$\frac{\lambda_{PF}^2}{\min_{i,j} a_{ij}} \ \geq \ \sum_{i,j = 1}^n a_{ij} $$ in general!? $\endgroup$ – thomashennecke May 12 '14 at 13:25
  • $\begingroup$ @thomashennecke: seems you are right - nice observation! Why not posting it as yet another answer? $\endgroup$ – Seva May 12 '14 at 13:37
  • $\begingroup$ @Seva: Hm ... I think, the changes are so minor, it properly belongs here as comment or edit to the answer. $\endgroup$ – thomashennecke May 12 '14 at 14:18
4
$\begingroup$

This is a little late in the game, but here is another estimate. Let $N$ be the maximal entry. Then the minimal entry of $A^3$ is at least $N + n^2-1$: the $ij$th entry of $A^3$ is the sum of terms of the form $A_{ik}A_{kl} A_{lj}$; if the max occurs at $kl$, we obtain the result (since the entries are all at least one).

Thus every entry of $A^3$ is at least $N + n^2-1$, so its Perron eigenvalue is at least $n(N+n^2-1)$ (where $n$ is the size of the matrix). Hence $\lambda_{PF} \geq (n(N+n^2-1))^{1/3} \geq \max \{n, (nN)^{1/3}\}$.

$\endgroup$
2
$\begingroup$

An alternative approach is that, setting $\lambda = \lambda_{PF}$, the limit $\lim_{k \to \infty} \frac{A^{k}}{\lambda^{k}}$ exists, and is an idempotent matrix of rank $1,$ so of trace $1$. It is quite interesting to note that multiplying $A$ by a permutation matrix may make a difference here. If we multiply $A$ by a permutation matrix, we may suppose that its largest entry is on the main diagonal, so that for some $r,$ we have $a_{ij} \leq a_{rr}$ for all $i,j.$ Then for every $k,$ it follows easily that the $(r,r)$-entry of $A^{k}$ is at least $a_{rr}^{k}.$ Since $\lim_{k \to \infty} {\rm trace}(\frac{A^{k}}{\lambda^{k}})= 1$, we must have $a_{rr} \leq \lambda.$ Hence if the largest entry of $A$ is somewhere on its main diagonal, we have $a_{ij} \leq \lambda_{PF}$ for all $i,j.$ Notice, though that while pre and post multiiplying $A$ by permutation matrices does not affect the operator norm (wrt Euclidean norm on vectors), it may change the spectral radius.

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