Suppose that I have a "sub-stochastic" matrix, namely, for an $n\times n$ matrix $A$ with nonnegative entries such that for any $i$, $\sum_j a_{ij}\leq 1$ and there exists some $i$ with $\sum_j a_{ij}<1$.

It is not hard to see the spectral radius of $A$, $\rho(A)<1$. I am wondering how can I bound $\rho(A)$ tightly in terms of entries of $A$ (e.g., the minimal nonzero entry of $A$). One can make reasonable assumptions (e.g. irreducibility).

Note that I do NOT have that for any $i$, $\sum_j a_{ij}<1$. That case would be much easier.


  • 2
    $\begingroup$ Not everyone knows what spectral radius is without looking at Wikipedia. For the curious but lazy, the spectral radius is the absolute maximum of the eigenvalues ( $\rho(A) = \max(|\lambda_i|)$ ). $\endgroup$ – user834 May 10 '12 at 7:23
  • 9
    $\begingroup$ According to your definition, a diagonal matrix with 1 as one of the diagonal entries and (say) 0.5 as the rest of the entries is a "sub-stochastic" matrix. But its spectral radius is 1. $\endgroup$ – Robin Kothari May 10 '12 at 16:01
  • 2
    $\begingroup$ @Robin. Nice catch. I realized this problem after the post. However, if you assume irreducibility, the problem disappears. $\endgroup$ – user29271 May 14 '12 at 23:04

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.