# Union of Permutations

This is a problem I asked on https://math.stackexchange.com/questions/647382/union-of-permutations. Feel free to close it if you think it below research level.

Having $k$ different permutations, $\pi_{1},\dots,\pi_{k}: \{1\ \ldots\ n\}\rightarrow \{1\ \ldots\ n\}$, the union of permutations is defined as follows:

$$\forall i{\in}[n],\ U_i=\{{\pi}_1(i),{\pi}_2(i),\dots,{\pi}_k(i)\}$$

Note that in $U_i$ there may be repetitions, so $|U_i|{\leq}k$, let $s=\sum_i^n|U_i|$, so I want to ask, what is the minimum $\sigma(n\ k)$ of all $s$ as above for any $k$ permutations?

For example, if we let $n=4,k=3$, we have three permutations $$\pi_1=1234,\pi_2=2134,\pi_3=3421$$ coded in the obvious way, then $$U_1=\{1,2,3\},U_2=\{2,1,4\},U_3=\{3,2\},U_4=\{4,1\}$$ so $s=3+3+2+2=10$. But we have a better choice: $$\pi_1=1234,\pi_2=2134,\pi_3=1324$$ here $$U_1=\{1,2\},U_2=\{2,1,3\},U_3=\{3,2\},U_4=\{4\}$$, $s=2+3+2+1=8$.

Intuitively, the more the different permutations share common parts, the less $s$ will be, so if we let $k=i!$, then for permutations in the form $\pi=(\pi^{*})(i+1)(i+2){\dots}n$ where $\pi^{*}$ is any permutation of $1,2,\dots,i$, namely the $k$ different permutations differ only on the first $i$ elements, then $s$ may be minimum, and $s=i^2-i+n$. Take $n=6, k=6$ for example, the best choices of 6 different permutations may be: $$\pi_1=123456, \pi_2=132456, \pi_3=213456, \pi_4=231456, \pi_5=312456, \pi_6=321456$$ and the best $s=3+3+3+1+1+1=12$. But this is a simple intuition; does anyone know what is the exact answer to this question?

• Just a reformulation which may look more familiar to someone. Given that the permanent of a 0-1 matrix $A$ is at least $k$, find the minimal sum of its elements. – Ilya Bogdanov Jan 28 '14 at 4:21
• For $n=6$, you may achieve more permutations keeping $s=12$. Set $U_1=U_2=\{1,2\}$, $U_3=U_4=\{3,4\}$, $U_5=U_6=\{5,6\}$. This pattern clearly fits for 8 permutations. So the optimal configuration should be a different one. (To make it more evident, compare $5!=120$ permutations obtained by permutations of the first 5 numbers with $2^7=128$ permutations obtained by switchings of 7 pairs of numbers.) – Ilya Bogdanov Jan 28 '14 at 4:28

$\def\perm{\mathop{\rm perm}}$This is a partial answer for the case when $n$ is large enough. In particular, we show that for $k=2^\ell$ and $n\geq 2\ell$ we have $s\geq n+2\ell$, supported by the model $U_{2i}=U_{2i-1}=\{2i-1,2i\}$, $i=1,\dots,\ell$.

For convenience, let us consider the permanent reformulation of the problem. Let us show that for every $s=n+\delta$, if the sum of elements of a 0-1 matrix $A$ is $s$ then $\perm A\leq 2^{\delta/2}$. The base case $\delta\leq 1$ is clear.

Take the row or column of $A$ containing the least number $t$ of 1's (WLOG this is the first row). If $t=0$, the statement is clear. So assume that $t\geq 1$. Then $$\perm A=\sum_{i=1}^t \perm A_i,$$ where $A_i$ is obtained from $A$ by deletion of the first row and the column with $i$th one. Let $s_i=(n-1)+\delta_i$ be the sum of elemtents of $A_i$; then $\delta_i\leq \delta-2t+2$, because the deleted column had at least $t$ ones. Thus $$\perm A\leq t2^{(\delta-2t+2)/2}.$$ Notice that $t2^{-t}\leq 1/2$ for positive integer $t$; so $\perm A\leq 2^{\delta/2}$ as required.

Remarks. Notice that if $t\geq 3$ on some step, then the estimate makes less by a factor of at most $3/4$. On the other hand, if in some deleted column we have more than $t$ ones (for $t=1$ or $t=2$), then the estimate also decreases by at most $\displaystyle\frac{\sqrt2+1}2<\frac34$. In particular, one may see that this estimate can be tighten for all odd $\delta$.

Right now I do not see how to extend this for larger values of $k$; but it may happen that the optimal example still consists of several blocks on the diagonal of almost the same size.

You could look for a sequence of permutations, that are adjacent in the Steinhaus-Johnson-Trotter sequence of permutations
http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithmsequence
for minimizing $s$, or, for those adjacent in the DeBruijn sequence
http://en.wikipedia.org/wiki/De_Bruijn_sequence
for more general questions regarding $s$

• Any proof showing $k$ permutations in Steinhaus-Johnson-Trotter does minimize $s$, or just intuitively because they differ only a little? – Yu Song Jan 28 '14 at 7:33
• just intuitively; would have to be checked whether Steinhaus-Johnson-Trotter yields smaller $s$ than lexicographic order of permutations. – Manfred Weis Jan 28 '14 at 7:45