This representation is known as the Birkhoff-von Neumann decomposition, and it may not be unique in general.
The problem of computing the representation with the minimum number of terms has been shown to be NP-hard, but some heuristics for computing it are known [REF].This theorem can be extended for the general stochastic matrix with deterministic transition matrices [REF].