On the imbedding problem for stochastic and doubly stochastic matrices (Q1100248)

It is shown that, for any \(n\times n\) stochastic matrix \(A=(a_{ij})\neq (\delta _{ij})\) which can be imbedded in a continuous time Markov chain, there exist distinct indices i,j such that for all k \(a_{ik}=0\) implies \(a_{jk}=0\), and likewise distinct indices i',j' such that, for all k, \(a_{ki'}=0\) implies \(a_{jk'}=0\). The present proof of this does not use Kingman and Williams' characterization of the patterns of zero entries which can occur in imbeddable stochastic matrices. In the analogous doubly stochastic situation the same result holds, even with ``implies'' replaced by ``if and only if''. The main result is that the set \({\mathcal F}\) of imbeddable stochastic (or doubly stochastic) matrices is a Lipschitz manifold with boundary. For any Markov chain leading to a matrix on the boundary of \({\mathcal F}\) the associated intensity matrix in the Kolmogorov differential equation has, at almost every time, at least one zero entry.