Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 11 down vote accepted

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.

share|improve this answer
    
Thanks, Do you know of any reference for this result? –  Mark Bell May 9 at 13:17
    
No, I have never heard of it before. –  Seva May 9 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 at 13:25
    
@thomashennecke: seems you are right - nice observation! Why not posting it as yet another answer? –  Seva May 12 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 at 14:18
show 1 more comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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