# Does small Perron-Frobenius eigenvalue imply small entries for integral matrices?

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.

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.

• Thanks, Do you know of any reference for this result? – Mark Bell May 9 '14 at 13:17
• No, I have never heard of it before. – Seva May 9 '14 at 13:25
• 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!? – thomashennecke May 12 '14 at 13:25
• @thomashennecke: seems you are right - nice observation! Why not posting it as yet another answer? – Seva May 12 '14 at 13:37
• @Seva: Hm ... I think, the changes are so minor, it properly belongs here as comment or edit to the answer. – thomashennecke May 12 '14 at 14:18

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

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.