07.05.12 · representation-theory / symmetric

Metrics on S_n

shipped3 tiersLean: none

Anchor (Master): Diaconis 1988 IMS Lecture Notes 11 Ch. 6; Critchlow 1985; Diaconis-Graham 1977 Adv. Appl. Math.

Intuition [Beginner]

When two people rank the same set of items differently, you want a number measuring "how far apart" their rankings are. Several natural distances exist: count how many items are in different positions, count how many pairs are in opposite order, or count the minimum number of swaps needed to turn one ranking into the other.

Each of these distances has a character-theoretic formula: it can be expressed as a sum involving the irreducible characters of the symmetric group. This is not a coincidence — the characters encode the deep symmetry structure of the group, and any function invariant under certain group operations can be expanded in characters.

Why does this concept exist? Because the most useful distances on permutations all have spectral expressions that connect them to representation theory, enabling character-based computations and statistical tests on ranking data.

Visual [Beginner]

A diagram showing three permutations of four items as sequences of numbered balls, with curved arrows indicating the swaps needed to transform one into another. Below each pair, the Cayley distance (number of transpositions), the Hamming distance (number of displaced items), and the Kendall tau distance (number of pairwise inversions) are displayed.

The three metrics give different answers for the same pair of permutations, reflecting different notions of "closeness."

Worked example [Beginner]

Consider the permutations $π = (2, 3, 1, 4)$ and $σ = (1, 2, 3, 4)$ in one-line notation on four items. We compute three distances.

Step 1. Cayley distance: the minimum number of transpositions needed to transform $π$ into $σ$ . The permutation $σ^{- 1} π = (2, 3, 1, 4)$ has cycle decomposition $(123) (4)$ . A 3-cycle requires $3 - 1 = 2$ transpositions. So $d_{C} (π, σ) = 2$ .

Step 2. Hamming distance: the number of positions where the two permutations differ. Comparing position by position: position 1 has 2 vs 1 (differ), position 2 has 3 vs 2 (differ), position 3 has 1 vs 3 (differ), position 4 has 4 vs 4 (same). So $d_{H} (π, σ) = 3$ .

Step 3. Kendall tau distance: the number of pairs in opposite relative order. In $π = (2, 3, 1, 4)$ : the pair $(1, 2)$ has $2 > 1$ but $2$ appears before $1$ , which is the wrong order compared to $(1, 2, 3, 4)$ . Counting inversions: $(2, 1), (3, 1)$ = 2 inversions. So $d_{K} (π, σ) = 2$ .

What this tells us: different metrics capture different aspects of the disagreement between two rankings. Cayley counts swaps; Hamming counts displaced items; Kendall counts pairwise disagreements.

Check your understanding [Beginner]

Formal definition [Intermediate+]

Let $S_{n}$ denote the symmetric group. We define four metrics on $S_{n}$ .

Cayley distance. $d_{C} (π, σ) = n - c (σ^{- 1} π)$ where $c (τ)$ is the number of cycles in the cycle decomposition of $τ$ (counting fixed points as cycles of length 1).

Hamming distance. $d_{H} (π, σ) = # {i : π (i) \neq = σ (i)}$ . Equivalently, $d_{H} (π, σ) = n - fix (σ^{- 1} π)$ where $fix (τ)$ is the number of fixed points of $τ$ .

Kendall tau distance. $d_{K} (π, σ) = # {(i, j) : i < j, (π^{- 1} σ (i) - π^{- 1} σ (j)) (i - j) < 0}$ . This counts the number of pairs whose relative order is reversed between $π$ and $σ$ .

Spearman rho (squared) distance. $d_{ρ} (π, σ) = \sum_{i = 1}^{n} (π (i) - σ (i))^{2}$ .

Each metric is right-invariant: $d (π τ, σ τ) = d (π, σ)$ for all $τ$ . This means $d (π, σ) = d (e, σ^{- 1} π)$ , so every metric is determined by its values on pairs involving the identity.

Definition (Character-theoretic expression). A metric $d$ on $S_{n}$ has a character-theoretic expression if there exist coefficients $a_{λ}$ such that

d (e, π) = λ ⊢ n \sum a_{λ} χ_{λ} (π)

for all $π \in S_{n}$ , where $χ_{λ}$ is the irreducible character indexed by $λ$ .

Counterexamples to common slips

Confusing right-invariance with left-invariance. All four metrics are right-invariant but not all are left-invariant. The Cayley distance is bi-invariant (since it depends only on cycle structure), but the Kendall tau distance is not left-invariant.
Spearman rho as a metric. The sum of squared position differences $d_{ρ}$ is not a metric in the strict sense (it does not satisfy the triangle inequality without taking square root). The square root $d_{ρ}$ is a metric.
Kendall tau normalisation. The raw inversion count ranges from $0$ to $n (n - 1) /2$ . The normalised version $τ = 1 - 2 d_{K} / (n (n - 1) /2)$ is the Kendall tau correlation coefficient used in statistics.

Key theorem with proof [Intermediate+]

Theorem (Character-theoretic expressions for metrics on $S_{n}$ — Diaconis 1988). Each of the four metrics has a character-theoretic expansion. In particular, for $π \in S_{n}$ with cycle type $μ = (μ_{1}, μ_{2}, \dots)$ :

d_{C} (e, π) = n - ℓ (μ) = n - λ ⊢ n \sum \frac{χ _{λ} ( μ )}{d _{λ}} \cdot (n - ℓ (μ)),

d_{H} (e, π) = n - fix (π) = n - \frac{1}{( n - 1 )!} λ ⊢ n \sum d_{λ} χ_{λ} (π) χ_{λ} (transposition),

and the Kendall tau distance satisfies

d_{K} (e, π) = (2 n) - \frac{1}{n} λ ⊢ n \sum \frac{d _{λ}}{d _{λ}} χ_{λ} (π) (2 n) = \frac{1}{2} i = 1 \sum n - 1 \frac{1}{m _{i}} ∣ χ^{(i)} (π) ∣^{2}

where $χ^{(i)}$ denotes the character of the representation carried by the $i$ -th graded piece of the coinvariant algebra and $m_{i}$ is a combinatorial multiplicity.

Proof. We prove the Hamming distance character formula; the others follow similar strategies.

Step 1 (Hamming as a class function). The number of fixed points $fix (π) = \sum_{i = 1}^{n} 1_{π (i) = i}$ can be written as $fix (π) = \sum_{i = 1}^{n} δ_{π (i), i}$ . This is the character of the permutation representation on ${1, \dots, n}$ , which decomposes as $1 \oplus V^{(n - 1, 1)}$ where $1$ is the identity representation. So $fix (π) = 1 + χ_{(n - 1, 1)} (π)$ .

Step 2 (Inversion via Plancherel). Express $fix (π)$ using the orthogonality relations. The function $fix$ is a class function (it depends only on the cycle type), so by character inversion:

fix (π) = λ ⊢ n \sum ⟨ fix, χ_{λ} ⟩ χ_{λ} (π), ⟨ fix, χ_{λ} ⟩ = \frac{1}{n !} τ \sum fix (τ) \overline{χ_{λ} (τ)} .

The inner product $⟨ fix, χ_{λ} ⟩$ equals the multiplicity of $V^{λ}$ in the permutation representation. By the decomposition $perm = 1 \oplus V^{(n - 1, 1)}$ , only $λ = (n)$ and $λ = (n - 1, 1)$ contribute:

fix (π) = 1 + χ_{(n - 1, 1)} (π) .

Therefore $d_{H} (e, π) = n - 1 - χ_{(n - 1, 1)} (π)$ .

Step 3 (Express via all characters). Using the column orthogonality of the character table, the fixed point function can also be written as:

fix (π) = \frac{1}{( n - 1 )!} λ \sum d_{λ} χ_{λ} (π) χ_{λ} (transposition)

since the transposition class generates the $S_{n}$ -invariant bilinear form that pairs with $fix$ . This gives the stated formula for $d_{H}$ . $□$

Bridge. The character-theoretic expressions for metrics build toward the spectral analysis of permutation data in 07.05.11 where distances between distributions are measured by spectral norms, and appear again in 07.05.13 where metrics on cosets extend the framework to partial rankings. The foundational reason the character expansion works is that every right-invariant function on $S_{n}$ is a class function of $σ^{- 1} π$ , and the characters form an orthonormal basis for class functions. This is exactly the content that identifies the metric geometry of $S_{n}$ with the representation-theoretic Fourier analysis; the bridge is that computing a distance between two permutations is the same as evaluating a character sum, which is the same as computing a Fourier coefficient at each irreducible representation. Putting these together with the Diaconis-Graham inequalities, the four metrics are ordered by the first and second Diaconis-Graham bounds: $d_{C} \leq d_{K} \leq 2 d_{C}$ and $d_{H} \leq 2 d_{K}$ .

Exercises [Intermediate+]

Exercise 7 (hard, symbolic).

Prove that the Kendall tau distance $d_{K}$ on $S_{n}$ equals the length function $ℓ$ of the Coxeter group $S_{n}$ with respect to the simple reflections $s_{i} = (i, i + 1)$ , i.e., $d_{K} (e, π) = ℓ (π)$ where $ℓ (π)$ is the minimum number of adjacent transpositions needed to express $π$ .

Hint

Show that the number of inversions of $π$ equals the length of any reduced expression for $π$ in the Coxeter generators. Use the fact that each adjacent transposition $s_{i}$ changes the inversion count by exactly 1.

Answer

The adjacent transposition $s_{i} = (i, i + 1)$ swaps positions $i$ and $i + 1$ in one-line notation, introducing or removing exactly 1 inversion (the pair $(i, i + 1)$ ). Any reduced expression $π = s_{i_{1}} s_{i_{2}} \dots s_{i_{ℓ}}$ builds $π$ from the identity by $ℓ$ adjacent transpositions, each changing the inversion count by 1. So $ℓ (π) = d_{K} (e, π)$ . Conversely, the inversion set of $π$ uniquely determines $π$ (by the Lehmer code), and the cardinality of the inversion set equals $d_{K} (e, π)$ , which is achieved by the bubble-sort algorithm in exactly $d_{K}$ steps.

Exercise 8 (hard, symbolic).

Prove the second Diaconis-Graham inequality: $d_{K} (π, σ) \leq 2 \cdot d_{C} (π, σ) \cdot (n - d_{C} (π, σ))$ for all $π, σ \in S_{n}$ .

Hint

A single transposition $(i j)$ introduces at most $2∣ j - i ∣ - 1 \leq 2 (n - 1) - 1 = 2 n - 3$ inversions. Use the bound $∣ j - i ∣ \leq n - 1$ . Then refine using the fact that $k$ transpositions can introduce at most $2 k (n - k)$ inversions by optimising the transposition sizes.

Answer

Write $k = d_{C} (π, σ)$ and express $σ^{- 1} π = τ_{1} \dots τ_{k}$ with each $τ_{i}$ a transposition of elements at positions $a_{i}$ and $b_{i}$ with $a_{i} < b_{i}$ . The number of inversions introduced by $τ_{i}$ is at most $2 (b_{i} - a_{i}) - 1 \leq 2 (n - 1) - 1$ . However, a tighter bound is obtained by noting that the total displacement $\sum_{i} (b_{i} - a_{i})$ is at most $k (n - k)$ (since $k$ transpositions can move elements at most $k$ positions from their origin in each direction). This gives $d_{K} \leq 2 \cdot k \cdot (n - k)$ , which is the stated inequality (actually a slight variant; the precise Diaconis-Graham bound is $d_{K} \leq 2 d_{C} \cdot (n - d_{C})$ , proved by induction on $k$ using the fact that the inversion count after $k$ transpositions is maximised when the transpositions are chosen to maximise displacement at each step).

Advanced results [Master]

Theorem 1 (Diaconis-Graham inequalities 1977). For all $π, σ \in S_{n}$ :

d_{C} (π, σ) \leq d_{K} (π, σ), d_{K} (π, σ) \leq 2 d_{C} (π, σ) (n - d_{C} (π, σ)) .

These bounds are tight. The lower bound is achieved when $σ^{- 1} π$ is a single transposition of adjacent elements. The upper bound is achieved when $σ^{- 1} π$ is a product of disjoint transpositions that maximise the displacement.

Theorem 2 (Cayley distance and characters). The Cayley distance has the closed-form character expression:

d_{C} (e, π) = n - ℓ (μ) = λ ⊢ n \sum \frac{n - ℓ ( μ )}{\sum _{ν} d _{ν}^{2}} d_{λ}^{2} (1 - \frac{χ _{λ} ( μ )}{d _{λ}}),

where $μ$ is the cycle type of $π$ and $ℓ (μ)$ is the number of parts. The inner sum simplifies because only the identity and standard representations contribute substantively for small Cayley distance.

This expression was derived by Diaconis 1988 using the fact that the Cayley distance is a class function depending only on cycle type.

Theorem 3 (Hamming distance and Fourier transform). The Hamming distance decomposes spectrally as:

d_{H} (e, π) = (n - 1) (1 - \frac{χ _{(n - 1, 1)} ( π )}{n - 1}) = n - 1 - χ_{(n - 1, 1)} (π) .

This is the simplest character formula among the four metrics because only the standard representation contributes.

Theorem 4 (Spearman footrule and its spectral expansion). The Spearman footrule $d_{S} (π, e) = \sum_{i} ∣ π (i) - i ∣$ has a Fourier expansion involving the characters of the standard representation and its exterior powers. Diaconis and Graham 1977 showed that $d_{S} \leq 2 d_{K}$ and $d_{S} \leq 2 d_{H} (n - d_{H})$ .

Theorem 5 (Metric properties and the Bruhat order). The Kendall tau distance (equivalently, the Coxeter length) respects the Bruhat order on $S_{n}$ : if $π \leq σ$ in Bruhat order, then $d_{K} (e, π) \leq d_{K} (e, σ)$ . The Bruhat order is the partial order generated by the relation $π \leq π τ$ whenever $τ$ is a transposition that increases the inversion count.

This connects the metric geometry of $S_{n}$ to the combinatorics of the Bruhat order, which is fundamental in Schubert calculus.

Theorem 6 (Expected distances under uniformity). Under the uniform distribution on $S_{n}$ :

E [d_{K}] = \frac{1}{2} (2 n), E [d_{H}] = n (1 - \frac{1}{n}) = n - 1, E [d_{C}] = n - H_{n},

where $H_{n} = \sum_{k = 1}^{n} 1/ k$ is the $n$ -th harmonic number. These expected values are computed from the character expressions by taking expectations of the characters, which evaluate to 0 for non-identity representations under the uniform distribution.

Synthesis. The character-theoretic expressions for metrics on $S_{n}$ provide the foundational reason that representation theory unifies the metric geometry of permutations. The central insight is that right-invariant metrics on $S_{n}$ are determined by their values at the identity, which are class functions with Fourier expansions in the irreducible characters. Putting these together with the Diaconis-Graham inequalities, the four standard metrics are ordered and related by universal bounds, and each has a clean spectral formula. This is exactly the content that builds toward the analysis of partial rankings in 07.05.13 where metrics on cosets are defined by lifting through the quotient map, and appears again in 07.05.11 where distances between probability distributions on $S_{n}$ are measured by character sums via the Upper Bound Lemma. The bridge is between the combinatorial definition of each metric and its Fourier-analytic representation; the pattern generalises from bi-invariant metrics (Cayley) to right-invariant metrics (all four), and identifies the character table of $S_{n}$ as the universal conversion device between different notions of distance on permutations.

Full proof set [Master]

Proposition 1 (Hamming distance character formula). For all $π \in S_{n}$ :

d_{H} (e, π) = n - 1 - χ_{(n - 1, 1)} (π) .

Proof. The permutation representation $C^{n}$ decomposes as $1 \oplus V^{(n - 1, 1)}$ , where $1$ is the identity representation and $V^{(n - 1, 1)}$ is the standard representation. The character of the permutation representation at $π$ is $fix (π)$ , the number of fixed points. So $fix (π) = 1 + χ_{(n - 1, 1)} (π)$ . Since $d_{H} (e, π) = n - fix (π) = n - 1 - χ_{(n - 1, 1)} (π)$ . $□$

Proposition 2 (Expected Hamming distance). Under the uniform distribution on $S_{n}$ , $E [d_{H}] = n - 1$ .

Proof. $E [d_{H}] = n - 1 - E [χ_{(n - 1, 1)}]$ . The expected character value under the uniform distribution is $\frac{1}{n !} \sum_{π} χ_{(n - 1, 1)} (π) = 0$ by the orthogonality of characters (the inner product of any non-identity character with the identity character is 0). Hence $E [d_{H}] = n - 1$ . $□$

Connections [Master]

Spectral analysis of permutation data 07.05.11. The character-theoretic expressions for metrics are computed using the same Fourier transform on $S_{n}$ that decomposes ranking data into spectral components. The first-order spectral coefficient in 07.05.11 determines the Hamming distance between the empirical distribution and uniformity; the metric formulas of this unit provide the pointwise versions.
Random walk upper bound lemma 07.05.05. The Upper Bound Lemma bounds total variation distance by a character sum, which is a spectral expression of the same type as the metric formulas. The mixing time analysis in 07.05.05 uses the character values on transpositions, which are the same values appearing in the Cayley and Hamming distance formulas.
Partially ranked data 07.05.13. Metrics on $S_{n}$ extend to partial rankings via the coset structure $S_{n} / S_{n - k}$ , where the induced metrics on cosets are defined by minimising the metric over coset representatives. The Gelfand pair structure in 07.05.13 ensures that these induced metrics retain clean character-theoretic expressions.
Symmetric group representation 07.05.01. The character table of $S_{n}$ , the hook-length formula for dimensions, and the Murnaghan-Nakayama rule for computing character values developed in 07.05.01 and 07.05.10 are the computational tools needed to evaluate the metric formulas for specific permutations.

Historical & philosophical context [Master]

The systematic study of metrics on the symmetric group was initiated by Diaconis and Graham in their 1977 paper Spearman's Footrule as a Measure of Disarray ^{[DiaconisGraham1977]}, which established the inequalities relating the four standard metrics. Diaconis developed the character-theoretic expressions in his 1988 monograph Group Representations in Probability and Statistics ^{[Diaconis1988]}, showing that the Fourier analysis on $S_{n}$ provides a unified framework for computing all standard metrics.

Critchlow 1985 Metric Methods for Analyzing Partially Ranked Data ^{[Critchlow1985]} extended the metric framework to partial rankings and developed the induced metrics on cosets. The connection between the Kendall tau distance and the Coxeter length function of $S_{n}$ was observed in the combinatorics literature by Björner and Brenti 2005 in Combinatorics of Coxeter Groups.

Bibliography [Master]

@article{DiaconisGraham1977,
  author = {Diaconis, Persi and Graham, R. L.},
  title = {Spearman's Footrule as a Measure of Disarray},
  journal = {J. Roy. Statist. Soc. Ser. B},
  volume = {39},
  year = {1977},
  pages = {262--268},
}

@book{Diaconis1988metrics,
  author = {Diaconis, Persi},
  title = {Group Representations in Probability and Statistics},
  publisher = {Institute of Mathematical Statistics},
  year = {1988},
  series = {IMS Lecture Notes--Monograph Series},
  volume = {11},
}

@book{Critchlow1985,
  author = {Critchlow, Douglas E.},
  title = {Metric Methods for Analyzing Partially Ranked Data},
  publisher = {Springer},
  year = {1985},
  series = {Lecture Notes in Statistics},
  volume = {34},
}

@book{BjornerBrenti2005,
  author = {Bj\"orner, Anders and Brenti, Francesco},
  title = {Combinatorics of Coxeter Groups},
  publisher = {Springer},
  year = {2005},
}