7
$\begingroup$

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?

$\endgroup$
3
  • $\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$ Commented Feb 24, 2015 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$ Commented Feb 25, 2015 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$ Commented Aug 21, 2018 at 0:02

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.