On the decomposition of stochastic matrices as convex combinations of zero-one matrices

Question

Let "stochastic" matrix be the matrix whose rows sum to one and deterministic matrix be a stochastic matrix whose all rows consist of a one and zero.

For example $\left [ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{array} \right] $ is a deterministic matrix.

I am trying to show that any stochastic matrix can be written as a convex combination of deterministic matrices.

Answer 1

Constructive proof:

Consider some nonzero substochastic matrix $P$ with equal-row-sums. Call $P_{is(i)}$ one of the minimal nonzero entries of row $i$, and consider the deterministic matrix $D$ such that $D_{is(i)}=1$ for every $i$ and $D_{ij}=0$ otherwise. Finally, define $m(P)=\min\{P_{ij}\mid P_{ij}\ne0\}$.

Then $P-m(P)D$ is a substochastic matrix with equal-row-sums and with at least one more zero entry than $P$.

Starting from some stochastic matrix $P$ and iterating the step $P\mapsto P-m(P)D$ at most a finite number $N$ of times, one gets a sequence $(P_k)_{0\leqslant k\leqslant N}$ of substochastic matrices with equal-row-sums and a sequence $(D_k)_{0\leqslant k\leqslant N-1}$ of deterministic matrices such that $P_0=P$, $P_N=0$, and $P_{k+1}=P_k-m(P_k)D_k$ for every $0\leqslant k\leqslant N-1$.

This yields the decomposition of $P$ as a convex combination of deterministic matrices $$P=\sum_{k=0}^{N-1}m(P_k)D_k.$$

Example: Consider the stochastic matrix $$P=\frac1{12}\begin{pmatrix}2&4&6\\ 2&2&8\\ 3&3&6\end{pmatrix},$$ then a sequence of reductions, showing the selected entries on $12\cdot P$ at each step, is $$ \begin{pmatrix}\underline 2&4&6\\ \underline2&2&8\\ \underline3&3&6\end{pmatrix}\ \begin{pmatrix}0&\underline4&6\\ 0&\underline2&8\\ \underline1&3&6\end{pmatrix}\ \begin{pmatrix}0&\underline3&6\\ 0&\underline1&8\\ 0&\underline3&6\end{pmatrix}\ \begin{pmatrix}0&\underline2&6\\ 0&0&\underline8\\ 0&\underline2&6\end{pmatrix}\ \begin{pmatrix}0&0&\underline6\\ 0&0&\underline6\\ 0&0&\underline6\end{pmatrix}$$ wich yields the decomposition $$P=\frac16\begin{pmatrix}1&0&0\\ 1&0&0\\ 1&0&0\end{pmatrix}+ \frac1{12}\begin{pmatrix}0&1&0\\ 0&1&0\\ 1&0&0\end{pmatrix}+ \frac1{12}\begin{pmatrix}0&1&0\\ 0&1&0\\ 0&1&0\end{pmatrix}+ \frac16\begin{pmatrix}0&1&0\\ 0&0&1\\ 0&1&0\end{pmatrix}+ \frac12\begin{pmatrix}0&0&1\\ 0&0&1\\ 0&0&1\end{pmatrix}. $$

Answer 2

The proof for the assertion can be found in "Markov Chains as Random Input Automata" by A. S. Davis. It is an extension of the Birkhoff-von Neumann theorem. Did's answer is based on the constructive proof of this theorem.