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$

3 Answers 3

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$
5
  • $\begingroup$ Thanks, Do you know of any reference for this result? $\endgroup$
    – Mark Bell
    May 9, 2014 at 13:17
  • $\begingroup$ No, I have never heard of it before. $\endgroup$
    – Seva
    May 9, 2014 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$ May 12, 2014 at 13:25
  • $\begingroup$ @thomashennecke: seems you are right - nice observation! Why not posting it as yet another answer? $\endgroup$
    – Seva
    May 12, 2014 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$ May 12, 2014 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 and acknowledge you have read our privacy policy.

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