HUANG, GUESTRIN AND GUIBAS
To avoid collapsing away so much information, we might define richer summary statistics that might
capture ‘higher-order’ effects. We define the second-order unordered permutation representation
by:
[τ
(n−2,2)
(σ)]
{i, j},{k,ℓ}
= 1
{
σ({k, ℓ}) = {i, j}
}
,
where we index the matrix rows and columns by unordered pairs {i, j}. The condition inside the
indicator function states that the representation captures whether the pair of objects {k,ℓ} maps to
the pair {i, j}, but is indifferent with respect to the ordering; that is, either k 7→ i and ℓ 7→ j, or,
k 7→ j and ℓ 7→ i.
Example 5 For n = 4, there are six possible unordered pairs: {1,2},{1,3},{1, 4},{2, 3},{2,4}, and
{3,4}. The matrix representation of the permutation (1, 2, 3) is:
τ
(2,2)
(1,2, 3) =
{1,2} {1, 3} {1, 4} {2,3} {2,4} {3,4}
{1,2} 0 0 0 1 0 0
{1,3}
1 0 0 0 0 0
{1,4}
0 0 0 0 1 0
{2,3}
0 1 0 0 0 0
{2,4}
0 0 0 0 0 1
{3,4}
0 0 1 0 0 0
.
The second order ordered permutation representation, τ
(n−2,1,1)
, is defined similarly:
[τ
(n−2,1,1)
(σ)]
(i, j),(k,ℓ)
= 1
{
σ((k, ℓ)) = (i, j)
}
,
where (k,ℓ) denotes an ordered pair. Therefore, [τ
(n−2,1,1)
(σ)]
(i, j),(k,ℓ)
is 1 if and only if σ maps k to
i and ℓ to j.
As in the first-order case, the Fourier transform of a probability distribution at τ
(n−2,2)
, returns
a matrix of marginal probabilities of the form: P(σ : σ({k,ℓ}) = {i, j}), which captures statements
like, "Alice and Bob occupy Tracks 1 and 2 with probability 1/2". Similarly, the Fourier transform
at τ
(n−2,1,1)
returns a matrix of marginal probabilities of the form P(σ : σ((k,ℓ)) = (i, j)), which
captures statements like, "Alice is in Track 1 and Bob is in Track 2 with probability 9/10".
We can go further and define third-order representations, fourth-order representations, and so
on. In general however, the permutation representations as they have been defined above are re-
ducible, intuitively due to the fact that it is possible to recover lower order marginal probabilities
from higher order marginal probabilities. For example, one can recover the normalization constant
(corresponding to the trivial representation) from the first order matrix of marginals by summing
across either the rows or columns, and the first order marginal probabilities from the second order
marginal probabilities by summing across appropriate matrix entries. To truly leverage the machin-
ery of Fourier analysis, it is important to understand the Fourier transform at the irreducibles of
the symmetric group, and in the next section, we show how to derive the irreducible representa-
tions of the Symmetric group by first defining permutation representations, then “subtracting off the
lower-order effects”.
5. Representation Theory on the Symmetric Group
In this section, we provide a brief introduction to the representation theory of the Symmetric group.
Rather than giving a fully rigorous treatment of the subject, our goal is to give some intuition about
1010