From the Birkhoff theorem, it is known that every doubly stochastic matrix can be written as a convex combination of permutation matrices, although this representation might not be unique.
Assume that a stochastic matrix is given. How can I find a permutation matrix that has a nonzero weight in at least one convex representation of the given stochastic matrix?
For example, if
$$P = \begin{bmatrix} \frac 12 & \frac 12\\ \frac 12 & \frac 12\end{bmatrix}$$
then $P$ can be written as follows
$$P = \frac 12 \begin{bmatrix} 1 & 0\\ 0 & 1\end{bmatrix} + \frac 12 \begin{bmatrix} 0 & 1\\ 1 & 0\end{bmatrix}$$
In this case, both permutation matrices in the right-hand side have the property that I wish because they receive nonzero weight in at least one convex representation of $P$.
Is there any simple algorithm to rapidly find at least one such permutation matrix for a given stochastic matrix?