2
$\begingroup$

Quasi-stochastic

In order not to make the title too long I used the term Quasi-Stochastic with this meaning: a quasi-stochastic matrix $Q$ is a square matrix $Q = (q_{i,j}) \in \mathbb{R}^{n \times n}$ where all entries are bound to the interval $q_{i,j} \in ]0,1[$ and where all rows sum to a number lower than 1 (strictly):

$\sum_{j=1}^n q_{i,j} < 1$

This condition determines what I call the quasi-stochastic thing.

The question: specific case

Consider a quasi-stochastic matrix $Q$ and its eigenvalues $\lambda_i$. I would like to understand if the following equation holds:

$ |\lambda_i| < 1, \forall i = 1 \dots n $

Or, less strictly

$ |\lambda_i| \leq 1, \forall i = 1 \dots n $

Rationale

There is a reason why I ask. If you consider a Markov chain and its transition probabilities matrix $P$, if the chain is ergodic than the matrix has all its eigenvalues in the unit circle with one eigenvalue on the edge of it. If create a reduced version of this matrix, what happens to the eigenvalues? Using Matlab I could try some experiments and experienced that all eigenvalues are in the circle and the eigenvalue which is $\lambda_1 = 1$ falls to $\lambda_1 < 1$. However how to get mathematical evidence?

  • 0
    Ah, yeah, thankyou :)2012-06-04

1 Answers 1

3

Yes it is indeed true. Note that $\lVert A \rVert_{\infty} = \text{ the maximum absolute row sum of the matrix} $ In your case, the maximum absolute row sum of the matrix is same as the maximum row sum of the matrix which in turn is strictly less than $1$. More importantly, if $\lambda_k$ is any eigenvalue of the matrix, then we have that $\dfrac1{\lVert A^{-1} \rVert} \leq \lvert \lambda_k \rvert \leq \lVert A \rVert, \text{ for all eigenvalues } \lambda_k$ for any valid matrix norm. In particular, choosing the matrix norm as $\infty$-norm, we get what you want.