Spectral analysis of permutation-valued data

Intuition [Beginner]

Imagine you collect survey responses where people rank five items from best to worst. Each person's response is a permutation — a reordering of the items. You have hundreds of such rankings and want to find the main "patterns" in the data.

Fourier analysis on the symmetric group does for permutation data what ordinary Fourier analysis does for time-series data: it decomposes a complicated signal into simple frequency components. Instead of sines and cosines, the "frequencies" are the irreducible representations of the symmetric group, indexed by partitions. Each component captures a different layer of structure in the ranking data.

Why does this concept exist? Because classical statistical tools assume numerical data, but rankings are permutations — and the representation theory of the symmetric group provides the natural harmonic analysis for functions defined on permutations.

Visual [Beginner]

A diagram showing a bar chart of ranking data on three items (six possible rankings) being decomposed into three spectral components. The first component is the uniform average; the second captures "item 1 tends to be ranked first"; the third captures a pairwise swap effect.

The uniform component gives the overall popularity; the second-order component identifies which items are consistently preferred; higher components capture finer interactions.

Worked example [Beginner]

Consider ranking data on $n=3$ items. There are $3!=6$ possible rankings. Imagine we observe the following counts from 60 respondents: the identity ranking (1,2,3) appears 20 times, the swap (2,1,3) appears 10 times, and each of the remaining four rankings appears 7 or 8 times.

Step 1. Convert counts to a probability distribution $f$ on the six permutations. For the identity $f(e)=20/60=1/3$; for the swap $f((12))=10/60=1/6$; for the others roughly $1/8$.

Step 2. Compute the first spectral component: the "mean" level, which is the uniform distribution $U$ giving $1/6$ to each permutation. The deviation $f-U$ measures how far the data strays from uniform.

Step 3. The next spectral component projects onto the standard representation, which detects whether item 1 is systematically ranked too high or too low. Here, $f(e)-1/6=1/6$ and $f((12))-1/6=0$, so the data is concentrated on rankings where item 1 is first.

What this tells us: the spectral decomposition separates the overall level (uniform), the first-order preference effects (item 1 is preferred), and the residual structure, giving a hierarchical summary of the ranking data.

Check your understanding [Beginner]

Formal definition [Intermediate+]

Let $S_n$ be the symmetric group on $n$ letters with irreducible representations $V^{\lambda }$ indexed by partitions $\lambda ⊢n$, of dimension $d_{\lambda }$. Let ${\rho }^{\lambda }:S_n\to \mathrm{GL}(V^{\lambda })$ denote the irreducible representation indexed by $\lambda$.

For a function $f:S_n\to \mathbb{C}$ (e.g., a probability distribution or a data histogram), the Fourier transform of $f$ at $\lambda$ is the $d_{\lambda }\times d_{\lambda }$ matrix

$$\hat{f}(\lambda )=\sum _{\pi \in S_n}f(\pi ){\rho }^{\lambda }(\pi ).$$

The spectral decomposition of $f$ is the collection $\{\hat{f}(\lambda ){\}}_{\lambda ⊢n}$ of Fourier coefficients at all irreducible representations. The inverse Fourier formula reconstructs $f$ from its spectrum:

$$f(\pi )=\frac{1}{n!}\sum _{\lambda ⊢n}{d}_{\lambda }\mathrm{tr}\left({\rho }^{\lambda }({\pi }^{-1})\hat{f}(\lambda )\right).$$

For ranking data, the key observation is that the isotypic components correspond to interpretable statistical effects. The component at $\lambda =(n)$ is the overall mean (uniform distribution). The component at $\lambda =(n-1,1)$ captures first-order effects (marginal preferences for individual items). The components at $\lambda =(n-2,2)$ and $(n-2,1,1)$ capture second-order effects (pairwise interactions).

Counterexamples to common slips

• Confusing Fourier coefficients with eigenvalues. The Fourier coefficient $\hat{f}(\lambda )$ is a matrix, not a scalar. Its eigenvalues carry spectral information, but the coefficient itself is the basic object.
• Omitting the dimension weighting. The inverse formula weights by $d_{\lambda }$, not by 1. For $S_n$ the dimensions $d_{\lambda }$ vary widely (e.g., the standard representation has $d_{(n-1,1)}=n-1$), so this weighting is essential.
• Assuming abelian Fourier analysis suffices. For abelian groups every irreducible is 1-dimensional and the Fourier transform produces scalars. For $S_n$ the irreducibles have dimensions up to roughly $\sqrt{n!}$, so the matrix-valued transform carries much more information.

Key theorem with proof [Intermediate+]

Theorem (Spectral decomposition for ranking data — Diaconis 1989). Let $f:S_n\to [0,1]$ be a probability distribution on permutations. Define the first-order projection $f_1$ and the second-order projection $f_2$ by projecting $f$ onto the isotypic subspaces corresponding to the partitions $(n-1,1)$ and $\{(n-2,2),(n-2,1,1)\}$ respectively. Then:

$$\Vert f-U{\Vert }_2^2=\Vert \hat{f}((n-1,1)){\Vert }_{\mathrm{HS}}^2+\sum _{\begin{array}{c}\lambda ⊢n\\ \lambda \ne (n),(n-1,1)\end{array}}\frac{d_{\lambda }}{n!}\Vert \hat{f}(\lambda ){\Vert }_{\mathrm{HS}}^2,$$

and the first-order term $\Vert \hat{f}((n-1,1)){\Vert }_{\mathrm{HS}}^2/(n!\cdot d_{(n-1,1)})$ equals the sum of squared deviations of the marginal ranking probabilities from uniform:

$$\frac{1}{n-1}\sum _{i=1}^n\sum _{j=1}^n{\left(P(\pi (i)=j)-\frac{1}{n}\right)}^2.$$

Proof. The proof has three steps.

Step 1 (Plancherel decomposition). By the Plancherel formula for $S_n$:

$$\sum _{\pi \in S_n}|f(\pi )-U(\pi ){|}^2=\frac{1}{n!}\sum _{\lambda ⊢n}{d}_{\lambda }\Vert \widehat{f-U}(\lambda ){\Vert }_{\mathrm{HS}}^2.$$

Since $\widehat{f-U}((n))=\hat{f}((n))-1=0$ (as $f$ is a probability measure, its Fourier transform at the identity representation equals 1), the sum starts at $\lambda =(n-1,1)$.

Step 2 (First-order identification). The standard representation $V^{(n-1,1)}$ has a concrete realisation: it is the $(n-1)$-dimensional subspace of ${\mathbb{C}}^n$ consisting of vectors whose coordinates sum to zero, with $S_n$ acting by permutation of coordinates. The Fourier coefficient $\hat{f}((n-1,1))$ can be computed entry by entry:

$$\hat{f}((n-1,1){)}_{a,b}=\sum _{\pi }f(\pi )\cdot [{\rho }^{(n-1,1)}(\pi ){]}_{a,b}.$$

Using the basis $e_i-e_{i+1}$ for $i=1,\dots ,n-1$, the matrix entries of ${\rho }^{(n-1,1)}(\pi )$ encode whether $\pi$ maps $i$ to $j$. The squared Hilbert-Schmidt norm then becomes a sum over the marginal probabilities $P(\pi (i)=j)={\sum }_{\pi :\pi (i)=j}f(\pi )$:

$$\frac{d_{(n-1,1)}}{n!}\Vert \hat{f}((n-1,1)){\Vert }_{\mathrm{HS}}^2=(n-1)\sum _{i,j}{\left(P(\pi (i)=j)-\frac{1}{n}\right)}^2.$$

The factor $(n-1)$ arises from the relationship between the trace inner product on the $(n-1)$-dimensional representation and the full $n\times n$ permutation matrix entries.

Step 3 (Combine). Separating the $(n-1,1)$ term from the rest of the Plancherel sum gives the stated decomposition. The first-order term captures all marginal (single-item) effects; the remaining terms capture all higher-order interactions. $\square$

Bridge. This spectral decomposition builds toward the analysis of partial rankings in 07.05.13 where the coset structure $S_n/S_{n-k}$ requires the representation theory of Gelfand pairs, and appears again in the metric analysis of 07.05.12 where the character-theoretic expressions for distances between permutations emerge from the same Fourier coefficients. The foundational reason the decomposition works is that the group algebra $\mathbb{C}[S_n]$ decomposes as a direct product of matrix algebras ${\prod }_{\lambda }{M}_{d_{\lambda }}(\mathbb{C})$, which is exactly the Artin-Wedderburn decomposition. The bridge is between statistical data analysis on permutations and the harmonic analysis on $S_n$ developed in 07.05.01; putting these together, every test statistic on ranking data has a representation-theoretic interpretation as a spectral norm.

Exercises [Intermediate+]

Advanced results [Master]

Theorem 1 (Diaconis 1989: spectral analysis generalises ANOVA). The decomposition of $L^2(S_n)$ into isotypic components generalises the classical ANOVA decomposition for factorial designs. The identity component gives the grand mean; the $(n-1,1)$ component gives the main effects; the $(n-2,2)$ and $(n-2,1,1)$ components give the two-factor interactions; and so on through the partition lattice.

This was established in Diaconis 1989 J. Amer. Statist. Assoc. 84, where the isomorphism between isotypic components and ANOVA effects was made explicit through the relationship between irreducible characters and the inclusion-exclusion structure of marginal probabilities.

Theorem 2 (Mallows model: explicit Fourier coefficients). For the Mallows model $f(\pi )=e^{-\theta d_K(\pi ,{\pi }_0)}/Z$ with Kendall tau distance $d_K$, the Fourier coefficients satisfy $\hat{f}(\lambda )=c_{\lambda }{I}_{d_{\lambda }}$ where $c_{\lambda }$ is expressible as a rational function of $q=e^{-\theta }$ involving the hook lengths of $\lambda$.

The closed-form expression was given by Diaconis 1989 and developed further by Marden 1995. The coefficient at $\lambda =(n-1,1)$ equals $(1-q)/(1-q^n)$, providing a direct link between the dispersion parameter and the first-order spectral component.

Theorem 3 (Consistency of spectral estimates). If $X_1,\dots ,X_N$ are i.i.d. draws from a distribution $f$ on $S_n$, then the empirical Fourier coefficients ${\hat{f}}_N(\lambda )=\frac{1}{N}{\sum }_{k=1}^N{\rho }^{\lambda }(X_k)$ satisfy ${\hat{f}}_N(\lambda )\to \hat{f}(\lambda )$ almost surely as $N\to \infty$, and $\sqrt{N}({\hat{f}}_N(\lambda )-\hat{f}(\lambda ))$ converges in distribution to a matrix-valued Gaussian.

This follows from the multivariate central limit theorem applied to the matrix entries of ${\rho }^{\lambda }(X_k)$, which are bounded random variables.

Theorem 4 (Testing uniformity via spectral components). To test $H_0:f=U$ against $H_1:f\ne U$, the test statistic $T={\sum }_{\pi }(f_N(\pi )-1/n!{)}^2$ has a representation-theoretic decomposition $T=\frac{1}{n!}{\sum }_{\lambda \ne (n)}{d}_{\lambda }\Vert {\hat{f}}_N(\lambda ){\Vert }_{\mathrm{HS}}^2$, and the first-order term $\Vert {\hat{f}}_N((n-1,1)){\Vert }_{\mathrm{HS}}^2$ provides the most powerful invariant test against alternatives with first-order structure.

This result appears in Diaconis 1989 and connects to the Neyman-Pearson lemma for group-invariant testing problems.

Theorem 5 (Diaconis 1989: sufficient statistics from spectral components). For the exponential family $f(\pi )=\exp ({\sum }_{\lambda }⟨{\Theta }_{\lambda },{\rho }^{\lambda }(\pi )⟩-A(\Theta ))/Z$, where ${\Theta }_{\lambda }$ is a $d_{\lambda }\times d_{\lambda }$ matrix parameter for each partition $\lambda$, the collection of empirical Fourier coefficients $\{{\hat{f}}_N(\lambda )\}$ forms a sufficient statistic.

This is the exponential family on $S_n$ with natural parameters in each isotypic component; sufficiency follows from the factorisation theorem since the log-likelihood depends on the data only through the Fourier coefficients.

Theorem 6 (Spectral analysis of paired comparisons). For paired-comparison data (where subjects choose between pairs of items), the Bradley-Terry model has a spectral interpretation: the Bradley-Terry preference parameters are the eigenvalues of the first-order Fourier coefficient $\hat{f}((n-1,1))$.

This was observed by Marden 1995 and connects classical psychometric models to the spectral framework.

Synthesis. Spectral analysis of permutation-valued data is the foundational reason that representation theory enters statistics through the symmetric group. The central insight is that the Artin-Wedderburn decomposition of $\mathbb{C}[S_n]$ identifies the space of real-valued functions on permutations with the direct product of matrix algebras ${\prod }_{\lambda }{M}_{d_{\lambda }}(\mathbb{C})$, and putting these together with the Plancherel isomorphism, every statistical question about ranking data has a spectral reformulation. This is exactly the content that builds toward the metric analysis in 07.05.12 where distances between permutations become spectral norms, and appears again in 07.05.13 where partial rankings extend the framework to cosets. The bridge is between the combinatorics of partitions and the statistics of rankings; the pattern generalises from full rankings to partial rankings to paired comparisons, identifying the Fourier transform on $S_n$ as the universal tool for permutation-valued data analysis.

Full proof set [Master]

Proposition 1 (Inverse Fourier formula). For $f:S_n\to \mathbb{C}$:

$$f(\pi )=\frac{1}{n!}\sum _{\lambda ⊢n}{d}_{\lambda }\mathrm{tr}\left({\rho }^{\lambda }({\pi }^{-1})\hat{f}(\lambda )\right).$$

Proof. Expand $\hat{f}(\lambda )={\sum }_{\sigma }f(\sigma ){\rho }^{\lambda }(\sigma )$. Then:

$$\frac{1}{n!}\sum _{\lambda }{d}_{\lambda }\mathrm{tr}\left({\rho }^{\lambda }({\pi }^{-1})\hat{f}(\lambda )\right)=\frac{1}{n!}\sum _{\lambda }{d}_{\lambda }\sum _{\sigma }f(\sigma )\mathrm{tr}\left({\rho }^{\lambda }({\pi }^{-1}){\rho }^{\lambda }(\sigma )\right).$$

By the orthogonality of characters: ${\sum }_{\lambda }{d}_{\lambda }\mathrm{tr}({\rho }^{\lambda }({\pi }^{-1}){\rho }^{\lambda }(\sigma ))={\sum }_{\lambda }{d}_{\lambda }{\chi }_{\lambda }({\pi }^{-1}\sigma )=n!\cdot {\delta }_{\pi ,\sigma }$ (column orthogonality of characters at the identity). Hence the right side collapses to $f(\pi )$. $\square$

Proposition 2 (First-order coefficient and marginals). For a probability distribution $f$ on $S_n$, the trace of $\hat{f}((n-1,1))$ equals ${\sum }_{i=1}^{n}P(\pi (i)=i)-1$.

Proof. The character of the standard representation at $\pi$ is ${\chi }_{(n-1,1)}(\pi )=\text{fix}(\pi )-1$ where $\text{fix}(\pi )$ is the number of fixed points of $\pi$. So:

$$\mathrm{tr}(\hat{f}((n-1,1)))=\sum _{\pi }f(\pi ){\chi }_{(n-1,1)}(\pi )=\sum _{\pi }f(\pi )(\text{fix}(\pi )-1)=\sum _{i=1}^{n}P(\pi (i)=i)-1.\square$$

Connections [Master]

• Random walk upper bound lemma 07.05.05. The spectral decomposition of permutation data is the static counterpart to the dynamic analysis in 07.05.05. The Upper Bound Lemma bounds the distance of a random walk distribution from uniform using the same character sums that appear here as spectral components; the random walk at time $k$ has Fourier coefficients $\hat{Q}(\lambda {)}^k$, and their decay rates control mixing, while the spectral analysis of data examines the same coefficients for a fixed empirical distribution.

• Symmetric group representation 07.05.01. The irreducible representations of $S_n$ indexed by partitions, their characters, and the hook-length formula for dimensions developed in 07.05.01 are the raw material for the spectral decomposition. Every Fourier coefficient $\hat{f}(\lambda )$ is computed using the matrix representations ${\rho }^{\lambda }$ and the characters ${\chi }_{\lambda }$ from that unit.

• Metrics on the symmetric group 07.05.12. The character-theoretic expressions for distances between permutations developed in the next unit are spectral norms of the difference of Fourier coefficients. The Cayley, Hamming, and Kendall tau distances all have representations as weighted character sums, making the spectral decomposition of this unit the common framework unifying distance computations on permutations.

• Schur-Weyl duality 07.05.04. The decomposition of tensor powers of ${\mathbb{C}}^n$ via Schur-Weyl duality produces the same indexing by partitions that governs the spectral analysis. The isotypic components of $L^2(S_n)$ are dual to the irreducible ${\mathrm{GL}}_n$-modules in the tensor algebra, linking the statistical framework to the representation theory of the general linear group.

Historical & philosophical context [Master]

Diaconis introduced spectral analysis of permutation-valued data in his 1989 paper A Generalization of Spectral Analysis ^{[Diaconis1989]} published in J. Amer. Statist. Assoc. 84. The key insight was that the ANOVA decomposition for factorial designs, which separates main effects from interactions, has a natural generalisation to permutations via the isotypic decomposition of the group algebra of $S_n$.

The statistical framework was systematised in Diaconis's 1988 monograph Group Representations in Probability and Statistics ^{[Diaconis1988]}, which placed the spectral analysis alongside the random walk and shuffling results as part of a unified programme applying representation theory to probability and statistics. Marden 1995 extended the framework to a wide variety of ranking models in Analyzing and Modeling Rank Data ^[Marden1995], including the Mallows model, the Bradley-Terry model, and the Plackett-Luce model.

Bibliography [Master]

@article{Diaconis1989,
  author = {Diaconis, Persi},
  title = {A Generalization of Spectral Analysis},
  journal = {J. Amer. Statist. Assoc.},
  volume = {84},
  year = {1989},
  pages = {694--701},
}

@book{Diaconis1988,
  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{Marden1995,
  author = {Marden, John I.},
  title = {Analyzing and Modeling Rank Data},
  publisher = {Chapman \& Hall},
  year = {1995},
}