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?

  • $\begingroup$ I thought of rewriting it as $P=(P-\lambda I)+\lambda I$ where $0<\lambda<1$. But now, the sums of rows and columns in $(P-\lambda I)$ is $1-\lambda$ ? $\endgroup$ – Srinivas K Feb 24 '15 at 19:57
  • $\begingroup$ Thanks a lot. Yes, but the problem is that $P-\lambda I$ might not be the convex combination of other permutation matrices. $\endgroup$ – Saeid Haghighatshoar Feb 25 '15 at 6:56
  • 1
    $\begingroup$ If $Q$ is a permutation matrix and $0<a<1$ such that all entries of $P-aQ$ are non-negative then $P=(1-a)\frac{P-aQ}{1-a}+aQ$. Notice that $\frac{P-aQ}{1-a}$ is doubly stochastic. Thus, a convex combination of permutations. Notice that $Q$'s weight is $a>0$. The converse is also true. $\endgroup$ – Daniel Aug 21 '18 at 0:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.