# Random uniform sampling of position restricted permutations

Is there any efficient algorithm which is able to generate nearly uniform samples of permutations in case of position restrictions?

Consider $N \times N$ restriction matrices $R$, that is matrices over $\{0,1\}$. Each such $R$ defines a set of permutations $\Pi_R$ according to

$\qquad\displaystyle \pi \in \Pi_R \iff \forall i \in [1..n].\ \pi(i) = j \implies R_{i,j} = 1$.

Note that $R$ is not permutation matrix but a general restriction matrix. I want to sample uniformly from $\Pi_R$ given $R$.

So far I am using Hungarian's assignment algorithm to produce random permutations consistent with restriction matrix $R$, but these permutations are significantly non-uniformly sampled.

Examples:

• Every $R$ that has one one per row and column admits only a single permutation.
• For

$\qquad\displaystyle R = \left( \begin{array}{ccc} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array} \right)$

there are only two permutations: $\pi_1 = (2 1 3)$ and $\pi_2 = (2 3 1)$.

• If $R$ contains only ones, $\Pi_R$ is the set of all permutations.

## 1 Answer

I'll answer both the question as it currently stands, and the original version of the question.

## The current question

Your question is basically asking for a way to sample uniformly at random from the set of perfect matchings of a given bipartite graph. In particular, we have $N$ nodes on the left side corresponding to the $N$ rows of $R$, and $N$ nodes on the right side corresponding to the $N$ columns of $R$. Draw an edge between node $i$ (on the left) and node $j$ (on the right) when $R_{i,j}=1$. This gives a bipartite graph $G$. Now there's a bijection between the perfect matchings of $G$ and the permutations in $\Pi_R$, so we want to sample uniformly at random from the perfect matchings of $G$.

The following question refers to algorithm for exactly that problem: Sampling perfect matching uniformly at random. In particular, there are existing algorithms that approximate sampling from the uniform distribution (i.e., their distribution is almost uniform).

## The original question

Originally, the question imposed the stronger restriction that $\pi(i)=j \Longleftrightarrow R_{i,j}=1$. Here's the solution to that version of the problem.

Theorem. If $R$ is a permutation matrix, there is a single permutation $\pi$ that is compatible with $R$. If $R$ is not a permutation matrix, there is no permutation $\pi$ that is compatible with $R$.

Recall that a permutation matrix is a matrix that has exactly one 1 in every row and every column.

Proof of theorem. Consider any row, say row $i$. If it is all zeros (has no $1$), then there's no matching permutation ($\pi(i)$ has to equal something). If it has two or more $1$'s, there is no matching permutation (you can't have $\pi(i)=j$ and $\pi(i)=k$ where $j\ne k$). So for there to be a matching permutation, the row must have exactly one $1$. Since the row $i$ was arbitrary, this must be true of all rows. By symmetric, the same is true for all columns. QED.

You can easily recognize whether a matrix is a permutation matrix or not. Given a permutation matrix you can easily recover the corresponding permutation. Therefore, an algorithm to do what you want is trivial. The algorithm either outputs nothing (if $R$ is not a permutation matrix) or always deterministically outputs a single permutation (if $R$ is a permutation matrix).

For the example $3 \times 3$ matrix you gave in your question, there is no permutation that is consistent with that matrix. Your matrix has $R_{2,1}=1$ and $R_{2,2}=1$. By your conditions, this implies the requirements that $\pi(2)=1$ and $\pi(2)=2$. However, $1\ne 2$, so it is impossible to have a permutation $\pi$ that satisfies both of these requirements.