Return to Answer

Notation. Let $w(X, Y)$ be the minimum number of swaps required to turn $X$ into $Y$, for $X$ and $Y$ two permutations of $M$ where $M$ as in Claim 1. Let $w(m, n) = \max_{X, Y} w(X, Y)$. Then Claim 2 states that $$w(m, n) \le m(n - 1).$$

Proof. The key fact is. that conjugating of a product of $k$ transpositions in $\text{Sym}(mn)$ results in a product of $k$ transpositions.

Notation. Let $w(X, Y)$ be the minimum number of swaps required to turn $X$ into $Y$, for $X$ and $Y$ two permutations of $M$ and $M$ as in Claim 1. Let $w(m, n) = \max_{X, Y} w(X, Y)$. Then Claim 2 states that $$w(m, n) \le m(n - 1).$$

Proof. The key fact is that conjugating a product of $k$ transpositions in $\text{Sym}(mn)$ results in a product of $k$ transpositions.

Claim 1. Let $M$ be a multiset of size $mn$ consisting of $n$ elements $a_1, \dots, a_n$, each with multiplicity $m$. Let $X = (x_s)_{1 \le s \le mn}$ with $x_s \in \{a_1, \dots, a_n\}$ be a permutation of $M$ and let $\mu = (\mu_{i, j})_{1 \le i, j \le n} \in \mathbb{Z}_{\ge 0}^{n \times n}$ be the matrix defined by $$\mu_{i, j} = \#\left\{s \, \vert \, x_s = a_j,\, im + 1 \le s \le (i + 1)m\right\}.$$ Then the sum of every row and every column of $\mu$ is $m$.

Note. The integer $H(n, m)$ of the Anand–Dumir–Gupta conjectures is the number of matrices in $\mathbb{Z}_{\ge 0}^{n \times n}$ with constant row and column sums equal to $m$, see [1]. The original distribution problem that motivated [1] is due to Kenji Mano; it was first investigated in [3].

We shall establish:

Our proof relies on the following lemma:

Lemma 1 (Birkhoff-von Neumann, see [1, Theorem 1.1]). Let $\mu \in \mathbb{Z}_{\ge 0}^{n \times n}$ be a matrix such that the sum of every of its rows and of every of its columns is $m$. Then $\mu$ is a sum of $m$ permutation matrices.

Our strategy is rather naive. It consists in showing that a permutation of $M$ decomposes as a union of $m$ intertwined permutations of $\{a_1, \dots, a_n\}$.

  This is the purpose of the next lemma.

We are now in position to prove Claim 2.

Proof of Claim 2. Each of the $m$ permutations $\sigma_k$ of Lemma 2 can be turned into the identity by means of at most $n - 1$ swaps ($n - 1$ is the maximal reflection length of the permutations of $\{a_1, \dots, a_n\}$). We conclude by observing that the minimum number of swaps $w(X, Y)$ required to turn $X$ into $Y$, for $X$ and $Y$ two permutations of $M$, satisfies: $$w(X \sigma, Y \sigma) = w(X, Y)$$ for every $\sigma \in \text{Sym}(mn)$.

It is now natural to ask:

Question. Is the upper bound of Claim 2 a tight bound? More specifically, does $w(m,n) \ge m(n - 1)$ hold?

Claim 1. Let $M = \{m \cdot a_1, \dots, m \cdot a_n\}$ be a multiset of size $mn$ consisting of $n$ elements $a_1, \dots, a_n$, each with multiplicity $m$. Let $X = (x_s)_{1 \le s \le mn}$ with $x_s \in \{a_1, \dots, a_n\}$ be a permutation of $M$ and let $\mu = (\mu_{i, j})_{1 \le i, j \le n} \in \mathbb{Z}_{\ge 0}^{n \times n}$ be the matrix defined by $$\mu_{i, j} = \#\left\{s \, \vert \, x_s = a_j,\, im + 1 \le s \le (i + 1)m\right\}.$$ Then the sum of every row and every column of $\mu$ is $m$.

Note. The integer $H(n, m)$ of the Anand–Dumir–Gupta conjectures is the number of matrices in $\mathbb{Z}_{\ge 0}^{n \times n}$ with constant row and column sums equal to $m$, see [1]. The original distribution problem that motivated [2] is due to Kenji Mano; it was first investigated in [3].

We shall establish the following simple fact:

Notation. Let $w(X, Y)$ be the minimum number of swaps required to turn $X$ into $Y$, for $X$ and $Y$ two permutations of $M$ where $M$ as in Claim 1. Let $w(m, n) = \max_{X, Y} w(X, Y)$. Then Claim 2 states that $$w(m, n) \le m(n - 1).$$

Our proof relies on the following straightforward lemma:

Lemma. Let $M$ be as in Claim 1 and let $X$ and $Y$ be two permutations of $M$. Then we have $$w(X \sigma, Y \sigma) = w(X, Y)$$ for every $\sigma \in \text{Sym}(mn)$.

Proof. The key fact is. that conjugating of a product of $k$ transpositions in $\text{Sym}(mn)$ results in a product of $k$ transpositions.

Proof of Claim 2. Let $X$ be a permutation of $M$. For each $i \in \{1, \dots, n - 1\}$, we need at most $m$ swaps to move the $m$ elements of $X$ equal to $a_i$ so that they occupy the positions from $(i - 1)m + 1$ to $im$. Thus it suffices to apply $m(n - 1)$ swaps to $X$ to turn it into the permutation $$(a_1 \cdots a_1 a_2 \cdots a_2 \cdots a_{n - 1} \cdots a_{n - 1} a_n \cdots a_n).$$ Since $\text{Sym}(mn)$ acts transitively on the permutations of $M$, the result now follows from the above lemma.

It seems now natural to ask:

Question. Is the upper bound of Claim 2 a tight bound? More specifically, does $w(m,n) \ge m(n - 1)$ hold?

In my initial answer, I thought that the following results could be useful. (As of now, it's unclear to me how they could help).

Lemma 1 (Birkhoff-von Neumann Theorem, see [1, Theorem 1.1]). Let $\mu \in \mathbb{Z}_{\ge 0}^{n \times n}$ be a matrix such that the sum of every of its rows and of every of its columns is $m$. Then $\mu$ is a sum of $m$ permutation matrices.

Our strategy is rather naive. It consists in showing that a permutation of $M$ decomposes as a union of $m$ intertwined permutations of $\{a_1, \dots, a_n\}$. This is explained in the next lemma.

The question relates to the numbers $H(n, m)$ of the Anand–Dumir–Gupta conjectures solved by Richard Stanley, see e.g. [1] (this MO post set me on this track).

Indeed, we have:

Claim 1. Let $M$ be a multiset of size $mn$ consisting of $n$ elements $a_1, \dots, a_n$, each with multiplicity $m$. Let $X = (x_s)_{1 \le s \le mn}$ with $x_s \in \{a_1, \dots, a_n\}$ be a permutation of $M$ and let $\mu = (\mu_{i, j})_{1 \le i, j \le n} \in \mathbb{Z}_{\ge 0}^{n \times n}$ be the matrix defined $$\mu_{i, j} = \#\left\{s \, \vert \, x_s = a_j,\, im + 1 \le s \le (i + 1)m\right\}.$$ Then the sum of every row and every column of $\mu$ is $m$.

Proof. A straightforward verification.

Note. The integer $H(n, m)$ of the Anand–Dumir–Gupta conjectures is the number of matrices in $\mathbb{Z}_{\ge 0}^{n \times n}$ with constant row and column sums equal to $m$, see [1].

We shall establish:

Claim 2. Let $M$ be a multiset as in Claim 1. Any two permutations of $M$ can be related by means of at most $m(n - 1)$ swaps.

Our proof relies on the following lemma:

Lemma 1 (Birkhoff-von Neumann, see [1, Theorem 1.1]). Let $\mu \in \mathbb{Z}_{\ge 0}^{n \times n}$ be a matrix such that the sum of every of its rows and of every of its columns is $m$. Then $\mu$ is a sum of $m$ permutation matrices.

Our strategy is rather naive. It consists in showing that a permutation of $M$ decomposes as a union of $m$ intertwined permutations of $\{a_1, \dots, a_n\}$.

This is the purpose of the next lemma.

Lemma 2. Let $M$ and $X$ be as in Claim 1. Then there are pairwise distinct indices $i_{k, l} \in \{1, \dots, mn\}$ with $k \in \{1, \dots, m\}$ and $l \in \{1, \dots, n \}$ such that

• $i_{k, l} \in [(l - 1)m + 1, lm]$ for every $k$ and every $l$,
• $\{x_{i_{k,l}} \, \vert \, 1 \le l \le n\} = \{a_1, \dots, a_n\}$ for every $k$, i.e., the map $\sigma_k$ defined by $$\sigma_k(a_l) = x_{i_{k, l}}$$ is a permutation of the set $\{a_1, \dots, a_n\}$ for every $k$.

Proof. Apply Claim 1 and Lemma 1: the matrix $\mu = \mu(X)$ is a sum of $m$ permutation matrices. The corresponding permutations are the desired permutations $\sigma_k$.

We are now in position to prove Claim 2.

Proof of Claim 2. Each of the $m$ permutations $\sigma_k$ of Lemma 2 can be turned into the identity by means of at most $n - 1$ swaps ($n - 1$ is the maximal reflection length of the permutations of $\{a_1, \dots, a_n\}$). We conclude by observing that the minimum number of swaps $w(X, Y)$ required to turn $X$ into $Y$, for $X$ and $Y$ two permutations of $M$, satisfies: $$w(X \sigma, Y \sigma) = w(X, Y)$$ for every $\sigma \in \text{Sym}(mn)$.

It is natural to ask:

Question. Is the upper bound of Claim 2 a tight bound? More specifically, does $w(m,n) \ge m(n - 1)$ hold?

[1] W. Bruns, "Commutative Algebra Arising from the Anand–Dumir–Gupta Conjectures", 2007.

The question relates to the numbers $H(n, m)$ of the Anand–Dumir–Gupta conjectures solved by Richard Stanley, see e.g. [1] (this MO post set me on this track).

Indeed, we have:

Claim 1. Let $M$ be a multiset of size $mn$ consisting of $n$ elements $a_1, \dots, a_n$, each with multiplicity $m$. Let $X = (x_s)_{1 \le s \le mn}$ with $x_s \in \{a_1, \dots, a_n\}$ be a permutation of $M$ and let $\mu = (\mu_{i, j})_{1 \le i, j \le n} \in \mathbb{Z}_{\ge 0}^{n \times n}$ be the matrix defined by $$\mu_{i, j} = \#\left\{s \, \vert \, x_s = a_j,\, im + 1 \le s \le (i + 1)m\right\}.$$ Then the sum of every row and every column of $\mu$ is $m$.

Proof. A straightforward verification.

Note. The integer $H(n, m)$ of the Anand–Dumir–Gupta conjectures is the number of matrices in $\mathbb{Z}_{\ge 0}^{n \times n}$ with constant row and column sums equal to $m$, see [1]. The original distribution problem that motivated [1] is due to Kenji Mano; it was first investigated in [3].

We shall establish:

Claim 2. Let $M$ be a multiset as in Claim 1. Any two permutations of $M$ can be related by means of at most $m(n - 1)$ swaps.

Our proof relies on the following lemma:

Lemma 1 (Birkhoff-von Neumann, see [1, Theorem 1.1]). Let $\mu \in \mathbb{Z}_{\ge 0}^{n \times n}$ be a matrix such that the sum of every of its rows and of every of its columns is $m$. Then $\mu$ is a sum of $m$ permutation matrices.

Our strategy is rather naive. It consists in showing that a permutation of $M$ decomposes as a union of $m$ intertwined permutations of $\{a_1, \dots, a_n\}$.

This is the purpose of the next lemma.

Lemma 2. Let $M$ and $X$ be as in Claim 1. Then there are pairwise distinct indices $i_{k, l} \in \{1, \dots, mn\}$ with $k \in \{1, \dots, m\}$ and $l \in \{1, \dots, n \}$ such that

• $i_{k, l} \in [(l - 1)m + 1, lm]$ for every $k$ and every $l$,
• $\{x_{i_{k,l}} \, \vert \, 1 \le l \le n\} = \{a_1, \dots, a_n\}$ for every $k$, i.e., the map $\sigma_k$ defined by $$\sigma_k(a_l) = x_{i_{k, l}}$$ is a permutation of the set $\{a_1, \dots, a_n\}$ for every $k$.

Proof. Apply Claim 1 and Lemma 1: the matrix $\mu = \mu(X)$ is a sum of $m$ permutation matrices. The corresponding permutations are the desired permutations $\sigma_k$. Alternatively, one may resort to Hall's marriage theorem and exhibit the sequences $(i_{k, l})$ directly through induction.

We are now in position to prove Claim 2.

Proof of Claim 2. Each of the $m$ permutations $\sigma_k$ of Lemma 2 can be turned into the identity by means of at most $n - 1$ swaps ($n - 1$ is the maximal reflection length of the permutations of $\{a_1, \dots, a_n\}$). We conclude by observing that the minimum number of swaps $w(X, Y)$ required to turn $X$ into $Y$, for $X$ and $Y$ two permutations of $M$, satisfies: $$w(X \sigma, Y \sigma) = w(X, Y)$$ for every $\sigma \in \text{Sym}(mn)$.

It is now natural to ask:

Question. Is the upper bound of Claim 2 a tight bound? More specifically, does $w(m,n) \ge m(n - 1)$ hold?

• [1] W. Bruns, "Commutative Algebra Arising from the Anand–Dumir–Gupta Conjectures", 2007.

• [2] H. Anand, V. Dumir, H. Gupta, "A combinatorial distribution problem", 1966.

• [3] M. Kenji, "On the formula ${}_{n!}H_r$", 1961.