<p>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}&lt;1$. </p>

<p>It is not hard to see the spectral radius of $A$, $\rho(A)&lt;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). </p>

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

<p>Thanks!</p>

CC BY-SA 3.0
2012-05-10T07:23:25.983Z
Not everyone knows what spectral radius is without looking at Wikipedia.  For the curious but lazy, the [spectral radius](http://en.wikipedia.org/wiki/Spectral_radius) is the absolute maximum of the eigenvalues ( $\rho(A) = \max(|\lambda_i|)$ ).
user834
CC BY-SA 3.0
2012-05-10T16:01:41.003Z
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.
Robin Kothari
CC BY-SA 3.0
2012-05-14T23:04:55.283Z
@Robin. Nice catch. I realized this problem after the post. However, if you assume irreducibility, the problem disappears.
user29271
<co.combinatorics><linear-algebra><matrices>
Bounding the spectral radius of a sub-stochastic matrix
user29271
# Bounding the spectral radius of a sub-stochastic matrix

(Asked by: username_0 on 2012-05-07)

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.

Thanks!

**Tags:** co.combinatorics, linear-algebra, matrices
> **Comments:**
> **username_1**: Not everyone knows what spectral radius is without looking at Wikipedia.  For the curious but lazy, the [spectral radius](http://en.wikipedia.org/wiki/Spectral_radius) is the absolute maximum of the eigenvalues ( $\rho(A) = \max(|\lambda_i|)$ ).  
> **username_2**: 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.  
> **username_0**: @Robin. Nice catch. I realized this problem after the post. However, if you assume irreducibility, the problem disappears.  

---

## 0 answers

