A CHARACTERIZATION OF THE CENTRALIZER OF A PERMUTATION

Thomas P. Kezlan and Noah H. Rhee

Abstract. An explicit form is determined for those permutations commuting with a given permutation, and the number of them is also determined.

In his modern algebra textbook Topics in Algebra [1] I. N. Herstein, after determining the number of conjugate classes in the symmetric group S_{n}, states that “... we can find all the elements commuting with a given permutation” and by way of example proceeds to do this for the transposition (1, 2) and for the n–cycle (1, 2, …, n) [1]. While this is relatively easy for permutations with such simple cycle structure, the problem is less tractable for those which are products of disjoint cycles of differing lengths, particularly if there are more than one of the same length. In this note we determine an explicit form of all permutations commuting with a given one and also determine their number.

Let σ be any permutation in S_{n}. The support of σ, denoted by supp(σ), is the set of letters moved by σ, the centralizer C(σ) of σ is the subgroup of all permutations in S_{n} which commute with σ, and the conjugate class Cl(σ) of σ is the set of all conjugates θσθ^{−1} where θ ∈ S_{n}. The number o(Cl(σ)) of conjugates of σ is given by o(Cl(σ)) = [S_{n} : C(σ)], the index of C(σ) in S_{n}.

We first consider the case in which σ is a product of disjoint cycles, all of the same length, viz., σ = σ_{1}σ_{2} ⋯ σ_{r} where σ_{1}, σ_{2}, …, σ_{r} are disjoint k–cycles with k > 1. Let σ_{j} = (a_{1j}, a_{2j}, …, a_{kj}) for j = 1, 2, …, r. Given a permutation θ ∈ S_{r} we define an auxiliary permutation θ′ ∈ S_{n} by θ′(a_{ij}) = a_{i,θ(j)} for i = 1, 2, …, k and j = 1, 2, …, r and θ′(x) = x for all other letters x. Note that supp(θ′) ⊆ supp(σ).

\underline{Lemma 1}. With the notation as above, a permutation in S_{n} commutes with σ if and only if it has the form

σ_{1}^{s_{1}}σ_{2}^{s_{2}} ⋯ σ_{r}^{s_{r}}θ′τ

where 1 ≤ s_{i} ≤ k for i = 1, 2, … r, where θ ∈ S_{r}, and where τ is disjoint with σ. Moreover the number of such permutations is k^{r}r!(n − kr)!.

\underline{Proof}. For i = 1, 2, …, r let d_{i} = k(r−i+1). Since a permutation is conjugate to σ if and only if it has the same cycle structure as σ, we have

o(Cl(σ)) = \frac{\binom{n}{d_{1}}\binom{d_{1}}{k}(k − 1)!\binom{d_{2}}{k}(k − 1)! ⋯ \binom{d_{r−1}}{k}(k − 1)!\binom{d_{r}}{k}(k − 1)!}{r!}

= \frac{[\frac{n!}{d_{1}!(n−d_{1})!}][\frac{d_{1}!(k−1)!}{k!d_{2}!}][\frac{d_{2}!(k−1)!}{k!d_{3}!}] ⋯ [\frac{d_{r−1}!(k−1)!}{k!d_{r}!}][\frac{d_{r}!(k−1)!}{k!0!}]}{r!}

= \frac{n!}{(n − d_{1})!r!k^{r}} ,

and hence,

o(C(σ)) = \frac{n!}{o(Cl(σ))} = k^{r}r!(n − kr)!.

Now let T denote the set of all permutations of the form given in the statement of the lemma. Noting that θ′σ(a_{ij}) = a_{i+1,θ(j)} = σθ′(a_{ij}), we have θ′σ = σθ′ from which T ⊆ C(σ) follows. Suppose

σ_{1}^{s_{1}}σ_{2}^{s_{2}} ⋯ σ_{r}^{s_{r}}θ′τ = σ_{1}^{t_{1}}σ_{2}^{t_{2}} ⋯ σ_{r}^{t_{r}}η′ρ

where 1 ≤ s_{i}, t_{i} ≤ k for i = 1, 2, …, r, where θ and η are in S_{r}, and where τ and ρ are in S_{n} and disjoint with σ. Since τ and ρ are also disjoint with θ′ and η′, we have τ = ρ. Suppose without loss of generality that s_{1} ≤ t_{1}. Then 0 ≤ t_{1} − s_{1} < k, whence,

\begin{aligned}a_{t_{1}−s_{1}+1,1} & = σ_{1}^{t_{1}−s_{1}}(a_{11}) = σ_{1}^{t_{1}−s_{1}}σ_{2}^{t_{2}−s_{2}} ⋯ σ_{r}^{t_{r}−s_{r}}(a_{11}) \\ & = θ′(η′)^{−1}(a_{11}) = θ′(a_{1,η^{−1}(1)}) = a_{1,θη^{−1}(1)}. \end{aligned}

Thus, t_{1} − s_{1} + 1 = 1, that is t_{1} = s_{1}, and θη^{−1}(1) = 1. In a similar way we obtain t_{i} = s_{i} and θη^{−1}(i) = i for i = 1, 2, … r. Thus, θ = η. This establishes the unique form of the elements of T, so o(T) = k^{r}r!(n − kr)! and T = C(σ).

For the general case suppose σ = σ_{1}σ_{2} ⋯ σ_{m} where σ_{1}, σ_{2}, …, σ_{m} are disjoint permutations such that for 1 ≤ i ≤ m, σ_{i} is a product of r_{i} disjoint k_{i}–cycles, and k_{1}, k_{2}, …, k_{m} are distinct integers greater than 1. For i = 1, 2, …, m let σ_{i} = σ_{1}^{(i)}σ_{2}^{(i)} ⋯ σ_{r_{i}}^{(i)} where σ_{1}^{(i)}, σ_{2}^{(i)}, …, σ_{r_{i}}^{(i)} are disjoint k_{i}–cycles.

\underline{Theorem 2}. With the notation as above, a permutation in S_{n} commutes with σ if and only if it has the form

∏_{i=1}^{m}(σ_{1}^{(i)})^{s_{1}^{(i)}}(σ_{2}^{(i)})^{s_{2}^{(i)}} ⋯ (σ_{r_{i}}^{(i)})^{s_{r_{i}}^{(i)}}θ′_{i}δ

where 1 ≤ s_{j}^{(i)} ≤ k_{i} for i = 1, 2, …, m and j = 1, 2, …, r_{i}, where θ_{i} ∈ S_{r_{i}} for i = 1, 2, …, m, and where δ is a permutation in S_{n} disjoint with σ. Moreover the number of such permutations is

(∏_{i=1}^{m} k_{i}^{r_{i}}r_{i}!)(n − ∑_{i=1}^{m} k_{i}r_{i})!.

\underline{Proof}. Let T denote the set of all permutations of the form given in the statement of the theorem. By using the lemma it is easy to see that T ⊆ C(σ). Now suppose α ∈ C(σ). Then

σ = ασα^{−1} = ∏_{i=1}^{m} ∏_{j=1}^{r_{i}} ασ_{j}^{(i)}α^{−1}

yields a decomposition of σ into a product of disjoint cycles. Since

σ = ∏_{i=1}^{m} ∏_{j=1}^{r_{i}} σ_{j}^{(i)}

is also a decomposition of σ into a product of disjoint cycles and k_{1}, k_{2}, …, k_{m} are distinct, by the uniqueness of decomposition we must have

∏_{j=1}^{r_{i}} ασ_{j}^{(i)}α^{−1} = ∏_{j=1}^{r_{i}} σ_{j}^{(i)}

for i = 1, 2, …, m, so we have ασ_{i}α^{−1} = σ_{i} for i = 1, 2, …, m, that is, α commutes with σ_{i} for i = 1, 2, …, m. Thus, by the lemma, for i = 1, 2, …, m, there must exist integers s_{1}^{(i)}, s_{2}^{(i)}, …, s_{r_{i}}^{(i)} and permutations θ_{i} ∈ S_{r_{i}} and τ_{i} ∈ S_{n} such that 1 ≤ s_{j}^{(i)} ≤ k_{i} for j = 1, 2, …, r_{i}, τ_{i} is disjoint with σ_{i}, and

α = (σ_{1}^{(i)})^{s_{1}^{(i)}}(σ_{2}^{(i)})^{s_{2}^{(i)}} ⋯ (σ_{r_{i}}^{(i)})^{s_{r_{i}}^{(i)}}θ′_{i}τ_{i}.

For brevity we let

β_{i} = (σ_{1}^{(i)})^{s_{1}^{(i)}}(σ_{2}^{(i)})^{s_{2}^{(i)}} ⋯ (σ_{r_{i}}^{(i)})^{s_{r_{i}}^{(i)}}θ′_{i}

for i = 1, 2, …, m; thus,

α = β_{1}τ_{1} = β_{2}τ_{2} = ⋯ = β_{m}τ_{m}.

Consider the two permutations τ_{1} and ∏_{i=2}^{m} β_{i}. Suppose x ∈ supp(σ), the latter being the disjoint union of supp(σ_{i}) for i = 1, 2, …, m. If x ∈ supp(σ_{1}), then τ_{1}(x) = x = (∏_{i=2}^{m} β_{i})(x); if x ∈ supp(σ_{j}) with j ≠ 1, then

τ_{1}(x) = β_{1}τ_{1}(x) = β_{j}τ_{j}(x) = β_{j}(x) = (∏_{i=2}^{m} β_{i})(x),

the last equation holding since x ∉ supp(σ_{i}) with i ≠ j. Thus, τ_{1} and ∏_{i=2}^{m} β_{i} agree on supp(σ). Hence, δ = (∏_{i=2}^{m} β_{i})^{−1}τ_{1} is a permutation of the remaining n − ∑_{i=1}^{m} k_{i}r_{i} letters not in supp(σ). We now have

α = β_{1}τ_{1} = β_{1}(∏_{i=2}^{m} β_{i})δ = ∏_{i=1}^{m}(σ_{1}^{(i)})^{s_{1}^{(i)}}(σ_{2}^{(i)})^{s_{2}^{(i)}} ⋯ (σ_{r_{i}}^{(i)})^{s_{r_{i}}^{(i)}}θ′_{i}δ,

showing that α ∈ T. So we have established T = C(σ).

To see that the representation of α in this form is unique, suppose we also have

α = ∏_{i=1}^{m}(σ_{1}^{(i)})^{t_{1}^{(i)}}(σ_{2}^{(i)})^{t_{2}^{(i)}} ⋯ (σ_{r_{i}}^{(i)})^{t_{r_{i}}^{(i)}}η′_{i}ρ.

Considering supports, it is easy to see that δ = ρ and that

(σ_{1}^{(i)})^{s_{1}^{(i)}}(σ_{2}^{(i)})^{s_{2}^{(i)}} ⋯ (σ_{r_{i}}^{(i)})^{s_{r_{i}}^{(i)}}θ′_{i} = (σ_{1}^{(i)})^{t_{1}^{(i)}}(σ_{2}^{(i)})^{t_{2}^{(i)}} ⋯ (σ_{r_{i}}^{(i)})^{t_{r_{i}}^{(i)}}η′_{i}

for i = 1, 2, …, m. But this is the case considered in the proof of the lemma, so for i = 1, 2, …, m and j = 1, 2, …, r_{i} we have s_{j}^{(i)} = t_{j}^{(i)} and θ_{i} = η_{i}. Hence, the representation of α is unique and counting elements of this form, we obtain o(C(σ)) = (∏_{i=1}^{m} k_{i}^{r_{i}}r_{i}!)(n−∑_{i=1}^{m} k_{i}r_{i})!, which completes the proof of the theorem.

\underline{Example 3}. In S_{25} let
σ = (1, 2)(3, 4)(5, 6)(7, 8, 9)(10, 11, 12)(13, 14, 15, 16)(17, 18, 19, 20).

Then

σ_{1} = (1, 2)(3, 4)(5, 6), k_{1} = 2, r_{1} = 3,
σ_{2} = (7, 8, 9)(10, 11, 12), k_{2} = 3, r_{2} = 2,
σ_{3} = (13, 14, 15, 16)(17, 18, 19, 20), k_{3} = 4, r_{3} = 2.

The number of permutations in S_{25} commuting with σ is

(2^{3} · 3!)(3^{2} · 2!)(4^{2} · 2!)(25 − 20)! = 3, 317, 760,

and they all have the form

(1, 2)^{c_{1}}(3, 4)^{c_{2}}(5, 6)^{c_{3}}(7, 8, 9)^{d_{1}}(10, 11, 12)^{d_{2}}(13, 14, 15, 16)^{e_{1}}(17, 18, 19, 20)^{e_{2}}θ′_{1}θ′_{2}θ′_{3}δ

where c_{i} = 1 or 2, d_{i} = 1, 2, or 3, e_{i} = 1, 2, 3, or 4 for each i, θ_{1} ∈ S_{3}, θ_{2} ∈ S_{2}, θ_{3} ∈ S_{2}, and δ is a permutation of {21, 22, 23, 24, 25}. We also note that, for example, if θ_{1} = (1, 3, 2), θ_{2} = (1, 2), and θ_{3} = 1, then

θ′_{1} = (1, 5, 3)(2, 6, 4), θ′_{2} = (7, 10)(8, 11)(9, 12), θ′_{3} = 1.

\underline{Reference}

1. I. N. Herstein, Topics in Algebra, 2nd ed., Xerox Corporation, Lexington, Massachusetts, 1975.

Thomas P. Kezlan Department of Mathematics and Statistics University of Missouri – Kansas City Kansas City, MO 64110 email: kezlan@cctr.umkc.edu

Noah H. Rhee Department of Mathematics and Statistics University of Missouri – Kansas City Kansas City, MO 64110 email: rhee@cctr.umkc.edu