5

Let $A$ be a strictly substochastic matrix (i.e., nonnegative elements and row sums strictly less than one) and let $M = (I-A)^{-1}.$ Since $I-A$ is an M-matrix, I know that matrix $M$ has all nonnegative entries. Simulations also show that $m_{ii} \geq m_{ji}$ for all $i,j$. Is that true in general?

This is true in the 2x2 case, since letting $\Delta$ be the determinant of $I-A$ (which is positive), then $m_{11} = (1-a_{22}) / \Delta$ while $m_{21} = a_{21} / \Delta$, and so $a_{21} + a_{22} < 1$ implies that $m_{11} > m_{21}$, and similarly $m_{22} > m_{12}$.

It is also easy to show it directly in the 3x3 case. Perhaps one can show by induction, but I imagine that this is a well known result?

Andres
  • 85

3 Answers3

2

Let me add a simple proof. Suppose that $m_{ji}>m_{ii}$ for certain $j\neq i$. Without loss of generality, we can assume additionally that $m_{ji}$ is maximal among all the element $m_{ki}$. Now $M=(I-A)^{-1}$ implies that $(I-A)M=I$ and hence $M=AM+I$. In particular we have that $m_{ji}=\sum_k a_{jk}m_{ki}$ because $j\neq i$. Hence $m_{ji}\leq \left(\sum_k a_{jk}\right)m_{ji}$. Since $\sum_k a_{jk}<1$ by assumption, we obtain that $m_{ji}\leq 0$. Since all entries of $M=\sum_n A^n$ are nonnegative, this contradicts $m_{ji}>m_{ii}$.

The fact that all entries of $M$ are nonnegative can be shown without using an infinites series and the concept of convergence. Suppose that $m_{rs}$ is the minimal element of $M$. Then using $M=AM+I$ again, we find that $m_{rs}\geq \sum_t a_{rt}m_{ts}\geq\left(\sum_t a_{rt}\right) m_{rs}$. Again the fact that $\sum_t a_{rt}<1$ implies that $m_{rs}\geq0$ and hence all elements of $M$ are nonnegative. As a consequence, $M=AM+I$ now implies that $m_{ii}\geq1$...

Helmut
  • 4,944
1

It's probably best to do this with a probabilistic argument. $A$ represents the transient portion of an absorbing state Markov chain, where each state has direct non-zero probability of absorbtion (hence $A$ is strictly sub-stochastic).

$m_{i,i} = \mu$ counts the expected number of visits to state $i$, given a start at $i$ before being absorbed and counting starts at 1 i.e. $m_{i,i}=\sum_{k=0}^\infty \mathbf e_i^TA^k\mathbf e_i=1 +\sum_{k=1}^\infty \mathbf e_i^TA^k\mathbf e_i$

$m_{j,i}$ counts expected number of visits to state $i$, given a start at $j$ before being absorbed and counting starts at 0. That is $m_{j,i}=\sum_{k=0}^\infty \mathbf e_j^TA^k\mathbf e_i=\sum_{k=1}^\infty \mathbf e_j^TA^k\mathbf e_i$. Furthermore there is probability $p \in (0,1]$ that we are absorbed before ever reaching state $i$ from $j$ thus $m_{j,i} = (1-p)\mu \lt \mu= m_{i,i}$

user8675309
  • 10,034
1

This follows from the proof of Theorem 1.3 (i) in Johnson and Smith's "Inverse M-Matrices II" published in Linear Algebra and its Applications 435 (2011) 953–983.

The proof of 1.3 (i) shows that if $R$ is an M-matrix and is diagonally dominant of its rows then matrix $S \equiv R^{-1}$ satisfies $|s_{ii}| > |s_{ji}|$ for all $i$ and all $j \neq i$.

Since $I-A$ is an M-matrix and is diagonally dominant of its rows, then it follows that $M \equiv (I-A)^{-1}$ satisfies $m_{ii} > m_{ji} \geq 0$ for all $i$ and all $j \neq i$.

Andres
  • 85