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 RHS 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?

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?

From Birkhof 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.

I have the following question: 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=[1/2 1/2; 1/2 1/2] then P can be written as P=1/2[1 0; 0 1] + 1/2 [0 1; 1 0]. In this case both [1 0; 0 1] and [0 1; 1 0] 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?

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 RHS 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?