Say I have a non-negative square $n\times n$ irreducible stochastic matrix $A$ (i.e., each column sums to 1), for which the following holds: $$A_{ij} > 0 \iff A_{ji} > 0.$$ I know that no more than 15 entries per row are positive, and if $A_{ij} > 0$, then $\frac{1}{15} \leq A_{ij} \leq \frac{6}{11}$ (this last bound is less important, the point is that it's $< 1$). For instance, this implies that $A^2_{ii} \geq 1/15$.

It's easy to prove that, for each $k > 0$, the smallest positive entry of $A^k$ is $\geq \frac{1}{15^k}$. It is also easy to prove that the greatest entry of $A^k$ will be $\leq \frac{6}{11}$, as $$A_{ij}^k \leq A^{k-1}_i(A^{k-1})^j \leq \max A_i^{k-1}.$$

However I would like to either a) give a better bound on the smallest positive entry, b) give a bound on the greatest entry that also varies in the exponent. The reason to do this is to give a good bound on the principal ratio $\gamma$ (defined below) of the Perron vector $x$ of $A$, i.e., the positive vector satisfying $Ax=x$ and $||x||_1 = 1$.

We know that there's some exponent $d < n$ such that $A^d$ is positive. By Minc's Nonnegative matrices, Theorem 3.1, one has $$\gamma := \max_{i,j}\frac{x_i}{x_j} \leq \max_{s,t,j}\frac{A^d_{sj}}{A^d_{tj}},$$ but the best we have with the previous discussion is $\rho \leq 6\cdot 15^d / 11.$

So, apart from a better entrywise bound, is it possible that I can get a (perhaps constant?) bound on $\gamma$?

Some of the references I'm working with are:

There are a number of related questions here on MO:

  • $\begingroup$ Welcome to MO. I wonder if $t$ is the best variable name to use for an exponent of a matrix -- at first I got confused because it looked like the transpose ... $\endgroup$ – gmvh Apr 17 '20 at 15:14
  • 1
    $\begingroup$ @gmvh I fixed it $\endgroup$ – Enric Florit Apr 17 '20 at 15:22

Your Answer

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

Browse other questions tagged or ask your own question.