1

Let $X$ be an $n\times n$ real matrix with coefficients $0\leq X_{ij}\leq 1$ such that $\sum_{j=1}^n X_{ij} \leq \bar{X}_i$, with $\bar{X}_i<1$ for all $i$. Consider the matrix $$ Y=(I-X)^{-1}, $$ where $I$ is the identity matrix. I would like to find bounds $\underline{Y}$ and $\overline{Y}$ such that $\underline{Y}\leq Y_{ij} \leq \overline{Y}$ for all $i,j$.

What I could find so far: $I-X$ is diagonally dominant so its eigenvalues are positive. In addition, its off-diagonal terms are nonpositive. It is therefore an $M$-matrix and the elements of its inverse are nonnegative. So one lower bound for $Y_{ij}$ is $\underline{Y}=0$, although there might be a tighter one.

user_lambda
  • 1,398

1 Answers1

1

As can be seen by considering the induced $\infty$-norm, the bound on the row-sums is enough to guarantee that the Neumann series $$ (I - X)^{-1} = \sum_{k=0}^\infty X^k $$ is convergent. Because $X^k$ is non-negative for all $k$, we have $Y_{ij} \geq X^{k}_{ij}$ for all $k$. In particular, if $X$ is irreducible, then we can guarantee that $$ Y_{ij} \geq \underline{Y} := r^{n}, $$ where $r = \min \{X_{ij} : X_{ij} \neq 0\}$ (the smallest non-zero entry of $X$). On the other hand, because the induced $\infty$-norm is multiplicative, we have $$ \left\| \sum_{k=0}^\infty X^k \right\|_\infty \leq \sum_{k=0}^\infty \|X\|_\infty^k = \frac{1}{1 - \|X\|_\infty}. $$ In other words, we have $$ Y_{ij} \leq \overline{Y} := (1 - \|X\|_\infty)^{-1} \leq \max_{i=1,\dots,n} (1 - \bar X_i)^{-1}. $$

Ben Grossmann
  • 225,327