Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $M$ be a row substochastic matrix, with at least one row having sum less than 1. Also, suppose $M$ is irreducible in the sense of a markov chain. Is there an easy way to show the largest eigenvalue must be strictly less than 1? I hope that this result is true as stated. I know that Cauchy interlacing theorem gives me $\leq$,

share|cite|improve this question
I think you are missing a condition, else you could take $M$ to be the 2 by 2 diagonal matrix with entries 1/2 and 1. The largest eigenvalue of this $M$ is 1. – Byron Schmuland May 4 '11 at 0:59
Sorry I meant to add irreducibility. Thanks for the correction – SKS May 4 '11 at 1:19

You can try completing your matrix to a Markov chain, adding a self loop at the additional state. The new Markov chain is irreducible and aperiodic and so has a unique stationary distribution, which is concentrated on the additional state. It is also the unique eigenvector with eigenvalue at least $1$.

Now take a purported eigenvector for your original matrix with eigenvalue $1$, and add a zero coordinate. The result is an eigenvector for the Markov chain, contradicting the properties we listed above.

In effect, you have a Markov chain with an invisible absorbing state, which is actually reachable from any other state. This ensures that in the long run the state will be reached, and so applying your matrix lots of times on any given vector will yield the zero vector. So all eigenvalues must be less than 1 in magnitude.

share|cite|improve this answer
I'm not quite seeing that the sub stochastic eigenvector, when extended with a zero coordinate becomes an eigenvector of the new markov chain, particularly when looking at what happens to the last coordinate of the eigenvector upon multiplication – SKS May 4 '11 at 22:25
The last coordinate is zero in both "input" and "output", since the corresponding row is $0,\ldots,0,1$ (the last entry corresponding to the added state). – Yuval Filmus May 4 '11 at 23:48
Something is bothering me about your argument. For instance, if you add an absorbing state the resulting chain is certainly not irreducible. – Byron Schmuland May 5 '11 at 0:04
@Byron I guess you're right about that! But it's still true that there is only one stationary probability since wherever you start, you'll almost surely reach the absorbing vertex. This is basically the argument in your answer. – Yuval Filmus May 5 '11 at 1:25

This is essentially Yuval's probabilistic argument with the probability removed. The goal is to show that powers of $M$ converge to zero.

For any state $i$ and integer $n\geq 0$, let $r^n_i=\sum_k M^n_{i k}$ denote the $i$th row sum of $M^n$. For $n=1$, we write $r_i$ rather than $r^1_i$. Since $M$ is substochastic we have $0\leq r^n_i\leq 1$.

Let $k^*$ be an index with $r_{k^*}<1$, and note that for $n\geq 1$
$$r^n_{k^*}=\sum_k M_{k^* k}\ r_k^{n-1}\leq \sum_k M_{k^* k} =r_{k^*}<1.$$

By irreducibility, for any $i$, there is an $m$ with $M_{i k^*}^m>0$. In fact, if $M$ is $N\times N$ matrix, and $i\neq k^*$ then we can assume $m<N$. (Take the shortest path from $i$ to $k^*$ with positive "probability").
Since $M_{i k}^m$ puts positive weight on the index $k=k^*$, we have $$r^N_i=\sum_k M^m_{i k}\ r^{N-m}_k < r^m_i \leq 1.$$

That is, every row sum of $M^N$ is strictly less than one. Now you can show that $M^{jN}\to 0$ as $j\to \infty$ and this shows that $M^N$ (and hence $M$) cannot have any eigenvalue with modulus 1.

share|cite|improve this answer

A bit late to the game, but I thought of this proof.

Suppose $A$ is an irreducible sub-stochastic matrix and $\lambda$ is the the Perron-Frobenius eigenvalue of $A$ (i.e. $\rho\left(A\right) = \lambda$) with $v$ the corresponding eigenvector normalized such that $\|v\|_{1} = 1$. By the Perron-Frobenius theorem for irreducible non-negative matrices, the entries of $v$ must be positive. Using this, we have the following.

\begin{align} |\lambda| &= \|\lambda v\|_{1} \\ &= \|vA\|_{1} \\ &= \sum_j\sum_k v_jA_{jk} \end{align} Let $\epsilon_j \doteq \frac{1}{N}\left(1 - \sum_{k=1}^N A_{jk}\right)$. If we add $\epsilon_j$ to each element of the $j$th row of A, the row sum will become one. Let $\boldsymbol\epsilon$ be the row vector containing the values of $\{\epsilon_j\}$. \begin{align} |\lambda| &= \sum_j \sum_k v_j\left(A_{jk} + \epsilon_j - \epsilon_j\right) \\ &= \sum_j \sum_k v_j\left(A_{jk} + \epsilon_j\right) -\sum_j \sum_k v_j \epsilon_j \\ &= \left\|v\left(A + \boldsymbol\epsilon^T\mathbf{1}\right)\right\|_1 - N \left(\boldsymbol\epsilon\cdot v\right) \end{align}

We define $\hat A \doteq A + \boldsymbol\epsilon^T\mathbf{1}$ and note that it is a proper stochastic matrix. Since $v$ is positive and $\boldsymbol\epsilon$ is non-negative with at least one positive entry we have $\boldsymbol\epsilon\cdot v > 0$. \begin{align} |\lambda| &= \left\| v \hat A \right\|_{1} - N \left(\boldsymbol\epsilon\cdot v\right) \\ &= 1 - N \left(\boldsymbol\epsilon\cdot v\right) \\ &< 1 \end{align}

share|cite|improve this answer
I might have missed something but I think your argument requires the matrix to be primitive, which may not be the case here. – Aiden Aug 26 '15 at 5:29
@Aiden Do you mean that being primitive is a necessary condition to invoke the Perron-Frobenius Theorem? That was not my understanding, but I could be wrong. – Daniel Johnson Aug 30 '15 at 15:35
I'm sorry your proof is right. But it is just the assertion that "the entries of $v$ must be positive" is a bit too strong. I think it should be we can choose it to be positive to be more rigorous. The "must" leads me to think about period 1 thing. Anyway I'am just being captious and making excuses honestly. your proof is a beautiful one. – Aiden Aug 30 '15 at 16:17

Your Answer


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.