Return to Answer

This isn't a full answer by any means, but it includes a result which may be useful and applies it to get some constraints on the case $n=4$ which limit the possible 5-gate solutions to 2500 easily enumerable cases.

First the general result: in any solution which permutes $n$ objects, there must be at least $n-1$ swaps which have probability $\frac{1}{2}$.

Proof: consider the permutation representation of the permutations of order $n$. These are the $n\times n$ matrices $A_\pi$ satisfying $(A_\pi)_{i,j} = [i = \pi(j)]$. Consider a swap between $i$ and $j$ with probability $p$: this has representation $(1-p)I + pA_{(i j)}$ (using cycle notation to represent the permutation). You can think of multiplication by this matrix in terms of representation theory or in Markov terms as applying the permutation $(i j)$ with probability $p$ and leaving things unchanged with probability $1-p$.

The permutation network is therefore a chain of such matrix multiplications. We start with the identity matrix and the final result will be a matrix $U$ where $U_{i,j} = \frac{1}{n}$, so we are going from a matrix of rank $n$ to a matrix of rank $1$ by multiplications - i.e. the rank is decreasing by $n-1$.

Considering the rank of the matrices $(1-p)I + pA_{(i j)}$, then, we see that they're essentially identity matrices apart from a minor $\left[ \frac{1-p}{p} \frac{p}{1-p} \right]$ (excuse the lines - I don't want to spend half an hour working out how to typeset matrices without an array environment), so they have full rank unless $p=\frac{1}{2}$, in which case they have rank $n-1$.

Applying Sylvester's matrix inequality we therefore find that each swap decreases the rank only if $p=\frac{1}{2}$, and when this condition is met it decreases it by no more than 1. Therefore we require at least $n-1$ swaps of probability $\frac{1}{2}$.

Note that this bound can't be tightened because Anthony Leverrier's network achieves it.

Application to the case $n=4$. We already have solutions with 6 gates, so the question is whether solutions with 5 gates are possible. We now know that at least 3 of the gates must be 50/50 swaps, so we have two "free" probabilities, $p$ and $q$. There are 32 possible events (5 independent events each with two outcomes) and $4! = 24$ buckets each of which must contain at least one event. The events divide up as 8 with probability $\frac{pq}{8}$, 8 with probability $\frac{\overline{p}q}{8}$, 8 with probability $\frac{p\overline{q}}{8}$, and 8 with probability $\frac{\overline{p}\overline{q}}{8}$.

32 events into 24 buckets with no empty buckets implies that at least 16 buckets contain precisely one event, so at least two of the four probabilities given above are equal to $\frac{1}{24}$. Taking symmetries into account we have two cases: $pq = \overline{p}q = \frac{1}{3}$ or $pq = \overline{p}\overline{q} = \frac{1}{3}$.

The first case gives $p=\overline{p}=\frac{1}{2}$, $q=\frac{2}{3}$ (correction or $q=\frac{1}{3}$, unwinding the symmetry). The second case gives $pq=1-p-q+pq$, so $pq = p(1-p) = \frac{1}{3}$, which has no real solutions.

Therefore if there is a 5-gate solution we have four gates with probability $\frac{1}{2}$ and one gate with probability either $\frac{1}{3}$ or $\frac{2}{3}$. Wlog the first swap is $0\leftrightarrow 1$, and the second is either $0\leftrightarrow 2$ or $2\leftrightarrow 3$; the other three each have (no more than) five possibilities, because there's no point doing the same swap twice in a row. So we have $2\times 5^3$ swap sequences to consider and 10 ways of assigning the probabilities, leading to 2500 cases which could be enumerated and tested mechanically.

Update: Yuval Filmus and I have both enumerated and tested the cases and found no solutions, so the optimal solution for $n=4$ involves 6 gates, and examples of 6-gate solutions are found in other answers.

This isn't a full answer by any means, but it includes a result which may be useful and applies it to get some constraints on the case $n=4$ which limit the possible 5-gate solutions to 2500 easily enumerable cases.

First the general result: in any solution which permutes $n$ objects, there must be at least $n-1$ swaps which have probability $\frac{1}{2}$.

Proof: consider the permutation representation of the permutations of order $n$. These are the $n\times n$ matrices $A_\pi$ satisfying $(A_\pi)_{i,j} = [i = \pi(j)]$. Consider a swap between $i$ and $j$ with probability $p$: this has representation $(1-p)I + pA_{(i j)}$ (using cycle notation to represent the permutation). You can think of multiplication by this matrix in terms of representation theory or in Markov terms as applying the permutation $(i j)$ with probability $p$ and leaving things unchanged with probability $1-p$.

The permutation network is therefore a chain of such matrix multiplications. We start with the identity matrix and the final result will be a matrix $U$ where $U_{i,j} = \frac{1}{n}$, so we are going from a matrix of rank $n$ to a matrix of rank $1$ by multiplications - i.e. the rank is decreasing by $n-1$.

Considering the rank of the matrices $(1-p)I + pA_{(i j)}$, then, we see that they're essentially identity matrices apart from a minor $\begin{pmatrix}1-p & p \\ p & 1-p\end{pmatrix}$, so they have full rank unless $p=\frac{1}{2}$, in which case they have rank $n-1$.

Applying Sylvester's matrix inequality we therefore find that each swap decreases the rank only if $p=\frac{1}{2}$, and when this condition is met it decreases it by no more than 1. Therefore we require at least $n-1$ swaps of probability $\frac{1}{2}$.

Note that this bound can't be tightened because Anthony Leverrier's network achieves it.

Application to the case $n=4$. We already have solutions with 6 gates, so the question is whether solutions with 5 gates are possible. We now know that at least 3 of the gates must be 50/50 swaps, so we have two "free" probabilities, $p$ and $q$. There are 32 possible events (5 independent events each with two outcomes) and $4! = 24$ buckets each of which must contain at least one event. The events divide up as 8 with probability $\frac{pq}{8}$, 8 with probability $\frac{\overline{p}q}{8}$, 8 with probability $\frac{p\overline{q}}{8}$, and 8 with probability $\frac{\overline{p}\overline{q}}{8}$.

32 events into 24 buckets with no empty buckets implies that at least 16 buckets contain precisely one event, so at least two of the four probabilities given above are equal to $\frac{1}{24}$. Taking symmetries into account we have two cases: $pq = \overline{p}q = \frac{1}{3}$ or $pq = \overline{p}\overline{q} = \frac{1}{3}$.

The first case gives $p=\overline{p}=\frac{1}{2}$, $q=\frac{2}{3}$ (correction or $q=\frac{1}{3}$, unwinding the symmetry). The second case gives $pq=1-p-q+pq$, so $pq = p(1-p) = \frac{1}{3}$, which has no real solutions.

Therefore if there is a 5-gate solution we have four gates with probability $\frac{1}{2}$ and one gate with probability either $\frac{1}{3}$ or $\frac{2}{3}$. Wlog the first swap is $0\leftrightarrow 1$, and the second is either $0\leftrightarrow 2$ or $2\leftrightarrow 3$; the other three each have (no more than) five possibilities, because there's no point doing the same swap twice in a row. So we have $2\times 5^3$ swap sequences to consider and 10 ways of assigning the probabilities, leading to 2500 cases which could be enumerated and tested mechanically.

Update: Yuval Filmus and I have both enumerated and tested the cases and found no solutions, so the optimal solution for $n=4$ involves 6 gates, and examples of 6-gate solutions are found in other answers.

This isn't a full answer by any means, but it includes a result which may be useful and applies it to get some constraints on the case $n=4$ which limit the possible 5-gate solutions to 2500 easily enumerable cases.

First the general result: in any solution which permutes $n$ objects, there must be at least $n-1$ swaps which have probability $\frac{1}{2}$.

Proof: consider the permutation representation of the permutations of order $n$. These are the $n\times n$ matrices $A_\pi$ satisfying $(A_\pi)_{i,j} = [i = \pi(j)]$. Consider a swap between $i$ and $j$ with probability $p$: this has representation $(1-p)I + pA_{(i j)}$ (using cycle notation to represent the permutation). You can think of multiplication by this matrix in terms of representation theory or in Markov terms as applying the permutation $(i j)$ with probability $p$ and leaving things unchanged with probability $1-p$.

The permutation network is therefore a chain of such matrix multiplications. We start with the identity matrix and the final result will be a matrix $U$ where $U_{i,j} = \frac{1}{n}$, so we are going from a matrix of rank $n$ to a matrix of rank $1$ by multiplications - i.e. the rank is decreasing by $n-1$.

Considering the rank of the matrices $(1-p)I + pA_{(i j)}$, then, we see that they're essentially identity matrices apart from a minor $\left[ \frac{1-p}{p} \frac{p}{1-p} \right]$ (excuse the lines - I don't want to spend half an hour working out how to typeset matrices without an array environment), so they have full rank unless $p=\frac{1}{2}$, in which case they have rank $n-1$.

Applying Sylvester's matrix inequality we therefore find that each swap decreases the rank only if $p=\frac{1}{2}$, and when this condition is met it decreases it by no more than 1. Therefore we require at least $n-1$ swaps of probability $\frac{1}{2}$.

Application to the case $n=4$. We already have solutions with 6 gates, so the question is whether solutions with 5 gates are possible. We now know that at least 3 of the gates must be 50/50 swaps, so we have two "free" probabilities, $p$ and $q$. There are 32 possible events (5 independent events each with two outcomes) and $4! = 24$ buckets each of which must contain at least one event. The events divide up as 8 with probability $\frac{pq}{8}$, 8 with probability $\frac{\overline{p}q}{8}$, 8 with probability $\frac{p\overline{q}}{8}$, and 8 with probability $\frac{\overline{p}\overline{q}}{8}$.

32 events into 24 buckets with no empty buckets implies that at least 16 buckets contain precisely one event, so at least two of the four probabilities given above are equal to $\frac{1}{24}$. Taking symmetries into account we have two cases: $pq = \overline{p}q = \frac{1}{3}$ or $pq = \overline{p}\overline{q} = \frac{1}{3}$.

The first case gives $p=\overline{p}=\frac{1}{2}$, $q=\frac{2}{3}$ (correction or $q=\frac{1}{3}$, unwinding the symmetry). The second case gives $pq=1-p-q+pq$, so $pq = p(1-p) = \frac{1}{3}$, which has no real solutions.

Therefore if there is a 5-gate solution we have four gates with probability $\frac{1}{2}$ and one gate with probability either $\frac{1}{3}$ or $\frac{2}{3}$. Wlog the first swap is $0\leftrightarrow 1$, and the second is either $0\leftrightarrow 2$ or $2\leftrightarrow 3$; the other three each have (no more than) five possibilities, because there's no point doing the same swap twice in a row. So we have $2\times 5^3$ swap sequences to consider and 10 ways of assigning the probabilities, leading to 2500 cases which could be enumerated and tested mechanically.

This isn't a full answer by any means, but it includes a result which may be useful and applies it to get some constraints on the case $n=4$ which limit the possible 5-gate solutions to 2500 easily enumerable cases.

First the general result: in any solution which permutes $n$ objects, there must be at least $n-1$ swaps which have probability $\frac{1}{2}$.

Proof: consider the permutation representation of the permutations of order $n$. These are the $n\times n$ matrices $A_\pi$ satisfying $(A_\pi)_{i,j} = [i = \pi(j)]$. Consider a swap between $i$ and $j$ with probability $p$: this has representation $(1-p)I + pA_{(i j)}$ (using cycle notation to represent the permutation). You can think of multiplication by this matrix in terms of representation theory or in Markov terms as applying the permutation $(i j)$ with probability $p$ and leaving things unchanged with probability $1-p$.

The permutation network is therefore a chain of such matrix multiplications. We start with the identity matrix and the final result will be a matrix $U$ where $U_{i,j} = \frac{1}{n}$, so we are going from a matrix of rank $n$ to a matrix of rank $1$ by multiplications - i.e. the rank is decreasing by $n-1$.

Considering the rank of the matrices $(1-p)I + pA_{(i j)}$, then, we see that they're essentially identity matrices apart from a minor $\left[ \frac{1-p}{p} \frac{p}{1-p} \right]$ (excuse the lines - I don't want to spend half an hour working out how to typeset matrices without an array environment), so they have full rank unless $p=\frac{1}{2}$, in which case they have rank $n-1$.

Applying Sylvester's matrix inequality we therefore find that each swap decreases the rank only if $p=\frac{1}{2}$, and when this condition is met it decreases it by no more than 1. Therefore we require at least $n-1$ swaps of probability $\frac{1}{2}$.

Note that this bound can't be tightened because Anthony Leverrier's network achieves it.

Application to the case $n=4$. We already have solutions with 6 gates, so the question is whether solutions with 5 gates are possible. We now know that at least 3 of the gates must be 50/50 swaps, so we have two "free" probabilities, $p$ and $q$. There are 32 possible events (5 independent events each with two outcomes) and $4! = 24$ buckets each of which must contain at least one event. The events divide up as 8 with probability $\frac{pq}{8}$, 8 with probability $\frac{\overline{p}q}{8}$, 8 with probability $\frac{p\overline{q}}{8}$, and 8 with probability $\frac{\overline{p}\overline{q}}{8}$.

32 events into 24 buckets with no empty buckets implies that at least 16 buckets contain precisely one event, so at least two of the four probabilities given above are equal to $\frac{1}{24}$. Taking symmetries into account we have two cases: $pq = \overline{p}q = \frac{1}{3}$ or $pq = \overline{p}\overline{q} = \frac{1}{3}$.

The first case gives $p=\overline{p}=\frac{1}{2}$, $q=\frac{2}{3}$ (correction or $q=\frac{1}{3}$, unwinding the symmetry). The second case gives $pq=1-p-q+pq$, so $pq = p(1-p) = \frac{1}{3}$, which has no real solutions.

Therefore if there is a 5-gate solution we have four gates with probability $\frac{1}{2}$ and one gate with probability either $\frac{1}{3}$ or $\frac{2}{3}$. Wlog the first swap is $0\leftrightarrow 1$, and the second is either $0\leftrightarrow 2$ or $2\leftrightarrow 3$; the other three each have (no more than) five possibilities, because there's no point doing the same swap twice in a row. So we have $2\times 5^3$ swap sequences to consider and 10 ways of assigning the probabilities, leading to 2500 cases which could be enumerated and tested mechanically.

Update: Yuval Filmus and I have both enumerated and tested the cases and found no solutions, so the optimal solution for $n=4$ involves 6 gates, and examples of 6-gate solutions are found in other answers.

This isn't a full answer by any means, but it includes a result which may be useful and applies it to get some constraints on the case $n=4$ which limit the possible 5-gate solutions to 1250 easily enumerable cases.

First the general result: in any solution which permutes $n$ objects, there must be at least $n-1$ swaps which have probability $\frac{1}{2}$.

Proof: consider the permutation representation of the permutations of order $n$. These are the $n\times n$ matrices $A_\pi$ satisfying $(A_\pi)_{i,j} = [i = \pi(j)]$. Consider a swap between $i$ and $j$ with probability $p$: this has representation $(1-p)I + pA_{(i j)}$ (using cycle notation to represent the permutation). You can think of multiplication by this matrix in terms of representation theory or in Markov terms as applying the permutation $(i j)$ with probability $p$ and leaving things unchanged with probability $1-p$.

The permutation network is therefore a chain of such matrix multiplications. We start with the identity matrix and the final result will be a matrix $U$ where $U_{i,j} = \frac{1}{n}$, so we are going from a matrix of rank $n$ to a matrix of rank $1$ by multiplications - i.e. the rank is decreasing by $n-1$.

Considering the rank of the matrices $(1-p)I + pA_{(i j)}$, then, we see that they're essentially identity matrices apart from a minor $\left[ \frac{1-p}{p} \frac{p}{1-p} \right]$ (excuse the lines - I don't want to spend half an hour working out how to typeset matrices without an array environment), so they have full rank unless $p=\frac{1}{2}$, in which case they have rank $n-1$.

Applying Sylvester's matrix inequality we therefore find that each swap decreases the rank only if $p=\frac{1}{2}$, and when this condition is met it decreases it by no more than 1. Therefore we require at least $n-1$ swaps of probability $\frac{1}{2}$.

Application to the case $n=4$. We already have solutions with 6 gates, so the question is whether solutions with 5 gates are possible. We now know that at least 3 of the gates must be 50/50 swaps, so we have two "free" probabilities, $p$ and $q$. There are 32 possible events (5 independent events each with two outcomes) and $4! = 24$ buckets each of which must contain at least one event. The events divide up as 8 with probability $\frac{pq}{8}$, 8 with probability $\frac{\overline{p}q}{8}$, 8 with probability $\frac{p\overline{q}}{8}$, and 8 with probability $\frac{\overline{p}\overline{q}}{8}$.

32 events into 24 buckets with no empty buckets implies that at least 16 buckets contain precisely one event, so at least two of the four probabilities given above are equal to $\frac{1}{24}$. Taking symmetries into account we have two cases: $pq = \overline{p}q = \frac{1}{3}$ or $pq = \overline{p}\overline{q} = \frac{1}{3}$.

The first case gives $p=\overline{p}=\frac{1}{2}$, $q=\frac{2}{3}$. The second case gives $pq=1-p-q+pq$, so $pq = p(1-p) = \frac{1}{3}$, which has no real solutions.

Therefore if there is a 5-gate solution we have four gates with probability $\frac{1}{2}$ and one gate with probability $\frac{2}{3}$. Wlog the first swap is $0\leftrightarrow 1$, and the second is either $0\leftrightarrow 2$ or $2\leftrightarrow 3$; the other three each have (no more than) five possibilities, because there's no point doing the same swap twice in a row. So we have $2\times 5^3$ swap sequences to consider and 5 ways of assigning the probabilities, leading to 1250 cases which could be enumerated and tested mechanically.

This isn't a full answer by any means, but it includes a result which may be useful and applies it to get some constraints on the case $n=4$ which limit the possible 5-gate solutions to 2500 easily enumerable cases.

First the general result: in any solution which permutes $n$ objects, there must be at least $n-1$ swaps which have probability $\frac{1}{2}$.

Proof: consider the permutation representation of the permutations of order $n$. These are the $n\times n$ matrices $A_\pi$ satisfying $(A_\pi)_{i,j} = [i = \pi(j)]$. Consider a swap between $i$ and $j$ with probability $p$: this has representation $(1-p)I + pA_{(i j)}$ (using cycle notation to represent the permutation). You can think of multiplication by this matrix in terms of representation theory or in Markov terms as applying the permutation $(i j)$ with probability $p$ and leaving things unchanged with probability $1-p$.

The permutation network is therefore a chain of such matrix multiplications. We start with the identity matrix and the final result will be a matrix $U$ where $U_{i,j} = \frac{1}{n}$, so we are going from a matrix of rank $n$ to a matrix of rank $1$ by multiplications - i.e. the rank is decreasing by $n-1$.

Considering the rank of the matrices $(1-p)I + pA_{(i j)}$, then, we see that they're essentially identity matrices apart from a minor $\left[ \frac{1-p}{p} \frac{p}{1-p} \right]$ (excuse the lines - I don't want to spend half an hour working out how to typeset matrices without an array environment), so they have full rank unless $p=\frac{1}{2}$, in which case they have rank $n-1$.

Applying Sylvester's matrix inequality we therefore find that each swap decreases the rank only if $p=\frac{1}{2}$, and when this condition is met it decreases it by no more than 1. Therefore we require at least $n-1$ swaps of probability $\frac{1}{2}$.

Application to the case $n=4$. We already have solutions with 6 gates, so the question is whether solutions with 5 gates are possible. We now know that at least 3 of the gates must be 50/50 swaps, so we have two "free" probabilities, $p$ and $q$. There are 32 possible events (5 independent events each with two outcomes) and $4! = 24$ buckets each of which must contain at least one event. The events divide up as 8 with probability $\frac{pq}{8}$, 8 with probability $\frac{\overline{p}q}{8}$, 8 with probability $\frac{p\overline{q}}{8}$, and 8 with probability $\frac{\overline{p}\overline{q}}{8}$.

32 events into 24 buckets with no empty buckets implies that at least 16 buckets contain precisely one event, so at least two of the four probabilities given above are equal to $\frac{1}{24}$. Taking symmetries into account we have two cases: $pq = \overline{p}q = \frac{1}{3}$ or $pq = \overline{p}\overline{q} = \frac{1}{3}$.

The first case gives $p=\overline{p}=\frac{1}{2}$, $q=\frac{2}{3}$ (correction or $q=\frac{1}{3}$, unwinding the symmetry). The second case gives $pq=1-p-q+pq$, so $pq = p(1-p) = \frac{1}{3}$, which has no real solutions.

Therefore if there is a 5-gate solution we have four gates with probability $\frac{1}{2}$ and one gate with probability either $\frac{1}{3}$ or $\frac{2}{3}$. Wlog the first swap is $0\leftrightarrow 1$, and the second is either $0\leftrightarrow 2$ or $2\leftrightarrow 3$; the other three each have (no more than) five possibilities, because there's no point doing the same swap twice in a row. So we have $2\times 5^3$ swap sequences to consider and 10 ways of assigning the probabilities, leading to 2500 cases which could be enumerated and tested mechanically.